Edith Hemaspaandra

ECAI Conference 2025 Conference Paper

On the Parallelizability of Approval-Based Committee Rules

• Zack Fitzsimmons
• Zohair Raza Hassan
• Edith Hemaspaandra

Approval-Based Committee (ABC) rules are an important tool for choosing a fair set of candidates when given the preferences of a collection of voters. Though finding a winning committee for many ABC rules is NP-hard, natural variations for these rules with polynomial-time algorithms exist. The recently introduced Method of Equal Shares, an important ABC rule with desirable properties, is also computable in polynomial time. However, when working with very large elections, polynomial time is not enough and parallelization may be necessary. We show that computing a winning committee using these polynomial-time ABC rules (including the Method of Equal Shares) is P-hard, thus showing they cannot be parallelized. In contrast, we show that finding a winning committee can be parallelized when the votes are single-peaked or single-crossing for the important ABC rule Chamberlin-Courant.

ECAI Conference 2023 Conference Paper

Using Weighted Matching to Solve 2-Approval/Veto Control and Bribery

• Zack Fitzsimmons
• Edith Hemaspaandra

Determining the complexity of election attack problems is a major research direction in the computational study of voting problems. The paper “Towards completing the puzzle: complexity of control by replacing, adding, and deleting candidates or voters” by Erdélyi et al. (JAAMAS 2021) provides a comprehensive study of the complexity of control problems. The sole open problem is constructive control by replacing voters for 2-Approval. We show that this case is in P, strengthening the recent RP (randomized polynomial-time) upper bound due to Fitzsimmons and Hemaspaandra (IJCAI 2022). We show this by transforming 2-Approval CCRV to weighted matching. We also use this approach to show that priced bribery for 2-Veto elections is in P. With this result, and the accompanying (unsurprising) result that priced bribery for 3-Veto elections is NP-complete, this settles the complexity for k-Approval and k-Veto standard control and bribery cases.

IJCAI Conference 2022 Conference Paper

Insight into Voting Problem Complexity Using Randomized Classes

• Zack Fitzsimmons
• Edith Hemaspaandra

