Edith Hemaspaandra

Proceedings of the Proceedings Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge, 2019

High-multiplicity election problems.

[BibT_eX]

[DOI]

Auton. Agents Multi Agent Syst., 2019

Finding Optimal Solutions With Neighborly Help.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Very Hard Electoral Control Problems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2017

The complexity of controlling candidate-sequential elections.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Credimus.

[BibT_eX]

[DOI]

CoRR, 2017

The complexity of online voter control in sequential elections.

[BibT_eX]

[DOI]

Auton. Agents Multi Agent Syst., 2017

The Complexity of Succinct Elections.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

Dodgson's Rule and Young's Rule.

[BibT_eX]

[DOI]

Ioannis Caragiannis

Proceedings of the Handbook of Computational Social Choice, 2016

Complexity Dichotomies for Unweighted Scoring Rules.

[BibT_eX]

[DOI]

CoRR, 2016

Manipulation Complexity of Same-System Runoff Elections.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2016

Modeling Single-Peakedness for Votes with Ties.

[BibT_eX]

[DOI]

Proceedings of the STAIRS 2016, 2016

Dichotomy for Pure Scoring Rules Under Manipulative Electoral Actions.

[BibT_eX]

[DOI]

Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

The Complexity of Manipulative Actions in Single-Peaked Societies.

[BibT_eX]

[DOI]

Proceedings of the Economics and Computation, 2016

2015

Weighted Electoral Control.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2015

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

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2015

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Complexity of Manipulative Actions When Voting with Ties.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

More Natural Models of Electoral Control by Partition.

[BibT_eX]

[DOI]

Gábor Erdélyi

Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

2014

The complexity of online manipulation of sequential elections.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

The complexity of manipulative attacks in nearly single-peaked electorates.

[BibT_eX]

[DOI]

Artif. Intell., 2014

Bribery and voter control under voting-rule uncertainty.

[BibT_eX]

[DOI]

Gábor Erdélyi

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2014

A Control Dichotomy for Pure Scoring Rules.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013

X THEN X: Manipulation of Same-System Runoff Elections

[BibT_eX]

[DOI]

CoRR, 2013

A Richer Understanding of the Complexity of Election Systems.

[BibT_eX]

[DOI]

Proceedings of the Fundamental Problems in Computing, 2013

2012

Controlling Candidate-Sequential Elections.

[BibT_eX]

[DOI]

Proceedings of the ECAI 2012, 2012

Online Voter Control in Sequential Elections.

[BibT_eX]

[DOI]

Proceedings of the ECAI 2012, 2012

Weighted Manipulation for Four-Candidate Llull Is Easy.

[BibT_eX]

[DOI]

Proceedings of the ECAI 2012, 2012

2011

Multimode Control Attacks on Elections.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2011

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

[BibT_eX]

[DOI]

Inf. Comput., 2011

A Simplest Undecidable Modal Logic

[BibT_eX]

[DOI]

CoRR, 2011

A Universally Defined Undecidable Unimodal Logic.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Minimization for Generalized Boolean Formulas.

[BibT_eX]

[DOI]

Proceedings of the IJCAI 2011, 2011

2010

On the complexity of kings.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Generalized modal satisfiability.

[BibT_eX]

[DOI]

Ilka Schnoor

J. Comput. Syst. Sci., 2010

Using complexity to protect elections.

[BibT_eX]

[DOI]

Commun. ACM, 2010

Manipulation of copeland elections.

[BibT_eX]

[DOI]

Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010

2009

Isomorphic Implication.

[BibT_eX]

[DOI]

Michael Bauland

Theory Comput. Syst., 2009

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.

[BibT_eX]

[DOI]

Math. Log. Q., 2009

Llull and Copeland Voting Computationally Resist Bribery and Constructive Control.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2009

How Hard Is Bribery in Elections?

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2009

2008

Llull and Copeland Voting Computationally Resist Bribery and Control

[BibT_eX]

[DOI]

CoRR, 2008

On the Complexity of Elementary Modal Logics.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

Copeland voting: ties matter.

[BibT_eX]

[DOI]

Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), 2008

Copeland Voting Fully Resists Constructive Control.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2008

Approximability of Manipulating Elections.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007

Dichotomy for voting systems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

Complexity results in graph reconstruction.

[BibT_eX]

[DOI]

Stanislaw P. Radziszowski

Rahul Tripathi

Discret. Appl. Math., 2007

Anyone but him: The complexity of precluding an alternative.

[BibT_eX]

[DOI]

Artif. Intell., 2007

