| Publication | Date of Publication | Type |
|---|
| Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting | 2024-08-06 | Paper |
The join can lower complexity
Lecture Notes in Computer Science | 2024-01-29 | Paper |
Intersection suffices for Boolean hierarchy equivalence
Lecture Notes in Computer Science | 2023-12-12 | Paper |
Query order in the polynomial hierarchy
Fundamentals of Computation Theory | 2022-12-09 | Paper |
Search versus Decision for Election Manipulation Problems
ACM Transactions on Computation Theory | 2022-12-05 | Paper |
A downward translation in the polynomial hierarchy
Lecture Notes in Computer Science | 2022-11-09 | Paper |
Promise problems and access to unambiguous computation
Mathematical Foundations of Computer Science 1992 | 2022-08-18 | Paper |
On the power of parity polynomial time
STACS 89 | 2022-08-16 | Paper |
| scientific article; zbMATH DE number 7509956 (Why is no real title available?) | 2022-04-19 | Paper |
The complexity of online bribery in sequential elections
Journal of Computer and System Sciences | 2022-04-04 | Paper |
| scientific article; zbMATH DE number 7450032 (Why is no real title available?) | 2021-12-20 | Paper |
scientific article; zbMATH DE number 7450032 (Why is no real title available?)
(available as arXiv preprint) | 2021-12-20 | Paper |
The opacity of backbones
Information and Computation | 2021-11-25 | Paper |
The robustness of LWPP and WPP, with an application to graph reconstruction
(available as arXiv preprint) | 2021-08-04 | Paper |
Closure and nonclosure properties of the classes of compressible and rankable sets
Journal of Computer and System Sciences | 2021-06-30 | Paper |
The robustness of LWPP and WPP, with an application to graph reconstruction
Computational Complexity | 2021-05-25 | Paper |
| Dogson's rule and Yong's rule | 2020-11-12 | Paper |
Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption
(available as arXiv preprint) | 2020-10-22 | Paper |
The Power of Self-Reducibility: Selectivity, Information, and Approximation
Complexity and Approximation | 2020-07-20 | Paper |
Reductions to sets of low information content (extended abstract)
Automata, Languages and Programming | 2019-12-04 | Paper |
Closure and nonclosure properties of the compressible and rankable sets
(available as arXiv preprint) | 2019-12-04 | Paper |
Fault-tolerance and complexity (extended abstract)
Automata, Languages and Programming | 2019-03-29 | Paper |
Recursion-theoretic ranking and compression
Journal of Computer and System Sciences | 2019-01-25 | Paper |
Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
Automata, Languages and Programming | 2018-07-04 | Paper |
Pseudorandom generators and the frequency of simplicity
STACS 95 | 2017-12-04 | Paper |
The complexity of controlling candidate-sequential elections
Theoretical Computer Science | 2017-05-15 | Paper |
Search versus decision for election manipulation problems
(available as arXiv preprint) | 2017-01-30 | Paper |
Computational Aspects of Approval Voting
Studies in Choice and Welfare | 2016-11-08 | Paper |
Manipulation complexity of same-system runoff elections
Annals of Mathematics and Artificial Intelligence | 2016-09-16 | Paper |
Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
Annals of Mathematics and Artificial Intelligence | 2016-09-16 | Paper |
| Online voter control in sequential elections | 2015-12-11 | Paper |
Online voter control in sequential elections
(available as arXiv preprint) | 2015-12-11 | Paper |
More natural models of electoral control by partition
Algorithmic Decision Theory | 2015-11-04 | Paper |
The complexity of manipulative attacks in nearly single-peaked electorates
Artificial Intelligence | 2015-08-27 | Paper |
Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
Journal of Artificial Intelligence Research | 2015-08-25 | Paper |
SELF-SPECIFYING MACHINES
International Journal of Foundations of Computer Science | 2015-04-29 | Paper |
Weighted electoral control
Journal of Artificial Intelligence Research | 2015-04-22 | Paper |
The consequences of eliminating NP solutions
Computer Science Review | 2014-10-07 | Paper |
The complexity of online manipulation of sequential elections
Journal of Computer and System Sciences | 2014-02-13 | Paper |
Three hierarchies of simple games parameterized by ``resource parameters
International Journal of Game Theory | 2013-03-04 | Paper |
Multimode control attacks on elections
Journal of Artificial Intelligence Research | 2011-03-08 | Paper |
The shield that never was: societies with single-peaked preferences are more open to manipulation and control
Information and Computation | 2011-02-21 | Paper |
Frequency of correctness versus average polynomial time
Information Processing Letters | 2010-08-20 | Paper |
Witness-isomorphic reductions and the local search problem (extended abstract)
Lecture Notes in Computer Science | 2010-06-17 | Paper |
On the complexity of kings
Theoretical Computer Science | 2010-02-09 | Paper |
Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
Journal of Artificial Intelligence Research | 2009-12-10 | Paper |
How hard is bribery in elections?
Journal of Artificial Intelligence Research | 2009-12-10 | Paper |
Generalized juntas and NP-hard sets
Theoretical Computer Science | 2009-09-10 | Paper |
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
Journal of Heuristics | 2009-08-31 | Paper |
Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
Mathematical Logic Quarterly | 2009-08-14 | Paper |
A Richer Understanding of the Complexity of Election Systems
Fundamental Problems in Computing | 2009-08-05 | Paper |
Anyone but him: the complexity of precluding an alternative
Artificial Intelligence | 2009-07-09 | Paper |
LATIN 2004: Theoretical Informatics
Lecture Notes in Computer Science | 2009-05-07 | Paper |
The complexity of power-index comparison
Theoretical Computer Science | 2009-02-19 | Paper |
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
Theoretical Computer Science | 2008-07-31 | Paper |
The Complexity of Power-Index Comparison
Algorithmic Aspects in Information and Management | 2008-07-10 | Paper |
Copeland Voting Fully Resists Constructive Control
Algorithmic Aspects in Information and Management | 2008-07-10 | Paper |
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time
Fundamentals of Computation Theory | 2008-02-26 | Paper |
On the Complexity of Kings
Fundamentals of Computation Theory | 2008-02-26 | Paper |
The Complexity of Computing the Size of an Interval
SIAM Journal on Computing | 2007-10-22 | Paper |
Query-monotonic Turing reductions
Theoretical Computer Science | 2007-09-19 | Paper |
Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
Lecture Notes in Computer Science | 2007-09-05 | Paper |
Cluster computing and the power of edge recognition
Information and Computation | 2007-08-23 | Paper |
Theory and Applications of Models of Computation
Lecture Notes in Computer Science | 2007-04-30 | Paper |
Complexity results in graph reconstruction
Discrete Applied Mathematics | 2007-02-19 | Paper |
Dichotomy for voting systems
Journal of Computer and System Sciences | 2007-01-22 | Paper |
SOFSEM 2006: Theory and Practice of Computer Science
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Theoretical Computer Science
Lecture Notes in Computer Science | 2006-11-01 | Paper |
If P \(\neq\) NP then some strongly noninvertible functions are invertible
Theoretical Computer Science | 2006-10-20 | Paper |
The complexity of finding top-Toda-equivalence-class members
Theory of Computing Systems | 2006-10-16 | Paper |
Computing and Combinatorics
Lecture Notes in Computer Science | 2006-01-11 | Paper |
Context-free languages can be accepted with absolutely no space overhead
Information and Computation | 2006-01-10 | Paper |
All superlinear inverse schemes are coNP-hard
Theoretical Computer Science | 2005-12-06 | Paper |
ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES
International Journal of Foundations of Computer Science | 2005-11-14 | Paper |
Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
SIAM Journal on Computing | 2005-09-16 | Paper |
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science | 2005-08-22 | Paper |
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science | 2005-08-22 | Paper |
Competing provers yield improved Karp-Lipton collapse results
Information and Computation | 2005-05-04 | Paper |
Algebraic Properties for Selector Functions
SIAM Journal on Computing | 2005-02-21 | Paper |
Lower bounds and the hardness of counting properties
Theoretical Computer Science | 2005-01-11 | Paper |
| scientific article; zbMATH DE number 2040917 (Why is no real title available?) | 2004-02-11 | Paper |
P-immune sets with holes lack self-reducibility properties.
Theoretical Computer Science | 2003-08-17 | Paper |
| scientific article; zbMATH DE number 1962842 (Why is no real title available?) | 2003-08-11 | Paper |
Almost-everywhere superiority for quantum polynomial time
Information and Computation | 2003-01-14 | Paper |
Optimal series-parallel trade-offs for reducing a function to its own graph
Information and Computation | 2003-01-14 | Paper |
| scientific article; zbMATH DE number 1839441 (Why is no real title available?) | 2002-12-02 | Paper |
| scientific article; zbMATH DE number 1759426 (Why is no real title available?) | 2002-11-04 | Paper |
| scientific article; zbMATH DE number 1759396 (Why is no real title available?) | 2002-11-04 | Paper |
| scientific article; zbMATH DE number 1796952 (Why is no real title available?) | 2002-09-05 | Paper |
Reducing the number of solutions of NP functions
Journal of Computer and System Sciences | 2002-08-04 | Paper |
On characterizing the existence of partial one-way permutations
Information Processing Letters | 2002-07-14 | Paper |
| scientific article; zbMATH DE number 1754654 (Why is no real title available?) | 2002-06-12 | Paper |
| scientific article; zbMATH DE number 1665448 (Why is no real title available?) | 2002-04-21 | Paper |
Theory of semi-feasible algorithms
Monographs in Theoretical Computer Science. An EATCS Series | 2002-04-01 | Paper |
| scientific article; zbMATH DE number 1678398 (Why is no real title available?) | 2001-12-04 | Paper |
| On Bounded-Weight Error-Correcting Codes | 2001-02-27 | Paper |
On Bounded-Weight Error-Correcting Codes
(available as arXiv preprint) | 2001-02-27 | Paper |
| scientific article; zbMATH DE number 1543293 (Why is no real title available?) | 2001-02-27 | Paper |
| scientific article; zbMATH DE number 1543295 (Why is no real title available?) | 2001-02-27 | Paper |
| scientific article; zbMATH DE number 1543037 (Why is no real title available?) | 2001-02-26 | Paper |
The complexity theory companion
Texts in Theoretical Computer Science. An EATCS Series | 2001-02-19 | Paper |
| scientific article; zbMATH DE number 1555921 (Why is no real title available?) | 2001-01-24 | Paper |
Restrictive Acceptance Suffices for Equivalence Problems
LMS Journal of Computation and Mathematics | 2000-09-25 | Paper |
Characterizing the existence of one-way permutations
Theoretical Computer Science | 2000-08-21 | Paper |
A second step towards complexity-theoretic analogs of Rice's Theorem
Theoretical Computer Science | 2000-08-21 | Paper |
Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
Journal of Computer and System Sciences | 2000-06-27 | Paper |
| scientific article; zbMATH DE number 1390058 (Why is no real title available?) | 2000-04-26 | Paper |
Robust reductions
Theory of Computing Systems | 2000-03-07 | Paper |
| scientific article; zbMATH DE number 1354134 (Why is no real title available?) | 1999-10-31 | Paper |
| scientific article; zbMATH DE number 1346509 (Why is no real title available?) | 1999-10-03 | Paper |
| scientific article; zbMATH DE number 1304327 (Why is no real title available?) | 1999-08-31 | Paper |
| scientific article; zbMATH DE number 1300961 (Why is no real title available?) | 1999-06-16 | Paper |
| scientific article; zbMATH DE number 1222831 (Why is no real title available?) | 1999-05-18 | Paper |
Boolean operations, joins, and the extended low hierarchy
Theoretical Computer Science | 1999-01-12 | Paper |
| scientific article; zbMATH DE number 1222577 (Why is no real title available?) | 1998-11-11 | Paper |
Exact analysis of Dodgson elections
Journal of the ACM | 1998-11-04 | Paper |
\(R_{1-tt}^Template:\mathcal SN\)(NP) distinguishes robust many-one and Turing completeness
Theory of Computing Systems | 1998-10-01 | Paper |
A Downward Collapse within the Polynomial Hierarchy
SIAM Journal on Computing | 1998-09-21 | Paper |
Query Order
SIAM Journal on Computing | 1998-09-21 | Paper |
Universally serializable computation
Journal of Computer and System Sciences | 1998-08-04 | Paper |
Easy sets and hard certificate schemes
Acta Informatica | 1997-12-10 | Paper |
| scientific article; zbMATH DE number 1091107 (Why is no real title available?) | 1997-11-25 | Paper |
| scientific article; zbMATH DE number 1048042 (Why is no real title available?) | 1997-09-22 | Paper |
Threshold Computation and Cryptographic Security
SIAM Journal on Computing | 1997-08-17 | Paper |
Logspace Reducibility: Models and Equivalences
International Journal of Foundations of Computer Science | 1997-06-16 | Paper |
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
SIAM Journal on Computing | 1997-05-26 | Paper |
Pseudorandom generators and the frequency of simplicity
Journal of Cryptology | 1997-05-26 | Paper |
Strong self-reducibility precludes strong immunity
Mathematical Systems Theory | 1997-03-03 | Paper |
P-selectivity: Intersections and indices
Theoretical Computer Science | 1997-02-28 | Paper |
Optimal advice
Theoretical Computer Science | 1997-02-28 | Paper |
Reducibility classes of P-selective sets
Theoretical Computer Science | 1997-02-27 | Paper |
Computing Solutions Uniquely Collapses the Polynomial Hierarchy
SIAM Journal on Computing | 1996-10-16 | Paper |
NONDETERMINISTICALLY SELECTIVE SETS
International Journal of Foundations of Computer Science | 1996-08-13 | Paper |
Defying upward and downward separation
Information and Computation | 1996-02-20 | Paper |
Easily Checked Generalized Self-Reducibility
SIAM Journal on Computing | 1996-01-28 | Paper |
Space-efficient recognition of sparse self-reducible languages
Computational Complexity | 1995-05-14 | Paper |
On the complexity of graph reconstruction
Mathematical Systems Theory | 1995-02-14 | Paper |
| scientific article; zbMATH DE number 512827 (Why is no real title available?) | 1994-12-11 | Paper |
| scientific article; zbMATH DE number 512802 (Why is no real title available?) | 1994-08-31 | Paper |
Lower bounds for the low hierarchy
Journal of the ACM | 1994-08-21 | Paper |
BANISHING ROBUST TURING COMPLETENESS
International Journal of Foundations of Computer Science | 1994-04-27 | Paper |
| scientific article; zbMATH DE number 522855 (Why is no real title available?) | 1994-03-24 | Paper |
| scientific article; zbMATH DE number 512798 (Why is no real title available?) | 1994-03-10 | Paper |
Quasi-injective reductions
Theoretical Computer Science | 1994-02-22 | Paper |
| scientific article; zbMATH DE number 403952 (Why is no real title available?) | 1993-09-06 | Paper |
On checking versus evaluation of multiple queries
Information and Computation | 1993-08-30 | Paper |
Collapsing degrees via strong computation
Journal of Computer and System Sciences | 1993-08-18 | Paper |
A complexity theory for feasible closure properties
Journal of Computer and System Sciences | 1993-08-18 | Paper |
| scientific article; zbMATH DE number 176750 (Why is no real title available?) | 1993-05-18 | Paper |
Using inductive counting to simulate nondeterministic computation
Information and Computation | 1993-05-16 | Paper |
Relating Equivalence and Reducibility to Sparse Sets
SIAM Journal on Computing | 1993-01-16 | Paper |
Polynomial-time compression
Computational Complexity | 1993-01-16 | Paper |
| scientific article; zbMATH DE number 58301 (Why is no real title available?) | 1992-09-27 | Paper |
ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
International Journal of Foundations of Computer Science | 1992-09-27 | Paper |
Separating complexity classes with tally oracles
Theoretical Computer Science | 1992-06-28 | Paper |
Simultaneous strong separations of probabilistic and unambiguous complexity classes
Mathematical Systems Theory | 1992-06-28 | Paper |
On Sets with Efficient Implicit Membership Tests
SIAM Journal on Computing | 1992-06-27 | Paper |
| scientific article; zbMATH DE number 18628 (Why is no real title available?) | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 18631 (Why is no real title available?) | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 17806 (Why is no real title available?) | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 15884 (Why is no real title available?) | 1992-06-25 | Paper |
Kolmogorov characterizations of complexity classes
Theoretical Computer Science | 1991-01-01 | Paper |
One-way functions and the nonisomorphism of NP-complete sets
Theoretical Computer Science | 1991-01-01 | Paper |
Probabilistic polynomial time is closed under parity reductions
Information Processing Letters | 1991-01-01 | Paper |
A note on enumerative counting
Information Processing Letters | 1991-01-01 | Paper |
On the complexity of ranking
Journal of Computer and System Sciences | 1990-01-01 | Paper |
On the power of parity polynomial time
Mathematical Systems Theory | 1990-01-01 | Paper |
Robust machines accept easy sets
Theoretical Computer Science | 1990-01-01 | Paper |
The Boolean Hierarchy II: Applications
SIAM Journal on Computing | 1989-01-01 | Paper |
The strong exponential hierarchy collapses
Journal of Computer and System Sciences | 1989-01-01 | Paper |
Enumerative counting is hard
Information and Computation | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4208065 (Why is no real title available?) | 1989-01-01 | Paper |
Complexity classes without machines: on complete languages for UP
Theoretical Computer Science | 1988-01-01 | Paper |
The Boolean Hierarchy I: Structural Properties
SIAM Journal on Computing | 1988-01-01 | Paper |
On sparse oracles separating feasible complexity classes
Information Processing Letters | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4074483 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 3978383 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4070309 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3988706 (Why is no real title available?) | 1986-01-01 | Paper |
