Computational Complexity: Reductions, Resources, and Robustness

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)

Project Description

This project focuses on a number of foundational issues regarding the key tools of complexity theory. It also studies the power of heuristic algorithms. Among the main streams 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: Many of the theory group's other projects also use the notions of reductions and problem classification. These projects can be viewed via the departmental research project pages.)

Bibliography

1
This is a list of selected journal (except when the work has not yet appeared in journal/book form) 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
E. Allender and L. Hemachandra.
Lower bounds for the low hierarchy.
Journal of the ACM, 39(1):234-251, 1992.

3
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.

4
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.

5
A. Beygelzimer and M. Ogihara.
The (non)enumerability of the determinant and the rank.
Theory of Computing Systems, 36(4):359-374, 2003.

6
A. Beygelzimer and M. Ogihara.
The enumerability of P collapses P to NC.
Theoretical Computer Science, 345(2-3):248-259, 2005.

7
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. AAAI Press, July 2008.
To appear.

8
G. Buntrock, L. Hemachandra, and D. Siefkes.
Using inductive counting to simulate nondeterministic computation.
Information and Computation, 102(1):102-117, 1993.

9
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.

10
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.

11
J. Cai, L. Hemaspaandra, and G. Wechsung.
Robust reductions.
Theory of Computing Systems, 32(6):625-647, 1999.

12
C. Calude and G. Istrate.
Determining and stationary sets for some classes of partial recursive functions.
Theoretical Computer Science, 82:151-155, 1991.

13
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.

14
C. Calude, H. Jürgensen, and M. Zimand.
Is independence an exception?
Applied Mathematics and Computation, 66:63-76, 1994.

15
C. Calude and M. Zimand.
Effective category and measure in abstract complexity theory.
Theoretical Computer Science, 154(2):307-327, 1996.

16
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.

17
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time.
In Proceedings of the 16th International Symposium on Fundamentals of Computation Theory, pages 300-311. Springer-Verlag Lecture Notes in Computer Science #4639, August 2007.

18
P. Faliszewski.
Nonuniform bribery.
In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, pages 1569-1572, May 2008.

19
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of bribery in elections.
In Proceedings of the 21st National Conference on Artificial Intelligence, pages 641-646. AAAI Press, July 2006.

20
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. Springer.
To appear.

21
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Llull and Copeland voting broadly resist bribery and control.
In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pages 724-730. AAAI Press, July 2007.

22
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Copeland voting fully resists constructive control.
In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, pages 165-176. Springer-Verlag Lecture Notes in Computer Science, June 2008.
To appear.

23
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, May 2008.

24
P. Faliszewski and L. Hemaspaandra.
The consequences of eliminating NP solutions.
Computer Science Review.
To appear.

25
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.

26
P. Faliszewski and L. Hemaspaandra.
Open questions in the theory of semifeasible computation.
SIGACT News, 37(1):47-65, 2006.

27
P. Faliszewski and L. Hemaspaandra.
The complexity of power-index comparison
In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, pages 177-187. Springer-Verlag Lecture Notes in Computer Science, June 2008.
To appear.

28
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.

29
W. Gasarch, L. Hemachandra, and A. Hoene.
On checking versus evaluation of multiple queries.
Information and Computation, 105(1):72-93, 1993.

30
C. Glaßer and L. Hemaspaandra.
A moment of perfect clarity I: The parallel census technique.
SIGACT News, 31(3):37-42, 2000.

31
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.

32
Y. Han, L. Hemaspaandra, and T. Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59-78, 1997.

33
J. Hartmanis and L. Hemachandra.
Robust machines accept easy sets.
Theoretical Computer Science, 74(2):217-226, 1990.

34
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.

35
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.

36
L. Hemachandra and A. Hoene.
Collapsing degrees via strong computation.
Journal of Computer and System Sciences, 46(3):363-380, 1993.

37
L. Hemachandra, A. Hoene, D. Siefkes, and P. Young.
On sets polynomially enumerable by iteration.
Theoretical Computer Science, 80(2):203-226, 1991.

38
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.

39
L. Hemachandra and G. Wechsung.
Kolmogorov characterizations of complexity classes.
Theoretical Computer Science, 83:313-322, 1991.

40
E. Hemaspaandra and L. Hemaspaandra.
Dichotomy for voting systems.
Journal of Computer and System Sciences, 73(1):73-83, 2007.

41
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
All superlinear inverse schemes are coNP-hard.
Theoretical Computer Science, 345(2-3):345-358, 2005.

42
E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R. Tripathi.
Complexity results in graph reconstruction.
Discrete Applied Mathematics, 155(2):103-118, 2007.

43
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.