The first step in classifying the complexity of an NP problem is typically showing the problem in P or NP-complete. This has been a successful first step for many problems, including voting problems. However, in this paper we show that this may not always be the best first step. We consider the problem of constructive control by replacing voters (CCRV) introduced by Loreggia et al. [2015, https: //dl. acm. org/doi/10. 5555/2772879. 2773411] for the scoring rule First-Last, which is defined by (1, 0, .. ., 0, -1). We show that this problem is equivalent to Exact Perfect Bipartite Matching, and so CCRV for First-Last can be determined in random polynomial time. So on the one hand, if CCRV for First-Last is NP-complete then RP = NP, which is extremely unlikely. On the other hand, showing that CCRV for First-Last is in P would also show that Exact Perfect Bipartite Matching is in P, which would solve a well-studied 40-year-old open problem. Considering RP as an option for classifying problems can also help classify problems that until now had escaped classification. For example, the sole open problem in the comprehensive table from Erdélyi et al. [2021, https: //doi. org/10. 1007/s10458-021-09523-9] is CCRV for 2-Approval. We show that this problem is in RP, and thus easy since it is widely assumed that P = RP.

IJCAI Conference 2021 Conference Paper

Kemeny Consensus Complexity

• Zack Fitzsimmons
• Edith Hemaspaandra

The computational study of election problems generally focuses on questions related to the winner or set of winners of an election. But social preference functions such as Kemeny rule output a full ranking of the candidates (a consensus). We study the complexity of consensus-related questions, with a particular focus on Kemeny and its qualitative version Slater. The simplest of these questions is the problem of determining whether a ranking is a consensus, and we show that this problem is coNP-complete. We also study the natural question of the complexity of manipulative actions that have a specific consensus as a goal. Though determining whether a ranking is a Kemeny consensus is hard, the optimal action for manipulators is to simply vote their desired consensus. We provide evidence that this simplicity is caused by the combination of election system (Kemeny), manipulative action (manipulation), and manipulative goal (consensus). In the process we provide the first completeness results at the second level of the polynomial hierarchy for electoral manipulation and for optimal solution recognition.

JAAMAS Journal 2020 Journal Article

Control in the presence of manipulators: cooperative and competitive cases

• Zack Fitzsimmons
• Edith Hemaspaandra
• Lane A. Hemaspaandra

Abstract Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the “chair” who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet for a Borda-voting case we show that such clashes raise the complexity unless NP = coNP.

JAAMAS Journal 2020 Journal Article

Correction to: Control in the presence of manipulators: cooperative and competitive cases

• Zack Fitzsimmons
• Edith Hemaspaandra
• Lane A. Hemaspaandra

Unfortunately, a post-galley copyediting error altered the contents of cells in the Condorcet Elections columns of the table in Footnote 7.

ECAI Conference 2020 Conference Paper

Election Score Can Be Harder than Winner

• Zack Fitzsimmons
• Edith Hemaspaandra

Voting rules based on scores generally determine the winner by computing the score of each candidate and the winner is the candidate with the best score. It would be natural to expect that computing the winner of an election is at least as hard as computing the score of a candidate. We show that this is not always the case. In particular, we show that for Young elections for dichotomous preferences the winner problem is easy, while determining the score of a candidate is hard. This complexity behavior has not been seen before and is unusual. The easiness of the winner problem for dichotomous Young crucially uses the fact that dichotomous preferences guarantee the transitivity of the majority relation. In addition to dichotomous preferences we also look at single-peaked preferences, the most well-studied domain restriction that guarantees the transitivity of the majority relation. We show that for the three major hard voting rules and their natural variants, dichotomous Young is the only case where winner is easy and score is hard. This also solves an open question from Lackner and Peters (AAAI 2017), by providing a polynomial-time algorithm for Dodgson score for single-peaked electorates.

MFCS Conference 2019 Conference Paper

Finding Optimal Solutions With Neighborly Help

• Elisabet Burjons
• Fabian Frei
• Edith Hemaspaandra
• Dennis Komm
• David Wehner

Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i. e. , locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e. g. , graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e. g. , recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.

JAAMAS Journal 2019 Journal Article

High-multiplicity election problems

• Zack Fitzsimmons
• Edith Hemaspaandra

Abstract The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the list succinctly, as the distinct votes of the electorate and their counts, i. e. , high-multiplicity representation. We consider how this representation affects the complexity of election problems. High-multiplicity representation may be exponentially smaller than standard representation, and so many polynomial-time algorithms for election problems in standard representation become exponential-time. Surprisingly, for polynomial-time election problems, we are often able to either adapt the same approach or provide new algorithms to show that these problems remain polynomial-time in the high-multiplicity case; this is in sharp contrast to the case where each voter has a weight, where the complexity usually increases. In the process we explore the relationship between high-multiplicity scheduling and manipulation of high-multiplicity elections. And we show that for any fixed set of job lengths, high-multiplicity scheduling on uniform parallel machines is in P, which was previously known for only two job lengths. We did not find any natural case where a polynomial-time election problem does not remain in P when moving to high-multiplicity representation. However, we found one natural NP-hard election problem where the complexity does increase, namely winner determination for Kemeny elections.

TARK Conference 2019 Conference Paper

The Complexity of Online Bribery in Sequential Elections (Extended Abstract)

• Edith Hemaspaandra
• Lane A. Hemachandra
• Jörg Rothe

Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all voters' votes. But neither of those assumptions always holds. In many real-world settings, votes come in sequentially, and the briber may have a use-it-or-lose-it moment to decide whether to bribe/alter a given vote, and at the time of making that decision, the briber may not know what votes remaining voters are planning on casting. In this paper, we introduce a model for, and initiate the study of, bribery in such an online, sequential setting. We show that even for election systems whose winner-determination problem is polynomial-time computable, an online, sequential setting may vastly increase the complexity of bribery, in fact jumping the problem up to completeness for high levels of the polynomial hierarchy or even PSPACE. On the other hand, we show that for some natural, important election systems, such a dramatic complexity increase does not occur, and we pinpoint the complexity of their bribery problems in the online, sequential setting.

AAAI Conference 2019 Conference Paper

Very Hard Electoral Control Problems

• Zack Fitzsimmons
• Edith Hemaspaandra
• Alexander Hoover
• David E. Narváez

It is important to understand how the outcome of an election can be modified by an agent with control over the structure of the election. Electoral control has been studied for many election systems, but for all these systems the winner problem is in P, and so control is in NP. There are election systems, such as Kemeny, that have many desirable properties, but whose winner problems are not in NP. Thus for such systems control is not in NP, and in fact we show that it is typically complete for Σp 2 (i. e. , NPNP, the second level of the polynomial hierarchy). This is a very high level of complexity. Approaches that perform quite well for solving NP problems do not necessarily work for Σp 2-complete problems. However, answer set programming is suited to express problems in Σp 2, and we present an encoding for Kemeny control.

AAMAS Conference 2018 Conference Paper

High-Multiplicity Election Problems

• Zack Fitzsimmons
• Edith Hemaspaandra

The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the list succinctly, as the distinct votes of the electorate and their counts, i. e. , high-multiplicity representation. We consider how this representation affects the complexity of election problems. High-multiplicity representation may be exponentially smaller than standard representation, and so many polynomial-time algorithms for election problems in standard representation become exponential-time. Surprisingly, for polynomial-time election problems, we are often able to either adapt the same approach or provide new algorithms to show that these problems remain polynomial-time in the highmultiplicity case; this is in sharp contrast to the case where each voter has a weight, where the complexity usually increases. In the process we explore the relationship between high-multiplicity scheduling and manipulation of high-multiplicity elections. And we show that for any fixed set of job lengths, high-multiplicity scheduling on uniform parallel machines is in P, which was previously known for only two job lengths. We did not find any natural case where a polynomial-time election problem does not remain in P when moving to high-multiplicity representation. However, we found one natural NP-hard election problem where the complexity does increase, namely winner determination for Kemeny elections.

MFCS Conference 2018 Conference Paper

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction

• Edith Hemaspaandra
• Lane A. Hemachandra
• Holger Spakowski
• Osamu Watanabe 0001

We show that the counting class LWPP [S. Fenner et al. , 1994] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i. e. , PP^{Legitimate Deck} = PP) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning, and Torán [J. Köbler et al. , 1992] that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our main LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection- and acceptance- gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the #P-based analog of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does.

