|
Computational Complexity: Reductions, Resources, and Robustness
This project focuses on
complexity theory. It also
studies the power of heuristic algorithms.
Among the
themes of this project are:
- Reductions
- Reductions are the tools with which the relative complexity
of problems are compared. How powerful are various types of
reductions? How robust are they with respect to definitional
variation?
- Resources and Models
- Complexity classes help us group together
problems that can be solved via a certain type of computing resource.
What problems can be solved withing what resource bounds?
Does increasing a resource increase the class of languages
that can be accepted (hierarchy theorems)? Also, as
one varies one's model of computation, how does the class
of languages accepted vary?
How do
resource-bounded measure and resource-bounded category help us
understand the relationships between complexity classes?
- Robustness
- Robustness is used here in the sense of being invariant (or at least
relatively resilient) with respect to the varying of some parameter.
For example, the theory of robust Turing machines studies the degree
to a computation can remain correct even given faulty access to an
information source it is using.
- Power of Heuristic Algorithms
- What
problems can be well-solved by heuristic algorithms? In which settings
can heuristic algorithms be used to obtain provably exact, optimal
solutions?
Note:
The
unifying idea of
all Lane's work is complexity (and
algorithms, but Lane's view of complexity is that it is often best
pursued through algorithms, although admittedly ones that operate
under hypotheses--that connection is the theme of Lane and Mitsunori
Ogihara's
book);
to Lane complexity
not only is a project but also is his
career theme.
And so this page contains most of the papers from his other
more focused projects, which can be found listed on
the department research project
pages.
- 1
-
This is a list of selected journal (except when the work has not yet
appeared in journal/book form, plus in some cases some conference articles)
papers, from or related to this project, by University of Rochester authors.
Essentially all the papers listed below can be found, in their full technical
report versions, in the UR-CS Technical Report Archive's
theory section. Here is
Lane's complete publication
list
and links to
essentially all his conference and journal papers (and also his arXiv.org
technical reports) can be found via the ``EE'' (electronic edition) links at
Lane's entry at the DBLP
project.
- 2
-
T. Gvozdeva, L. Hemaspaandra, and A. Slinko.
Three hierarchies of simple games parameterized by ``resource''
parameters.
International Journal of Game Theory.
To appear.
- 3
-
A. El Gamel, L. Hemachandra, I. Shperling, and V. Wei.
Using simulated annealing to design good codes.
IEEE Transactions on Information Theory, IT-33(1):116-123,
1987.
- 4
-
J. Hartmanis and L. Hemachandra.
Robust machines accept easy sets.
Theoretical Computer Science, 74(2):217-226, 1990.
- 5
-
L. Hemachandra.
Algorithms from complexity theory: Polynomial-time operations for
complex sets.
In Proceedings of the 1990 SIGAL International Symposium on
Algorithms, pages 221-231. Springer-Verlag Lecture Notes in Computer
Science #450, August 1990.
- 6
-
C. Calude and G. Istrate.
Determining and stationary sets for some classes of partial recursive
functions.
Theoretical Computer Science, 82:151-155, 1991.
- 7
-
L. Hemachandra, A. Hoene, D. Siefkes, and P. Young.
On sets polynomially enumerable by iteration.
Theoretical Computer Science, 80(2):203-226, 1991.
- 8
-
L. Hemachandra and S. Jain.
On the limitations of locally robust positive reductions.
International Journal of Foundations of Computer Science,
2(3):237-255, 1991.
- 9
-
L. Hemachandra and G. Wechsung.
Kolmogorov characterizations of complexity classes.
Theoretical Computer Science, 83:313-322, 1991.
- 10
-
E. Allender and L. Hemachandra.
Lower bounds for the low hierarchy.
Journal of the ACM, 39(1):234-251, 1992.
- 11
-
C. Calude, G. Istrate, and M. Zimand.
Recursive Baire classification and speedable
functions.
Zeitschrift für Mathematische Logik und Grundlagen der
Mathematik, 38:169-178, 1992.
- 12
-
G. Buntrock, L. Hemachandra, and D. Siefkes.
Using inductive counting to simulate nondeterministic computation.
Information and Computation, 102(1):102-117, 1993.
- 13
-
J. Cai, L. Hemachandra, and J. Vyskoc.
Promises and fault-tolerant database access.
In K. Ambos-Spies, S. Homer, and U. Schöning, editors,
Complexity Theory, pages 101-146. Cambridge University Press, 1993.
- 14
-
W. Gasarch, L. Hemachandra, and A. Hoene.
On checking versus evaluation of multiple queries.
Information and Computation, 105(1):72-93, 1993.
- 15
-
L. Hemachandra.
Fault-tolerance and complexity.
In Proceedings of the 20th International Colloquium on
Automata, Languages, and Programming, pages 189-202. Springer-Verlag Lecture Notes in Computer Science #700, July 1993.
- 16
-
L. Hemachandra and A. Hoene.
Collapsing degrees via strong computation.
Journal of Computer and System Sciences, 46(3):363-380, 1993.
- 17
-
L. Hemaspaandra.
Lowness: A yardstick for NP P.
SIGACT News, 24(2):10-14, 1993.
- 18
-
L. Hemaspaandra, S. Jain, and N. Vereshchagin.
Banishing robust Turing completeness.
International Journal of Foundations of Computer Science,
4(3):245-265, 1993.
- 19
-
M. Zimand.
The complexity of the optimal spanning hypertree problem.
Technical Report TR-471, Department of Computer Science, University
of Rochester, Rochester, NY, September 1993.
- 20
-
M. Zimand.
If not empty, NP-P is topologically large.
Theoretical Computer Science, 119:293-310, 1993.
- 21
-
C. Calude, H. Jürgensen, and M. Zimand.
Is independence an exception?
Applied Mathematics and Computation, 66:63-76, 1994.
- 22
-
L. Hemaspaandra.
The not-ready-for-prime-time conjectures.
SIGACT News, 25(2):5-10, 1994.
- 23
-
D. Kratsch and L. Hemaspaandra.
On the complexity of graph reconstruction.
Mathematical Systems Theory, 27(3):257-273, 1994.
- 24
-
I. Tomescu and M. Zimand.
Optimal spanning hypertrees.
Discrete Applied Mathematics, 54:67-76, 1994.
- 25
-
L. Hemaspaandra, A. Ramachandran, and M. Zimand.
Worlds to die for.
SIGACT News, 26(4):5-15, 1995.
- 26
-
M. Zimand.
On the topological size of p-m-complete degrees.
Theoretical Computer Science, 147(2):137-147, 1995.
- 27
-
C. Calude and M. Zimand.
Effective category and measure in abstract complexity theory.
Theoretical Computer Science, 154(2):307-327, 1996.
- 28
-
L. Hemaspaandra, A. Hoene, and M. Ogihara.
Reducibility classes of P-selective sets.
Theoretical Computer Science, 155(2):447-457, 1996.
Erratum appears in the same journal, 234(1-2):323.
- 29
-
L. Hemaspaandra and M. Zimand.
Strong self-reducibility precludes strong immunity.
Mathematical Systems Theory, 29(5):535-548, 1996.
- 30
-
M. Zimand.
Existential Theorems in Computational Complexity Theory: Size
and Robustness.
Ph.D. thesis, Department of Computer Science, University of
Rochester, Rochester, NY, 1996.
UR Technical Report TR-632.
- 31
-
Y. Han, L. Hemaspaandra, and T. Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59-78, 1997.
- 32
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Exact analysis of Dodgson elections: Lewis Carroll's 1876
voting system is complete for parallel access to NP.
Journal of the ACM, 44(6):806-825, 1997.
- 33
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Raising NP lower bounds to parallel NP lower bounds.
SIGACT News, 28(2):2-13, 1997.
- 34
-
L. Hemaspaandra and Z. Jiang.
Logspace reducibility: Models and equivalences.
International Journal of Foundations of Computer Science,
8(1):95-108, 1997.
- 35
-
L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.
Polynomial-time multi-selectivity.
Journal of Universal Computer Science, 3(3):197-229, 1997.
- 36
-
L. Hemaspaandra, J. Rothe, and G. Wechsung.
Easy sets and hard certificate schemes.
Acta Informatica, 34(11):859-879, 1997.
- 37
-
L. Hemaspaandra and A. Selman, editors.
Complexity Theory Retrospective II.
Springer-Verlag, 1997.
- 38
-
M. Zimand.
Large sets in AC have many strings with low Kolmogorov
complexity.
Information Processing Letters, 62(3):165-170, 1997.
- 39
-
E. Hemaspaandra and J. Rothe.
Recognizing when greed can approximate maximum independent sets is
complete for parallel access to NP.
Information Processing Letters, 65(3):151-156, 1998.
- 40
-
L. Hemaspaandra, H. Hempel, and J. Vogel.
Optimal separations for parallel versus sequential self-checking:
Parallelism can exponentially increase self-checking cost.
Technical Report TR-691, Department of Computer Science, University
of Rochester, Rochester, NY, May 1998.
- 41
-
L. Hemaspaandra, K. Rajasethupathy, P. Sethupathy, and M. Zimand.
Power balance and apportionment algorithms for the United States
Congress.
ACM Journal of Experimental Algorithmics, 3(1), 1998.
URL doi.acm.org/10.1145/297096.297106, 16pp.
- 42
-
M. Zimand.
On the size of classes with weak membership properties.
Theoretical Computer Science, 209(1-2):225-235, 1998.
- 43
-
R. Bent, M. Schear, L. Hemaspaandra, and G. Istrate.
A note on bounded-weight error-correcting codes.
Journal of Universal Computer Science, 5(12):817-827, 1999.
- 44
-
J. Cai, L. Hemaspaandra, and G. Wechsung.
Robust reductions.
Theory of Computing Systems, 32(6):625-647, 1999.
- 45
-
M. Zimand.
Weighted NP optimization problems: Logical definability and
approximation properties.
SIAM Journal on Computing, 28(1):36-56, 1999.
- 46
-
C. Glaßer and L. Hemaspaandra.
A moment of perfect clarity I: The parallel census technique.
SIGACT News, 31(3):37-42, 2000.
- 47
-
C. Glaßer and L. Hemaspaandra.
A moment of perfect clarity II: Consequences of sparse sets hard
for NP with respect to weak reductions.
SIGACT News, 31(4):39-51, 2000.
- 48
-
R. Beigel, L. Hemaspaandra, H. Hempel, and J. Vogel.
Optimal series-parallel tradeoffs for reducing a function to its own
graph.
Information and Computation, 173(2):123-131, 2002.
- 49
-
L. Hemaspaandra and M. Ogihara.
The Complexity Theory Companion.
Springer-Verlag, 2002.
- 50
-
L. Hemaspaandra, M. Ogihara, and G. Wechsung.
Reducing the number of solutions of NP functions.
Journal of Computer and System Sciences, 64(2):311-328, 2002.
- 51
-
A. Beygelzimer and M. Ogihara.
The (non)enumerability of the determinant and the rank.
Theory of Computing Systems, 36(4):359-374, 2003.
- 52
-
L. Hemaspaandra and H. Hempel.
P-immune sets with holes lack self-reducibility properties.
Theoretical Computer Science, 302(1-3):457-466, 2003.
- 53
-
L. Hemaspaandra and L. Torenvliet.
Theory of Semi-Feasible Algorithms.
Springer-Verlag, 2003.
- 54
-
L. Hemaspaandra, H. Hempel, and A. Nickelsen.
Algebraic properties for selector functions.
SIAM Journal on Computing, 33(6):1309-1337, 2004.
- 55
-
L. Hemaspaandra and M. Thakur.
Lower bounds and the hardness of counting properties.
Theoretical Computer Science, 326(1-3):1-28, 2004.
- 56
-
A. Beygelzimer and M. Ogihara.
The enumerability of P collapses P to NC.
Theoretical Computer Science, 345(2-3):248-259, 2005.
- 57
-
J. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
Competing provers yield improved Karp-Lipton collapse results.
Information and Computation, 198(1):1-23, 2005.
- 58
-
D. Eisenstat.
Simpler proofs of the power of one query to a P-selective set.
Technical Report TR-883, Department of Computer Science, University
of Rochester, Rochester, NY, October 2005.
- 59
-
P. Faliszewski and L. Hemaspaandra.
Advice for semifeasible sets and the complexity-theoretic
cost(lessness) of algebraic properties.
International Journal of Foundations of Computer Science,
16(5):913-928, 2005.
- 60
-
P. Faliszewski and M. Ogihara.
Separating the notions of self- and autoreducibility.
In Proceedings of the 30th International Symposium on
Mathematical Foundations of Computer Science, pages 308-315.
Springer-Verlag Lecture Notes in Computer Science #3618,
August/September 2005.
- 61
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
All superlinear inverse schemes are coNP-hard.
Theoretical Computer Science, 345(2-3):345-358, 2005.
- 62
-
L. Hemaspaandra, P. Mukherji, and T. Tantau.
Context-free languages can be accepted with absolutely no space
overhead.
Information and Computation, 203(2):163-180, 2005.
- 63
-
H. Spakowski, M. Thakur, and R. Tripathi.
Quantum and classical complexity classes: Separations, collapses,
and closure properties.
Information and Computation, 200(1):1-34, 2005.
- 64
-
P. Faliszewski and L. Hemaspaandra.
Open questions in the theory of semifeasible computation.
SIGACT News, 37(1):47-65, 2006.
- 65
-
L. Hemaspaandra, M. Ogihara, M. Zaki, and M. Zimand.
The complexity of finding top-Toda-equivalence-class members.
Theory of Computing Systems, 39(5):669-684, 2006.
- 66
-
L. Hemaspaandra and L. Torenvliet.
P-selectivity, immunity, and the power of one bit.
In Proceedings of the 32nd International Conference on Current
Trends in Theory and Practice of Computer Science, pages 323-331.
Springer-Verlag Lecture Notes in Computer Science #3881, January 2006.
- 67
-
L. Hemaspaandra, C. Homan, S. Kosub, and K. Wagner.
The complexity of computing the size of an interval.
SIAM Journal on Computing, 36(5):1264-1300, 2006-2007.
- 68
-
E. Hemaspaandra and L. Hemaspaandra.
Dichotomy for voting systems.
Journal of Computer and System Sciences, 73(1):73-83, 2007.
- 69
-
E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R. Tripathi.
Complexity results in graph reconstruction.
Discrete Applied Mathematics, 155(2):103-118, 2007.
- 70
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artificial Intelligence, 171(5-6):255-285, 2007.
- 71
-
L. Hemaspaandra, C. Homan, and S. Kosub.
Cluster computing and the power of edge recognition.
Information and Computation, 205(8):1274-1293, 2007.
- 72
-
L. Hemaspaandra and M. Thakur.
Query-monotonic Turing reductions.
Theoretical Computer Science, 383(2-3):153-186, 2007.
- 73
-
E. Brelsford, P. Faliszewski, E. Hemaspaandra, H. Schnoor, and I. Schnoor.
Approximability of manipulating elections.
In Proceedings of the 23rd AAAI Conference on Artificial
Intelligence, pages 44-49. AAAI Press, July 2008.
- 74
-
P. Faliszewski.
Manipulations of elections: Algorithms and infeasibility results.
Technical Report TR-941, Department of Computer Science, University
of Rochester, Rochester, NY, November 2008.
This is the technical report version, available on the web at
cs.rochester.edu/trs/theory-trs.html, of Piotr Faliszewski's Ph.D.
dissertation.
- 75
-
P. Faliszewski.
Nonuniform bribery.
In Proceedings of the 7th International Conference on
Autonomous Agents and Multiagent Systems, pages 1569-1572. International
Foundation for Autonomous Agents and Multiagent Systems, May 2008.
- 76
-
P. Faliszewski, E. Hemaspaandra, and H. Schnoor.
Copeland voting: Ties matter.
In Proceedings of the 7th International Conference on
Autonomous Agents and Multiagent Systems, pages 983-990. International
Foundation for Autonomous Agents and Multiagent Systems, May 2008.
- 77
-
P. Faliszewski and L. Hemaspaandra.
The consequences of eliminating NP solutions.
Computer Science Review, 2(1):40-54, 2008.
- 78
-
L. Hemaspaandra, J. Rothe, and A. Saxena.
Enforcing and defying associativity, commutativity, totality, and
strong noninvertibility for one-way functions in complexity theory.
Theoretical Computer Science, 401(1-3):27-35, 2008.
- 79
-
M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind.
Manipulating quota value in weighted voting games.
In Proceedings of the 23rd AAAI Conference on Artificial
Intelligence, pages 215-220. AAAI Press, July 2008.
- 80
-
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Frequency of correctness versus average polynomial time.
Information Processing Letters, 109(16):946-949, 2009.
- 81
-
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Generalized juntas and NP-hard sets.
Theoretical Computer Science, 410(38-40):3995-4000, 2009.
- 82
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
How hard is bribery in elections?
Journal of Artificial Intelligence Research, 35:485-532,
2009.
- 83
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
In Proceedings of the 21st International Joint Conference on
Artificial Intelligence, pages 128-133. AAAI Press & IJCAI, July 2009.
- 84
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Llull and Copeland voting computationally resist bribery and
constructive control.
Journal of Artificial Intelligence Research, 35:275-341,
2009.
- 85
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
A richer understanding of the complexity of election systems.
In S. Ravi and S. Shukla, editors, Fundamental Problems in
Computing: Essays in Honor of Professor Daniel J. Rosenkrantz,
pages 375-406. Springer, 2009.
- 86
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The shield that never was: Societies with single-peaked preferences
are more open to manipulation and control.
In Proceedings of the 12th Conference on Theoretical Aspects of
Rationality and Knowledge, pages 118-127. ACM Digital Library, July 2009.
- 87
-
P. Faliszewski and L. Hemaspaandra.
The complexity of power-index comparison.
Theoretical Computer Science, 410(1):101-107, 2009.
- 88
-
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexity-theoretic resistance to control.
Mathematical Logic Quarterly, 55(4):397-424, 2009.
- 89
-
C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding
Dodgson-election winners.
Journal of Heuristics, 15(4):403-423, 2009.
- 90
-
D. Baumeister, G. Erdélyi, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Computational aspects of approval voting.
In J. Laslier and M. Sanver, editors, Handbook on Approval
Voting, pages 199-251. Springer, 2010.
- 91
-
F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomial-time algorithms for
single-peaked electorates.
In Proceedings of the 24th AAAI Conference on Artificial
Intelligence, pages 715-722. AAAI Press, July 2010.
- 92
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Using complexity to protect elections.
Communications of the ACM, 53(11):74-82, 2010.
- 93
-
E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
Theoretical Computer Science, 411(4-5):783-798, 2010.
- 94
-
L. Hemaspaandra.
A note on nonuniform versus uniform ACC circuits for NE.
Technical Report TR-964, Department of Computer Science, University
of Rochester, Rochester, NY, December 2010.
- 95
-
C. Menton.
Normalized range voting broadly resists control.
Technical Report arXiv:1005.5698 [cs.GT], Computing Research
Repository, arXiv.org/corr/, May 2010.
- 96
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked
electorates.
In Proceedings of the 13th Conference on Theoretical Aspects of
Rationality and Knowledge, pages 228-237. ACM Digital Library, July 2011.
- 97
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
Journal of Artificial Intelligence Research, 40:305-351,
2011.
- 98
-
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The shield that never was: Societies with single-peaked preferences
are more open to manipulation and control.
Information and Computation, 209(2):89-107, 2011.
(Last modified: February 1, 2012.)
Lane A. Hemaspaandra
|