Lane A. Hemaspaandra
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Lane A. Hemaspaandra has a total of 136 co-authors. Here are the top co-authors by number of shared publications:
Edith Hemaspaandra
37 shared publications- Mitsunori Ogihara
Frost Institute for Data Science and Computing, University of Miami, Coral Gables, FL
25 shared publications Jörg Rothe
22 shared publicationsHarald Hempel
Institut für Informatik, Friedrich-Schiller-Universität Jena, D-07743 Jena, Germany
13 shared publicationsPiotr Faliszewski
13 shared publicationsGerd Wechsung
12 shared publications
Latest Publications
- 13 November 2026
- Published by Springer Nature
- p. 197-212
Axiomatic Tools for Separating Electoral Control Types, with Applications to Concrete Systems
- 13 November 2026
- Published by Springer Nature
- p. 197-212
Axiomatic Tools for Separating Electoral Control Types, with Applications to Concrete Systems
- Open Access
- 11 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 641-643
Rediscovering Important Algorithms: A Pedagogical Approach to Help Students Better Appreciate Their Problem-Solving Skills
- 11 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 641-643
Open AccessRediscovering Important Algorithms: A Pedagogical Approach to Help Students Better Appreciate Their Problem-Solving Skills
- Open Access
- 3 August 2026
- Published by Springer Nature in Theory of Computing Systems
- Vol. 70 (3) , 44
Search Versus Search for Collapsing Electoral Control Types
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [6]. We say two compatible (i.e., having the same input types) control types that are about the same election system $$\mathcal {E}$$ form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the attempted attacks can be successfully carried out (see the Preliminaries for a more formal definition) [31]. For each of the seven general (i.e., holding for all election systems) electoral control type collapsing pairs found by Hemaspaandra, Hemaspaandra, and Menton [31] and for each of the additional electoral control type collapsing pairs of Carleton et al. [10] for veto and approval (and many other election systems in light of that paper’s Theorems 3.6 and 3.9), both members of the collapsing pair have the same complexity since as sets they are the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [31] and Carleton et al. [10], we prove that the pair’s members’ search-version complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. For the concrete systems plurality, veto, and approval, we completely determine which of their (due to our results) polynomially-related collapsing search-problem pairs are polynomial-time computable and which are NP-hard.- 3 August 2026
- Published by Springer Nature in Theory of Computing Systems
- Vol. 70 (3) , 44
Open AccessSearch Versus Search for Collapsing Electoral Control Types
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [6]. We say two compatible (i.e., having the same input types) control types that are about the same election system $$\mathcal {E}$$ form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the attempted attacks can be successfully carried out (see the Preliminaries for a more formal definition) [31]. For each of the seven general (i.e., holding for all election systems) electoral control type collapsing pairs found by Hemaspaandra, Hemaspaandra, and Menton [31] and for each of the additional electoral control type collapsing pairs of Carleton et al. [10] for veto and approval (and many other election systems in light of that paper’s Theorems 3.6 and 3.9), both members of the collapsing pair have the same complexity since as sets they are the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [31] and Carleton et al. [10], we prove that the pair’s members’ search-version complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. For the concrete systems plurality, veto, and approval, we completely determine which of their (due to our results) polynomially-related collapsing search-problem pairs are polynomial-time computable and which are NP-hard. - Open Access
- 17 February 2026
- Published by Association for Computing Machinery (ACM)
- p. 1333-1334
Conceptual Models for Teaching and Learning Computer Science Theory
- 17 February 2026
- Published by Association for Computing Machinery (ACM)
- p. 1333-1334
Open AccessConceptual Models for Teaching and Learning Computer Science Theory
- 20 June 2025
- Published by Springer Nature
- p. 217-236
Search Versus Search for Collapsing Electoral Control Types
- 20 June 2025
- Published by Springer Nature
- p. 217-236
Search Versus Search for Collapsing Electoral Control Types
- Open Access
- 11 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (4) , 1-26
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that Few P ⊆ ⊕P). In this article, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappiness”) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all \((\mathcal {O}(1) + \log \log n)\) -ambiguity NP sets are in the restricted counting class RC PRIMES .- 11 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (4) , 1-26
Open AccessGaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that Few P ⊆ ⊕P). In this article, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappiness”) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all \((\mathcal {O}(1) + \log \log n)\) -ambiguity NP sets are in the restricted counting class RC PRIMES . - Open Access
- 11 September 2024
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 81, 71-116
Separating and Collapsing Electoral Control Types
Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that perhaps other pairs of control types are identical, and so work still is being needlessly duplicated. We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.
- 11 September 2024
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 81, 71-116
Open AccessSeparating and Collapsing Electoral Control Types
Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that perhaps other pairs of control types are identical, and so work still is being needlessly duplicated. We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.
- 29 June 2024
- Published by Springer Nature
- p. 369-402
The Complexity of Manipulative Actions in Single-Peaked Societies
- 29 June 2024
- Published by Springer Nature
- p. 369-402
The Complexity of Manipulative Actions in Single-Peaked Societies
- Open Access
Search versus Search for Collapsing Electoral Control Types
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [BTT92]. We say two compatible (i.e., having the same input types) control types that are about the same election system E form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the attempted attacks can be successfully carried out. For each of the seven general (i.e., holding for all election systems) electoral control type collapsing pairs found by Hemaspaandra, Hemaspaandra, and Menton [HHM20] and for each of the additional electoral control type collapsing pairs of Carleton et al. [CCH+ 22] for veto and approval (and many other election systems in light of that paper's Theorems 3.6 and 3.9), both members of the collapsing pair have the same complexity since as sets they are the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [HHM20] and Carleton et al. [CCH+ 22], we prove that the pair's members' search-version complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. For the concrete systems plurality, veto, and approval, we completely determine which of their (due to our results) polynomially-related collapsing search-problem pairs are polynomial-time computable and which are NP-hard.
Open AccessSearch versus Search for Collapsing Electoral Control Types
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [BTT92]. We say two compatible (i.e., having the same input types) control types that are about the same election system E form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the attempted attacks can be successfully carried out. For each of the seven general (i.e., holding for all election systems) electoral control type collapsing pairs found by Hemaspaandra, Hemaspaandra, and Menton [HHM20] and for each of the additional electoral control type collapsing pairs of Carleton et al. [CCH+ 22] for veto and approval (and many other election systems in light of that paper's Theorems 3.6 and 3.9), both members of the collapsing pair have the same complexity since as sets they are the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [HHM20] and Carleton et al. [CCH+ 22], we prove that the pair's members' search-version complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. For the concrete systems plurality, veto, and approval, we completely determine which of their (due to our results) polynomially-related collapsing search-problem pairs are polynomial-time computable and which are NP-hard.
- Open Access
Separating and Collapsing Electoral Control Types
[HHM20] discovered, for 7 pairs (C,D) of seemingly distinct standard electoral control types, that C and D are identical: For each input I and each election system, I is a Yes instance of both C and D, or of neither. Surprisingly this had gone undetected, even as the field was score-carding how many std. control types election systems were resistant to; various "different" cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that other pairs of control types are also identical, and so work still is being needlessly duplicated. We determine, for all std. control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. We show that no identical control pairs exist beyond the known 7. We for 3 central election systems determine which control pairs are identical ("collapse") with respect to those systems, and we explore containment/incomparability relationships between control pairs. For approval voting, which has a different "type" for its votes, [HHM20]'s 7 collapses still hold. But we find 14 additional collapses that hold for approval voting but not for some election systems whose votes are linear orderings. We find 1 additional collapse for veto and none for plurality. We prove that each of the 3 election systems mentioned have no collapses other than those inherited from [HHM20] or added here. But we show many new containment relationships that hold between some separating control pairs, and for each separating pair of std. control types classify its separation in terms of containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these 3 important election systems, clarifies the landscape of the 44 std. control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.
Open AccessSeparating and Collapsing Electoral Control Types
[HHM20] discovered, for 7 pairs (C,D) of seemingly distinct standard electoral control types, that C and D are identical: For each input I and each election system, I is a Yes instance of both C and D, or of neither. Surprisingly this had gone undetected, even as the field was score-carding how many std. control types election systems were resistant to; various "different" cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that other pairs of control types are also identical, and so work still is being needlessly duplicated. We determine, for all std. control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. We show that no identical control pairs exist beyond the known 7. We for 3 central election systems determine which control pairs are identical ("collapse") with respect to those systems, and we explore containment/incomparability relationships between control pairs. For approval voting, which has a different "type" for its votes, [HHM20]'s 7 collapses still hold. But we find 14 additional collapses that hold for approval voting but not for some election systems whose votes are linear orderings. We find 1 additional collapse for veto and none for plurality. We prove that each of the 3 election systems mentioned have no collapses other than those inherited from [HHM20] or added here. But we show many new containment relationships that hold between some separating control pairs, and for each separating pair of std. control types classify its separation in terms of containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these 3 important election systems, clarifies the landscape of the 44 std. control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.