TCS Journal 2017 Journal Article

The complexity of controlling candidate-sequential elections

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• Jörg Rothe

AAAI Conference 2017 Short Paper

The Complexity of Succinct Elections

• Zack Fitzsimmons
• Edith Hemaspaandra

The computational study of elections generally assumes that the preferences of the electorate come in as a list of votes. Depending on the context, it may be much more natural to represent the preferences of the electorate succinctly, as the distinct votes and their counts. Though the succinct representation may be exponentially smaller than the nonsuccinct, we find only one natural case where the complexity increases, in sharp contrast to the case where each voter has a weight, where the complexity usually increases.

ECAI Conference 2016 Conference Paper

Dichotomy for Pure Scoring Rules Under Manipulative Electoral Actions

• Edith Hemaspaandra
• Henning Schnoor

Scoring systems are an extremely important class of election systems. We study the complexity of manipulation, constructive control by deleting voters (CCDV), and bribery for scoring systems. For manipulation, we show that for all scoring rules with a constant number of different coefficients, manipulation is in P. And we conjecture that there is no dichotomy theorem.

JAAMAS Journal 2016 Journal Article

The complexity of online voter control in sequential elections

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• Jörg Rothe

Abstract Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters’ preferences and that all votes are cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is \(\mathrm {PSPACE}\) -complete, even if there are only two candidates. In addition, we obtain (by a new characterization of coNP in terms of weight-bounded alternating Turing machines) completeness for \({\mathrm {coNP}}\) in the deleting/adding cases with a bounded deletion/addition limit, and we obtain completeness for \({\mathrm {NP}}\) in the partition cases with an additional restriction. We also show that for plurality, online control by deleting or adding voters is in \({\mathrm {P}}\), and for partitioning voters is \({\mathrm {coNP}}\) -hard.

JAIR Journal 2015 Journal Article

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

• Felix Brandt
• Markus Brill
• Edith Hemaspaandra
• Lane A. Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates---single-peaked preferences---those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems---including those for Kemeny and Llull elections---fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Theta-two-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

IJCAI Conference 2015 Conference Paper

The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract)

• Piotr Faliszewski
• Edith Hemaspaandra
• Lane A. Hemaspaandra

Many electoral control and manipulation problems—which we will refer to in general as “manipulative actions” problems—are NP-hard in the general case. Many of these problems fall into polynomial time if the electorate is singlepeaked, i. e. , is polarized along some axis/issue. However, real-world electorates are not truly single-peaked—for example, there may be some maverick voters—and to take this into account, we study the complexity of manipulative-action algorithms for the case of nearly single-peaked electorates.

JAIR Journal 2015 Journal Article

