Computational Complexity

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

Note: Please also see the web pages of my wonderful colleague, Prof. Kaave Hosseini.

Project Description

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.
Structure in Complexity Theory: Central to complexity are the properties and structure of classes and their sets, and various strengths of relations between sets. Among the many important properties to study are closure properties, completeness, enumerability, immunity, information content, isomorphism, self-reducibility, and semi-feasibility.
The 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.

References

1: This is a list of selected papers, from or related to this project, by University of Rochester authors. Links to essentially all Lane's conference and journal papers (and also his arXiv.org technical reports) can be found via the pointers from the related entries within Lane's entry at the DBLP project. Additionally, here is a link to Lane's complete publication list (note: that list does not itself have links to papers).
2: J. Abascal, L. Hemaspaandra, S. Maimon, and D. Rubery.
Closure and nonclosure properties of the compressible and rankable sets.
In Proceedings of the 13th International Conference on Language and Automata Theory and Applications, pages 177–189. Springer-Verlag Lecture Notes in Computer Science #11417, March 2019.
3: J. Abascal, L. Hemaspaandra, S. Maimon, and D. Rubery.
Closure and nonclosure properties of the classes of compressible and rankable sets.
Journal of Computer and System Sciences, 120:162–176, 2021.
4: E. Allender and L. Hemachandra.
Lower bounds for the low hierarchy.
Journal of the ACM, 39(1):234–251, 1992.
5: 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.
6: 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.
7: 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.
8: A. Beygelzimer and M. Ogihara.
The (non)enumerability of the determinant and the rank.
Theory of Computing Systems, 36(4):359–374, 2003.
9: A. Beygelzimer and M. Ogihara.
The enumerability of P collapses P to NC.
Theoretical Computer Science, 345(2–3):248–259, 2005.
10: 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.
11: F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra.
Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates.
Journal of Artificial Intelligence Research, 53:439–496, 2015.
12: 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.
13: G. Buntrock, L. Hemachandra, and D. Siefkes.
Using inductive counting to simulate nondeterministic computation.
Information and Computation, 102(1):102–117, 1993.
14: J.-Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
Competing provers yield improved Karp–Lipton collapse results.
Information and Computation, 198(1):1–23, 2005.
15: J.-Y. Cai, L. Hemachandra, and J. Vyskoč.
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.
16: J.-Y. Cai, L. Hemaspaandra, and G. Wechsung.
Robust reductions.
Theory of Computing Systems, 32(6):625–647, 1999.
17: C. Calude and G. Istrate.
Determining and stationary sets for some classes of partial recursive functions.
Theoretical Computer Science, 82:151–155, 1991.
18: 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.
19: C. Calude, H. Jürgensen, and M. Zimand.
Is independence an exception?
Applied Mathematics and Computation, 66:63–76, 1994.
20: C. Calude and M. Zimand.
Effective category and measure in abstract complexity theory.
Theoretical Computer Science, 154(2):307–327, 1996.
21: I. Caragiannis, E. Hemaspaandra, and L. Hemaspaandra.
Dodgson's Rule and Young's Rule.
In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, pages 103–126. Cambridge University Press, 2016.
22: B. Carleton, M. Chavrimootoo, L. Hemaspaandra, D. Narváez, C. Taliancich, and H. Welles.
Search versus search for collapsing electoral control types (extended abstract).
In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, May–June 2023.
to appear.
23: B. Carleton, M. Chavrimootoo, L. Hemaspaandra, D. Narváez, C. Taliancich, and H. Welles.
Separating and collapsing electoral control types.
In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, May–June 2023.
to appear.
24: 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.
25: 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.
26: G. Erdélyi, E. Hemaspaandra, and L. Hemaspaandra.
Bribery and voter control under voting-rule uncertainty.
In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, pages 61–68. International Foundation for Autonomous Agents and Multiagent Systems, May 2014.
27: G. Erdélyi, E. Hemaspaandra, and L. Hemaspaandra.
More natural models of electoral control by partition.
In Proceedings of the 4th International Conference on Algorithmic Decision Theory, pages 396–413. Springer-Verlag Lecture Notes in Artificial Intelligence #9346, September 2015.
28: 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.
29: 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.
30: 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.
31: 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.
32: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
How hard is bribery in elections?
Journal of Artificial Intelligence Research, 35:485–532, 2009.
33: 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, July 2009.
34: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Using complexity to protect elections.
Communications of the ACM, 53(11):74–82, 2010.
35: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
Journal of Artificial Intelligence Research, 40:305–351, 2011.
36: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Weighted electoral control.
In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pages 367–374. International Foundation for Autonomous Agents and Multiagent Systems, May 2013.
37: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked electorates.
Artificial Intelligence, 207:69–99, 2014.
38: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked electorates.
In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 4178–4182. AAAI Press, July/August 2015.
39: P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Weighted electoral control.
Journal of Artificial Intelligence Research, 52:507–542, 2015.
40: 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.
41: 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.
42: 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.
43: 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.
44: 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.
45: 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.
46: P. Faliszewski and L. Hemaspaandra.
Open questions in the theory of semifeasible computation.
SIGACT News, 37(1):47–65, 2006.
47: P. Faliszewski and L. Hemaspaandra.
The consequences of eliminating NP solutions.
Computer Science Review, 2(1):40–54, 2008.
48: P. Faliszewski and L. Hemaspaandra.
The complexity of power-index comparison.
Theoretical Computer Science, 410(1):101–107, 2009.
49: P. Faliszewski and M. Ogihara.
On the autoreducibility of functions.
Theory of Computing Systems, 46(2):222–245, 2010.
50: Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Control in the presence of manipulators: Cooperative and competitive cases.
In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pages 113–119. AAAI Press, August 2013.
51: Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Manipulation complexity of same-system runoff elections.
Annals of Mathematics and Artificial Intelligence, 77(3–4):159–189, 2016.
52: Z. Fitzsimmons, E. Hemaspaandra, and L. Hemaspaandra.
Control in the presence of manipulators: Cooperative and competitive cases.
Autonomous Agents and Multi-Agent Systems, 34(2, Article 52):1–32, 2020.
53: W. Gasarch, L. Hemachandra, and A. Hoene.
On checking versus evaluation of multiple queries.
Information and Computation, 105(1):72–93, 1993.
54: C. Glaßer and L. Hemaspaandra.
A moment of perfect clarity I: The parallel census technique.
SIGACT News, 31(3):37–42, 2000.
55: 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.
56: T. Gvozdeva, L. Hemaspaandra, and A. Slinko.
Three hierarchies of simple games parameterized by “resource” parameters.
International Journal of Game Theory, 42(1):1–17, 2013.
57: Y. Han, L. Hemaspaandra, and T. Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59–78, 1997.
58: J. Hartmanis and L. Hemachandra.
Robust machines accept easy sets.
Theoretical Computer Science, 74(2):217–226, 1990.
59: 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.
60: 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.
61: L. Hemachandra and A. Hoene.
Collapsing degrees via strong computation.
Journal of Computer and System Sciences, 46(3):363–380, 1993.
62: L. Hemachandra, A. Hoene, D. Siefkes, and P. Young.
On sets polynomially enumerable by iteration.
Theoretical Computer Science, 80(2):203–226, 1991.
63: 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.
64: L. Hemachandra and G. Wechsung.
Kolmogorov characterizations of complexity classes.
Theoretical Computer Science, 83:313–322, 1991.
65: E. Hemaspaandra and L. Hemaspaandra.
Dichotomy for voting systems.
Journal of Computer and System Sciences, 73(1):73–83, 2007.
66: E. Hemaspaandra and L. Hemaspaandra.
Credimus.
In J.-F. Laslier, H. Moulin, M. Sanver, and W. Zwicker, editors, The Future of Economic Design: The Continuing Development of a Field as Envisioned by Its Researchers, pages 141–152. Springer, 2019.
67: E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
All superlinear inverse schemes are coNP-hard.
Theoretical Computer Science, 345(2–3):345–358, 2005.
68: E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
In Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science, pages 377–388. Leibniz International Proceedings in Informatics (LIPIcs) #20, February/March 2013.
69: E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
ACM Transactions on Computation Theory, 12(#1, Article 3):1–42, 2020.
70: E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R. Tripathi.
Complexity results in graph reconstruction.
Discrete Applied Mathematics, 155(2):103–118, 2007.
71: 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.
72: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Raising NP lower bounds to parallel NP lower bounds.
SIGACT News, 28(2):2–13, 1997.
73: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artificial Intelligence, 171(5–6):255–285, 2007.
74: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Hybrid elections broaden complexity-theoretic resistance to control.
Mathematical Logic Quarterly, 55(4):397–424, 2009.
75: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Controlling candidate-sequential elections.
In Proceedings of the 20th European Conference on Artificial Intelligence, pages 905–906. IOS Press, August 2012.
76: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Online voter control in sequential elections.
In Proceedings of the 20th European Conference on Artificial Intelligence, pages 396–401. IOS Press, August 2012.
77: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online manipulation of sequential elections.
Journal of Computer and System Sciences, 80(4):697–710, 2014.
78: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of manipulative actions in single-peaked societies.
In J. Rothe, editor, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, pages 327–360. Springer, 2016.
79: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of controlling candidate-sequential elections.
Theoretical Computer Science, 678:14–21, 2017.
80: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online voter control in sequential elections.
Autonomous Agents and Multi-Agent Systems, 31(5):1055–1076, 2017.
81: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online bribery in sequential elections.
In Proceedings of the 17th Conference on Theoretical Aspects of Rationality and Knowledge, pages 233–251. Electronic Proceedings in Theoretical Computer Science #297, July 2019.
82: E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
The complexity of online bribery in sequential elections.
Journal of Computer and System Sciences, 127:66–90, 2022.
83: E. Hemaspaandra, L. Hemaspaandra, and H. Schnoor.
A control dichotomy for pure scoring rules.
In Proceedings of the 28th AAAI Conference on Artificial Intelligence, pages 712–720. AAAI Press, July 2014.
84: E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph reconstruction.
In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, pages 51:1–51:14. Leibniz International Proceedings in Informatics (LIPIcs) #117, August 2018.
85: E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph reconstruction.
Computational Complexity, 29(2, Article 7):1–49, 2020.
86: E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
Theoretical Computer Science, 411(4–5):783–798, 2010.
87: 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.
88: L. Hemaspaandra.
Lowness: A yardstick for NPP.
SIGACT News, 24(2):10–14, 1993.
89: L. Hemaspaandra.
The not-ready-for-prime-time conjectures.
SIGACT News, 25(2):5–10, 1994.
90: L. Hemaspaandra.
A note on nonuniform versus uniform ACC ${}^k$ circuits for NE.
Technical Report TR-964, Department of Computer Science, University of Rochester, Rochester, NY, December 2010.
91: L. Hemaspaandra.
Beautiful structures: An appreciation of the contributions of Alan Selman.
SIGACT News, 45(3):54–70, 2014.
92: L. Hemaspaandra.
Complexity classes.
In K. Rosen, editor, Handbook of Discrete and Combinatorial Mathematics, pages 1308–1314. CRC Press, 2nd edition, 2018.
93: L. Hemaspaandra.
Computational social choice and computational complexity: BFFs?
In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 7971–7977. AAAI Press, February 2018.
94: L. Hemaspaandra.
That most important intersection.
In H.-J. Böckenhauer, D. Komm, and W. Unger, editors, Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of his 60th Birthday, pages 568–589. Springer, 2018.
95: L. Hemaspaandra.
The power of self-reducibility: Selectivity, information, and approximation.
In D.-Z. Du and J. Wang, editors, Complexity and Approximation, pages 19–47. Springer, 2020.
96: L. Hemaspaandra.
Teaching models, computability, and complexity in time of covid-19.
SIGACT News, 51(3):55–58, 2020.
97: L. Hemaspaandra.
Thoughts on alan selman (1941–2021).
Bulletin of the EATCS, 133:15–20, 2021.
98: L. Hemaspaandra.
Juris Hartmanis (1928–2022): Understanding time, space, and human creativity.
SIGACT News, 53(3):42–45, 2022.
99: L. Hemaspaandra.
Juris Hartmanis and two golden rules.
SIGACT News, 53(4):35–40, 2022.
100: L. Hemaspaandra and H. Hempel.
P-immune sets with holes lack self-reducibility properties.
Theoretical Computer Science, 302(1–3):457–466, 2003.
101: L. Hemaspaandra, H. Hempel, and A. Nickelsen.
Algebraic properties for selector functions.
SIAM Journal on Computing, 33(6):1309–1337, 2004.
102: 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.
103: 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.
104: L. Hemaspaandra, C. Homan, and S. Kosub.
Cluster computing and the power of edge recognition.
Information and Computation, 205(8):1274–1293, 2007.
105: 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.
106: L. Hemaspaandra, S. Jain, and N. Vereshchagin.
Banishing robust Turing completeness.
International Journal of Foundations of Computer Science, 4(3):245–265, 1993.
107: L. Hemaspaandra and Z. Jiang.
Logspace reducibility: Models and equivalences.
International Journal of Foundations of Computer Science, 8(1):95–108, 1997.
108: L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.
Polynomial-time multi-selectivity.
Journal of Universal Computer Science, 3(3):197–229, 1997.
109: L. Hemaspaandra, M. Juvekar, A. Nadjimzadah, and P. Phillips.
Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting.
In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, pages 57:1–57:15. Leibniz International Proceedings in Informatics (LIPIcs) #241, August 2022.
110: L. Hemaspaandra, R. Lavaee, and C. Menton.
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.
In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pages 1345–1346. International Foundation for Autonomous Agents and Multiagent Systems, May 2013.
111: L. Hemaspaandra, R. Lavaee, and C. Menton.
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.
Annals of Mathematics and Artificial Intelligence, 77(3–4):191–223, 2016.
112: 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.
113: L. Hemaspaandra and D. Narváez.
The opacity of backbones.
In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 3900–3906. AAAI Press, February 2017.
114: L. Hemaspaandra and D. Narváez.
Existence versus exploitation: The opacity of backbones and backdoors under a weak assumption.
In Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science, pages 247–259. Springer-Verlag Lecture Notes in Computer Science #11376, January 2019.
115: L. Hemaspaandra and D. Narváez.
Existence versus exploitation: The opacity of backdoors and backbones.
Progress in Artificial Intelligence, 10(3):297–308, 2021.
116: L. Hemaspaandra and D. Narváez.
The opacity of backbones.
Information and Computation, 281(Article 104772):1–10, 2021.
117: L. Hemaspaandra and M. Ogihara.
The Complexity Theory Companion.
Springer-Verlag, 2002.
118: 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.
119: 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.
120: 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.
121: L. Hemaspaandra, A. Ramachandran, and M. Zimand.
Worlds to die for.
SIGACT News, 26(4):5–15, 1995.
122: 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.
123: L. Hemaspaandra, J. Rothe, and G. Wechsung.
Easy sets and hard certificate schemes.
Acta Informatica, 34(11):859–879, 1997.
124: L. Hemaspaandra and D. Rubery.
Recursion-theoretic ranking and compression.
Journal of Computer and System Sciences, 101:31–41, 2019.
125: L. Hemaspaandra and A. Selman, editors.
Complexity Theory Retrospective II.
Springer-Verlag, 1997.
126: L. Hemaspaandra and H. Spakowski.
Team diagonalization.
SIGACT News, 49(3):51–61, 2018.
127: L. Hemaspaandra and M. Thakur.
Lower bounds and the hardness of counting properties.
Theoretical Computer Science, 326(1–3):1–28, 2004.
128: L. Hemaspaandra and M. Thakur.
Query-monotonic Turing reductions.
Theoretical Computer Science, 383(2–3):153–186, 2007.
129: L. Hemaspaandra and L. Torenvliet.
Theory of Semi-Feasible Algorithms.
Springer-Verlag, 2003.
130: 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.
131: L. Hemaspaandra and R. Williams.
An atypical survey of typical-case heuristic algorithms.
SIGACT News, 43(4):71–89, 2012.
132: L. Hemaspaandra and M. Zimand.
Strong self-reducibility precludes strong immunity.
Mathematical Systems Theory, 29(5):535–548, 1996.
133: 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.
134: D. Kratsch and L. Hemaspaandra.
On the complexity of graph reconstruction.
Mathematical Systems Theory, 27(3):257–273, 1994.
135: C. Menton.
Normalized range voting broadly resists control.
Theory of Computing Systems, 53(4):507–531, 2013.
136: 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.
137: I. Tomescu and M. Zimand.
Optimal spanning hypertrees.
Discrete Applied Mathematics, 54:67–76, 1994.
138: 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.
139: M. Zimand.
If not empty, NP-P is topologically large.
Theoretical Computer Science, 119:293–310, 1993.
140: M. Zimand.
On the topological size of p-m-complete degrees.
Theoretical Computer Science, 147(2):137–147, 1995.
141: 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.
142: M. Zimand.
Large sets in AC have many strings with low Kolmogorov complexity.
Information Processing Letters, 62(3):165–170, 1997.
143: M. Zimand.
On the size of classes with weak membership properties.
Theoretical Computer Science, 209(1–2):225–235, 1998.
144: M. Zimand.
Weighted NP optimization problems: Logical definability and approximation properties.
SIAM Journal on Computing, 28(1):36–56, 1999.
145: 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.

$\begin{tabular}{l} {}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ \hline \end{tabular}$

(Last modified: February 16, 2023.)

Lane A. Hemaspaandra