44
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Raising NP lower bounds to parallel NP lower bounds.
SIGACT News, 28(2):2-13, 1997.

45
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artificial Intelligence, 171(5-6):255-285, 2007.

46
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexity-theoretic resistance to control.
In Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 1308-1314. IJCAI, January 2007.

47
E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
In Proceedings of the 16th International Symposium on Fundamentals of Computation Theory, pages 328-340. Springer-Verlag Lecture Notes in Computer Science #4639, August 2007.

48
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.

49
L. Hemaspaandra.
Lowness: A yardstick for NP$-$P.
SIGACT News, 24 (Spring)(2):10-14, 1993.

50
L. Hemaspaandra.
The not-ready-for-prime-time conjectures.
SIGACT News, 24(2):5-10, 1994.

51
L. Hemaspaandra and H. Hempel.
P-immune sets with holes lack self-reducibility properties.
Theoretical Computer Science, 302(1-3):457-466, 2003.

52
L. Hemaspaandra, H. Hempel, and A. Nickelsen.
Algebraic properties for selector functions.
SIAM Journal on Computing, 33(6):1309-1337, 2004.

53
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.

54
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.

55
L. Hemaspaandra, C. Homan, and S. Kosub.
Cluster computing and the power of edge recognition.
Information and Computation, 205(8):1274-1293, 2007.

56
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.

57
L. Hemaspaandra, S. Jain, and N. Vereshchagin.
Banishing robust Turing completeness.
International Journal of Foundations of Computer Science, 4(3):245-265, 1993.

58
L. Hemaspaandra and Z. Jiang.
Logspace reducibility: Models and equivalences.
International Journal of Foundations of Computer Science, 8(1):95-108, 1997.

59
L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.
Polynomial-time multi-selectivity.
Journal of Universal Computer Science, 3(3):197-229, 1997.

60
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.

61
L. Hemaspaandra and M. Ogihara.
The Complexity Theory Companion.
Springer-Verlag, 2002.

62
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.

63
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.

64
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 http://www.jea.acm.org/1998/HemaspaandraPower, 16pp.

65
L. Hemaspaandra, A. Ramachandran, and M. Zimand.
Worlds to die for.
SIGACT News, 26(4):5-15, 1995.

66
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.
To appear.

67
L. Hemaspaandra, J. Rothe, and G. Wechsung.
Easy sets and hard certificate schemes.
Acta Informatica, 34(11):859-879, 1997.

68
L. Hemaspaandra and A. Selman, editors.
Complexity Theory Retrospective II.
Springer-Verlag, 1997.

69
L. Hemaspaandra and M. Thakur.
Lower bounds and the hardness of counting properties.
Theoretical Computer Science, 326(1-3):1-28, 2004.

70
L. Hemaspaandra and M. Thakur.
Query-monotonic Turing reductions.
Theoretical Computer Science, 383(2-3):153-186, 2007.

71
L. Hemaspaandra and L. Torenvliet.
Theory of Semi-Feasible Algorithms.
Springer-Verlag, 2003.

72
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.

73
L. Hemaspaandra and M. Zimand.
Strong self-reducibility precludes strong immunity.
Mathematical Systems Theory, 29(5):535-548, 1996.

74
C. Homan and L. Hemaspaandra.
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners.
Journal of Heuristics.
To appear.

75
D. Kratsch and L. Hemaspaandra.
On the complexity of graph reconstruction.
Mathematical Systems Theory, 27(3):257-273, 1994.

76
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.

77
I. Tomescu and M. Zimand.
Optimal spanning hypertrees.
Discrete Applied Mathematics, 54:67-76, 1994.

78
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.

79
M. Zimand.
If not empty, NP-P is topologically large.
Theoretical Computer Science, 119:293-310, 1993.

80
M. Zimand.
On the topological size of p-m-complete degrees.
Theoretical Computer Science, 147(2):137-147, 1995.

81
M. Zimand.
Existential Theorems in Computational Complexity Theory: Size and Robustness.
PhD thesis, Department of Computer Science, University of Rochester, Rochester, NY, 1996.
UR Technical Report TR-632.

82
M. Zimand.
Large sets in AC$^0$ have many strings with low Kolmogorov complexity.
Information Processing Letters, 62(3):165-170, 1997.

83
M. Zimand.
On the size of classes with weak membership properties.
Theoretical Computer Science, 209(1-2):225-235, 1998.

84
M. Zimand.
Weighted NP optimization problems: Logical definability and approximation properties.
SIAM Journal on Computing, 28(1):36-56, 1999.

85
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. AAAI Press, July 2008.
To appear.
$\begin{tabular}{l}
{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\hline
\end{tabular}$

(Last modified: June 5, 2008.)


Lane A. Hemaspaandra