Weighted Electoral Control

• Piotr Faliszewski
• Edith Hemaspaandra
• Lane A. Hemaspaandra

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.

AAAI Conference 2014 Conference Paper

A Control Dichotomy for Pure Scoring Rules

• Edith Hemaspaandra
• Lane Hemaspaandra
• Henning Schnoor

Scoring systems are an extremely important class of election systems. A length-m (so-called) scoring vector applies only to m-candidate elections. To handle general elections, one must use a family of vectors, one per length. The most elegant approach to making sure such families are “family-like” is the recently introduced notion of (polynomial-time uniform) pure scoring rules (Betzler and Dorn 2010), where each scoring vector is obtained from its precursor by adding one new coefficient. We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k ≤ 3, k-veto with k ≤ 2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a “hybrid” of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models for defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be “w. l. o. g. ” in fact do lose generality.

AIJ Journal 2014 Journal Article

The complexity of manipulative attacks in nearly single-peaked electorates

• Piotr Faliszewski
• Edith Hemaspaandra
• Lane A. Hemaspaandra

IJCAI Conference 2013 Conference Paper

Control in the Presence of Manipulators: Cooperative and Competitive Cases

• Zack Fitzsimmons
• Edith Hemaspaandra
• Lane A. Hemaspaandra

Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the “chair” who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet we for a Borda-voting case show that such clashes raise the complexity unless NP = coNP.

TARK Conference 2013 Conference Paper

The Complexity of Online Manipulation of Sequential Elections

• Edith Hemaspaandra
• Lane A. Hemachandra
• Jörg Rothe

Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential, and manipulators may know the already cast votes but may not know the future votes. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that in this setting manipulation can be extremely complex even for election systems with simple winner problems. Yet we also show that for some of the most important election systems such manipulation is simple in certain settings. This suggests that when using sequential voting, one should pay great attention to the details of the setting in choosing one’s voting rule. Among the highlights of our classifications are: We show that, depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonuniquewinner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first PNP[1] completeness and PNP -completeness results in the field of computational social choice, in particular proving such completeness for, respectively, the complexity of 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections.

ECAI Conference 2012 Conference Paper

Controlling Candidate-Sequential Elections

• Edith Hemaspaandra
• Lane A. Hemachandra
• Jörg Rothe

All previous work on "candidate-control" manipulation of elections has been in the model of full-information, simultaneous voting. This is a problem, since in quite a few real-world settings- from TV singing/dancing talent shows to university faculty-hiring processes-candidates are introduced, and appraised by the voters, in sequence. We provide a natural model for sequential candidate evaluation, a framework for evaluating the computational complexity of controlling the outcome within that framework, and some initial results on the range such complexity can take on. We hope our work will lead to further examination of temporally involved candidate control.

ECAI Conference 2012 Conference Paper

Online Voter Control in Sequential Elections

• Edith Hemaspaandra
• Lane A. Hemachandra
• Jörg Rothe

Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters' preferences and that all votes are cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is PSPACE-complete, even if there are only two candidates. In addition, we obtain completeness for coNP in the deleting/adding cases with a bounded deletion/addition limit, and for NP in the partition cases with only one candidate. Finally, we show that for plurality, online control by deleting or adding voters is in P, and for partitioning voters is coNP-hard.

ECAI Conference 2012 Conference Paper

Weighted Manipulation for Four-Candidate Llull Is Easy

• Piotr Faliszewski
• Edith Hemaspaandra
• Henning Schnoor

Our main contribution is a surprising polynomial-time algorithm for weighed coalitional manipulation of four-candidate Copeland (also known as Llull) elections. On the technical side, our algorithm relies on a polynomial-time routine that solves a variant of the partition problem. We also show that there is a pseudopolynomial-time algorithm for weighted coalitional manipulation with a fixed number of candidates under any anonymous rule with a polynomial-time winner-determination procedure.

MFCS Conference 2011 Conference Paper

A Universally Defined Undecidable Unimodal Logic

• Edith Hemaspaandra
• Henning Schnoor

Abstract Modal logics are widely used in computer science. The complexity of their satisfiability problems has been an active field of research since the 1970s. We prove that even very “simple” modal logics can be undecidable: We show that there is an undecidable unimodal logic that can be obtained by restricting the allowed models with an equality-free first-order formula in which only universal quantifiers appear.

IJCAI Conference 2011 Conference Paper