Llull and Copeland Voting Broadly Resist Bribery and Control.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP.

[BibT_eX]

[DOI]

Holger Spakowski

RAIRO Theor. Informatics Appl., 2006

Generalized Modal Satisfiability.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

The Complexity of Bribery in Elections.

[BibT_eX]

[DOI]

Proceedings of the Proceedings, 2006

2005

The complexity of Kemeny elections.

[BibT_eX]

[DOI]

Holger Spakowski

Jörg Vogel

Theor. Comput. Sci., 2005

All superlinear inverse schemes are coNP-hard.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

The Complexity of Kings

[BibT_eX]

[DOI]

Osamu Watanabe

CoRR, 2005

2004

Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas

[BibT_eX]

[DOI]

CoRR, 2004

The Complexity of Boolean Constraint Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

Complexity of Cycle Length Modularity Problems in Graphs.

[BibT_eX]

[DOI]

Holger Spakowski

Mayur Thakur

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

2002

The Minimization Problem for Boolean Formulas.

[BibT_eX]

[DOI]

Gerd Wechsung

SIAM J. Comput., 2002

Almost-Everywhere Superiority for Quantum Polynomial Time.

[BibT_eX]

[DOI]

Marius Zimand

Inf. Comput., 2002

Equivalence and Isomorphism for Boolean Constraint Satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

2001

The Complexity of Poor Man's Logic.

[BibT_eX]

[DOI]

J. Log. Comput., 2001

Using the No-Search Easy-Hard Technique for Downward Collapse

[BibT_eX]

[DOI]

CoRR, 2001

2000

Computational Politics: Electoral Systems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Modal Satisfiability Is in Deterministic Linear Space.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 2000

1999

On the Power of Positive Turing Reductions.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 1999

Almost-Everywhere Superiority for Quantum Computing

[BibT_eX]

[DOI]

Marius Zimand

CoRR, 1999

Translating Equality Downwards

[BibT_eX]

[DOI]

CoRR, 1999

R1-ttSN(NP) Distinguishes Robust Many-One and Turing Completeness

[BibT_eX]

[DOI]

CoRR, 1999

Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

1998

What's up with downward collapse: using the easy-hard technique to link Boolean and polynomial hierarchy collapses.

[BibT_eX]

[DOI]

SIGACT News, 1998

A Downward Collapse within the Polynomial Hierarchy.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

RS N1-tt (NP) Distinguishes Robust Many-One and Turing Completeness.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1998

Query Order and the Polynomial Hierarchy.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 1998

Recognizing when Greed can Approximate Maximum Independent Sets is Complete for Parallel Access to NP.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1998

Downward Collapse from a Weaker Hypothesis

[BibT_eX]

[DOI]

CoRR, 1998

1997

Raising NP lower bounds to parallel NP lower bounds.

[BibT_eX]

[DOI]

SIGACT News, 1997

Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP.

[BibT_eX]

[DOI]

J. ACM, 1997

An Introduction to Query Order.

[BibT_eX]

Bull. EATCS, 1997

A Downward Translation in the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Query Order in the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

RSN1-tt(NP) Distinguishes Robust Many-One and Turing Completeness.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1996

The Price of Universality.

[BibT_eX]

[DOI]

Notre Dame J. Formal Log., 1996

P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

1995

SPARSE Reduces Conjunctively to TALLY.

[BibT_eX]

[DOI]

Harry Buhrman

Luc Longpré

SIAM J. Comput., 1995

1994

Quasi-injective Reductions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Census Techniques Collapse Space Classes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1994

Complexity Transfer for Modal Logic (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

1993

A modal perspective on the computational complexity of attribute value grammar.

[BibT_eX]

[DOI]

Patrick Blackburn

J. Log. Lang. Inf., 1993

The Relative Power of Logspace and Polynomial Time Reductions.

[BibT_eX]

[DOI]

Harry Buhrman

Leen Torenvliet

Comput. Complex., 1993

1992

Bounded Reductions.

[BibT_eX]

Harry Buhrman

Gerard R. Renardel de Lavalette

Leen Torenvliet

Proceedings of the Complexity Theory: Current Research, 1992

1991

Query Optimization Using Rewrite Rules.

[BibT_eX]

[DOI]

Sieger van Denneheuvel

Karen L. Kwast

Proceedings of the Rewriting Techniques and Applications, 4th International Conference, 1991

1990

Nexttime is not Necessary.

[BibT_eX]

Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, 1990

1989

Nondeterminism fairness and a fundamental analogy.

[BibT_eX]