Minimization for Generalized Boolean Formulas

• Edith Hemaspaandra
• Henning Schnoor

The minimization problem for propositional formulas is an important optimization problem in the second level of the polynomial hierarchy. In general, the problem is Sigma-2-complete under Turing reductions, but restricted versions are tractable. We study the complexity of minimization for formulas in two established frameworks for restricted propositional logic: The Post framework allowing arbitrarily nested formulas over a set of Boolean connectors, and the constraint setting, allowing generalizations of CNF formulas. In the Post case, we obtain a dichotomy result: Minimization is solvable in polynomial time or coNP-hard. This result also applies to Boolean circuits. For CNF formulas, we obtain new minimization algorithms for a large class of formulas, and give strong evidence that we have covered all polynomial-time cases.

TARK Conference 2011 Conference Paper

The complexity of manipulative attacks in nearly single-peaked electorates

• Piotr Faliszewski
• Edith Hemaspaandra
• Lane A. Hemachandra

Many electoral bribery, control, and manipulation problems (which we will refer to in general as “manipulative actions” problems) are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked (i. e. , is polarized along some axis/issue). However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend to merely be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates, for various notions of nearness and various election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to NP-hardness, but we also provide many instances where a reasonable number of mavericks can be tolerated without increasing the manipulative-action complexity.

AAAI Conference 2010 Conference Paper

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

• Felix Brandt
• Markus Brill
• Edith Hemaspaandra
• Lane Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. This paper shows that for voters who follow the most central political-science model of electorates—single-peaked preferences—those protections vanish. By using singlepeaked preferences to simplify combinatorial covering challenges, we show that NP-hard bribery problems—including those for Kemeny and Llull elections—fall to polynomial time. By using single-peaked preferences to simplify combinatorial partition challenges, we show that NP-hard partitionof-voters problems fall to polynomial time. We furthermore show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θp 2-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

AAMAS Conference 2010 Conference Paper

Manipulation of Copeland Elections

• Piotr Faliszewski
• Edith Hemaspaandra
• Henning Schnoor

We resolve an important open problem regarding the complexity of (constructive) unweighted coalitional manipulation problem in Copeland$^\alpha$ elections, that is, the complexity of Copeland$^\alpha$-manipulation for alpha in {0, 1}. Copeland$^\alpha$, $0 \le \alpha \le 1$, is an election system where for each pair of candidates we check which one is preferred by more voters (i. e. , we conduct a head-to-head majority contest) and we give one point to this candidate and zero to the other. However, in case of a tie both candidates receive alpha points. In the end, candidates with most points win. It is known that Copeland$^\alpha$-manipulation is NP-complete for all rational alpha's in [0, 1]-{0. 5} (i. e. , for all the reasonable cases except the three truely interesting ones). In this paper we show that the problem remains NP-complete for $\alpha \in {0, 1}$. In addition, we resolve the complexity of Copeland$^\alpha$-manipulation for each rational $\alpha \in [0, 1]$ for the case of irrational voters.

TCS Journal 2010 Journal Article

On the complexity of kings

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• Till Tantau
• Osamu Watanabe

IJCAI Conference 2009 Conference Paper

• Piotr Faliszewski
• Edith Hemaspaandra
• Lane A. Hemaspaandra

In 1992, Bartholdi, Tovey, and Trick [1992] opened the study of control attacks on elections—attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i. e. , multimode) attack. We do so to more realistically capture the richness of reallife settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.

TARK Conference 2009 Conference Paper

The shield that never was: societies with single-peaked preferences are more open to manipulation and control

• Piotr Faliszewski
• Edith Hemaspaandra
• Lane A. Hemachandra
• Jörg Rothe

Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-hardness shields, and recently there has been much focus on whether such worst-case hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having singlepeaked preferences, many existing NP-hardness results on manipulation and control evaporate.

AAAI Conference 2008 Conference Paper

Approximability of Manipulating Elections

• Eric Brelsford
• Edith Hemaspaandra

In this paper, we set up a framework to study approximation of manipulation, control, and bribery in elections. We show existence of approximation algorithms (even fully polynomial time approximation schemes) as well as obtain inapproximability results.

AAMAS Conference 2008 Conference Paper

Copeland Voting: Ties Matter

• Piotr Faliszewski
• Edith Hemaspaandra
• Henning Schnoor

We study the complexity of manipulation for a family of election systems derived from Copeland voting via introducing a parameter α that describes how ties in head-to-head contests are valued. We show that the thus obtained problem of manipulation for unweighted Copelandα elections is NP-complete even if the size of the manipulating coalition is limited to two. Our result holds for all rational values of α such that 0 < α < 1 except for α = 1 2. Since it is well known that manipulation via a single voter is easy for Copeland, our result is the first one where an election system originally known to be vulnerable to manipulation via a single voter is shown to be resistant to manipulation via a coalition of a constant number of voters. We also study the complexity of manipulation for Copelandα for the case of a constant number of candidates. We show that here the exact complexity of manipulation often depends closely on the α: Depending on whether we try to make our favorite candidate a winner or a unique winner and whether α is 0, 1 or between these values, the problem of weighted manipulation for Copelandα with three candidates is either in P or is NP-complete. Our results show that ways in which ties are treated in an election system, here Copeland voting, can be crucial to establishing complexity results for this system.

IJCAI Conference 2007 Conference Paper

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• J
• ouml; rg Rothe

Electoral control refers to attempts by an election's organizer ("the chair") to influence the outcome by adding/deleting/partitioning voters or candidates. The groundbreaking work of Bartholdi, Tovey, and Trick on (constructive) control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible. We introduce and study a method of combining two or more candidate-anonymous election schemes in such a way that the combined scheme possesses all the resistances to control (i. e. , all the NP-hardnesses of control) possessed by any of its constituents: It combines their strengths. From this and new resistance constructions, we prove for the first time that there exists an election scheme that is resistant to all twenty standard types of electoral control.

AIJ Journal 2007 Journal Article

Anyone but him: The complexity of precluding an alternative

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• Jörg Rothe

TCS Journal 2005 Journal Article

All superlinear inverse schemes are coNP-hard

• Edith Hemaspaandra
• Lane A. Hemaspaandra
• Harald Hempel

AAAI Conference 2005 Conference Paper

Anyone but Him: The Complexity of Precluding an Alternative

• Edith Hemaspaandra

Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preference aggregation to destructive control. That is, we study the ability of an election’s chair to, through such mechanisms as voter/candidate addition/suppression/partition, ensure that a particular candidate (equivalently, alternative) does not win. And we study the extent to which election systems can make it impossible, or computationally costly (NP-complete), for the chair to execute such control. Among the systems we study—plurality, Condorcet, and approval voting—we find cases where systems immune or computationally resistant to a chair choosing the winner nonetheless are vulnerable to the chair blocking a victory. Beyond that, we see that among our studied systems no one system offers the best protection against destructive control. Rather, the choice of a preference aggregation system will depend closely on which types of control one wishes to be protected against. We also find concrete cases where the complexity of or susceptibility to control varies dramatically based on the choice among natural tie-handling rules. Key words: preferences, computational complexity, multiagent systems.

MFCS Conference 2005 Conference Paper

Isomorphic Implication

• Michael Bauland
• Edith Hemaspaandra

Abstract We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in \({\rm P^{NP}_{||}}\). We show how to extend the NP-hardness and coNP-hardness to \({\rm P^{NP}_{||}}\) -hardness for some cases, and conjecture that this can be done in all cases.

TCS Journal 2005 Journal Article

The complexity of Kemeny elections

• Edith Hemaspaandra
• Holger Spakowski
• Jörg Vogel

MFCS Conference 2004 Conference Paper

All Superlinear Inverse Schemes Are coNP-Hard

• Edith Hemaspaandra
• Lane A. Hemachandra
• Harald Hempel

Abstract How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. As part of our work we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.

MFCS Conference 2004 Conference Paper

Complexity Results in Graph Reconstruction

• Edith Hemaspaandra
• Lane A. Hemachandra
• Stanislaw P. Radziszowski
• Rahul Tripathi

Abstract We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs. We show that the problems are rather closely related for all amounts c of deletion: For all c ≥ 1, GI \(\equiv^{l}_{iso}\) VDC c, GI \(\equiv^{l}_{iso}\) EDC c, GI \(\leq^{l}_{m}\) LVD c, and GI \(\equiv^{p}_{iso}\) LED c. For all c ≥ 1 and k ≥ 2, \({\rm GI} \equiv^{p}_{iso} {k\textnormal{-}\rm VDC}_c\) and \({\rm GI} \equiv^{p}_{iso} {k\textnormal{-}\rm EDC}_c\). For all c ≥ 1 and k ≥ 2, \({\rm GI} \leq^{l}_{m} {k\textnormal{-}\rm LVD}_c\). In particular, for all c ≥ 1, \({\rm GI} \equiv^{p}_{iso} {2\textnormal{-}\rm LVD}_c\). For all c ≥ 1 and k ≥ 2, \({\rm GI} \equiv^{p}_{iso} {k\textnormal{-}\rm LED}_c\). For many of these, even the c = 1 cases were not known. Similar to the definition of reconstruction numbers vrn ∃ ( G ) [10] and ern ∃ ( G ) (see p. 120 of [17]), we introduce two new graph parameters, vrn ∀ ( G ) and ern ∀ ( G ), and give an example of a family { G n } n ≥ 4 of graphs on n vertices for which vrn ∃ ( G n ) < vrn ∀ ( G n ). For every k ≥ 2 and n ≥ 1, we show there exists a collection of k graphs on (2 k − − 1 +1) n + k vertices with 2 n 1-vertex-preimages, i. e. , one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.

CSL Conference 2002 Conference Paper

Equivalence and Isomorphism for Boolean Constraint Satisfaction

• Elmar Böhler
• Edith Hemaspaandra
• Steffen Reith
• Heribert Vollmer

Abstract A Boolean constraint satisfaction instance is a set of constraint applications where the allowed constraints are drawn from a fixed set C of Boolean functions. We consider the problem of determining whether two given constraint satisfaction instances are equivalent and prove a dichotomy theorem by showing that for all finite sets C of constraints, this problem is either polynomial-time solvable or coNP-complete, and we give a simple criterion to determine which case holds. A more general problem addressed in this paper is the isomorphism problem, the problem of determining whether there exists a renaming of the variables that makes two given constraint satisfaction instances equivalent in the above sense. We prove that this problem is coNP-hard if the corresponding equivalence problem is coNP-hard, and polynomial-time many-one reducible to the graph isomorphism problem in all other cases.

MFCS Conference 2000 Invited Paper

Computational Politics: Electoral Systems

• Edith Hemaspaandra
• Lane A. Hemachandra

Abstract This paper discusses three computation-related results in the study of electoral systems: 1. Determining the winner in Lewis Carroll’s 1876 electoral system is complete for parallel access to NP [ 22 ]. 2. For any electoral system that is neutral, consistent, and Condorcet, determining the winner is complete for parallel access to NP [ 21 ]. 3. For each census in US history, a simulated annealing algorithm yields provably fairer (in a mathematically rigorous sense) congressional apportionments than any of the classic algorithms—even the algorithm currently used in the United States [ 24 ].

CSL Conference 2000 Conference Paper

Modal Satisfiability Is in Deterministic Linear Space

• Edith Hemaspaandra

Abstract In recent years, there has been a lot of interest in analyzing the space requirements for modal logics. In this paper, we prove that modal satisfiability is in deterministic linear space. This improves the best previously-known O ( n log n ) bound and it is the first linear space result in this area.

FOCS Conference 1997 Conference Paper

The Minimization Problem for Boolean Formulas

• Edith Hemaspaandra
• Gerd Wechsung

We investigate the computational complexity of the minimization problem for Boolean formulas. Depending on the definition, these problems are trivially in /spl Sigma//sub 2//sup P/ or II/sub 2//sup P/, and these are the best upper bounds known. The only previously known lower bounds are also trivial, and are coNP lower bounds at best, thus leaving quite a large gap between the upper and lower bounds. In this paper, we prove much better lower bounds: hardness for parallel access to NP for those cases in which coNP was the best previously known lower bound, and coNP-hardness for the case in which no lower bound was previously known.

TCS Journal 1994 Journal Article

Quasi-injective reductions

• Edith Hemaspaandra
• Lane A. Hemaspaandra

TARK Conference 1990 Conference Paper

Nexttime is not Necessary

• Edith Hemaspaandra

We investigate the propositional modal logic of knowledge and time for distributed systems. Previous results by Halpern and Vardi [HV89] and Ladner and Reif [LR] illustrate that the validity problems for a number of these logics are highly intractable; in particular they prove a number of II~-completeness results. The logics considered by the above authors contain at least two out of the three temporal logic operators: ~sometimes~, gnexttime~, and auntil~. Although their proofs rely heavily on either the anexttime~ or the ~until~ operator, we show that the completeness results remain valid if we restrict the temporal operators to asometimes~.