| Publication | Date of Publication | Type |
|---|
| The join can lower complexity | 2024-01-29 | Paper |
| Intersection suffices for Boolean hierarchy equivalence | 2023-12-12 | Paper |
| Query order in the polynomial hierarchy | 2022-12-09 | Paper |
| Search versus Decision for Election Manipulation Problems | 2022-12-05 | Paper |
| A downward translation in the polynomial hierarchy | 2022-11-09 | Paper |
| Promise problems and access to unambiguous computation | 2022-08-18 | Paper |
| On the power of parity polynomial time | 2022-08-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5071022 | 2022-04-19 | Paper |
| The complexity of online bribery in sequential elections | 2022-04-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5018515 | 2021-12-20 | Paper |
| The opacity of backbones | 2021-11-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5005153 | 2021-08-04 | Paper |
| Closure and nonclosure properties of the classes of compressible and rankable sets | 2021-06-30 | Paper |
| The robustness of LWPP and WPP, with an application to graph reconstruction | 2021-05-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5133008 | 2020-11-12 | Paper |
| Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption | 2020-10-22 | Paper |
| The Power of Self-Reducibility: Selectivity, Information, and Approximation | 2020-07-20 | Paper |
| Reductions to sets of low information content | 2019-12-04 | Paper |
| Closure and nonclosure properties of the compressible and rankable sets | 2019-12-04 | Paper |
| Fault-tolerance and complexity (Extended abstract) | 2019-03-29 | Paper |
| Recursion-theoretic ranking and compression | 2019-01-25 | Paper |
| Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP | 2018-07-04 | Paper |
| Pseudorandom generators and the frequency of simplicity | 2017-12-04 | Paper |
| The complexity of controlling candidate-sequential elections | 2017-05-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2957899 | 2017-01-30 | Paper |
| Computational Aspects of Approval Voting | 2016-11-08 | Paper |
| Manipulation complexity of same-system runoff elections | 2016-09-16 | Paper |
| Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control | 2016-09-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3457243 | 2015-12-11 | Paper |
| More Natural Models of Electoral Control by Partition | 2015-11-04 | Paper |
| The complexity of manipulative attacks in nearly single-peaked electorates | 2015-08-27 | Paper |
| Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates | 2015-08-25 | Paper |
| SELF-SPECIFYING MACHINES | 2015-04-29 | Paper |
| Weighted Electoral Control | 2015-04-22 | Paper |
| The consequences of eliminating NP solutions | 2014-10-07 | Paper |
| The complexity of online manipulation of sequential elections | 2014-02-13 | Paper |
| Three hierarchies of simple games parameterized by ``resource parameters | 2013-03-04 | Paper |
| Multimode Control Attacks on Elections | 2011-03-08 | Paper |
| The shield that never was: societies with single-peaked preferences are more open to manipulation and control | 2011-02-21 | Paper |
| Frequency of correctness versus average polynomial time | 2010-08-20 | Paper |
| Witness-isomorphic reductions and the local search problem (extended abstract) | 2010-06-17 | Paper |
| On the complexity of kings | 2010-02-09 | Paper |
| Llull and Copeland Voting Computationally Resist Bribery and Constructive Control | 2009-12-10 | Paper |
| How Hard Is Bribery in Elections? | 2009-12-10 | Paper |
| Generalized juntas and NP-hard sets | 2009-09-10 | Paper |
| Guarantees for the success frequency of an algorithm for finding Dodgson-election winners | 2009-08-31 | Paper |
| Hybrid Elections Broaden Complexity-Theoretic Resistance to Control | 2009-08-14 | Paper |
| A Richer Understanding of the Complexity of Election Systems | 2009-08-05 | Paper |
| Anyone but him: the complexity of precluding an alternative | 2009-07-09 | Paper |
| LATIN 2004: Theoretical Informatics | 2009-05-07 | Paper |
| The complexity of power-index comparison | 2009-02-19 | Paper |
| Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions | 2008-07-31 | Paper |
| Copeland Voting Fully Resists Constructive Control | 2008-07-10 | Paper |
| The Complexity of Power-Index Comparison | 2008-07-10 | Paper |
| On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time | 2008-02-26 | Paper |
| On the Complexity of Kings | 2008-02-26 | Paper |
| The Complexity of Computing the Size of an Interval | 2007-10-22 | Paper |
| Query-monotonic Turing reductions | 2007-09-19 | Paper |
| Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners | 2007-09-05 | Paper |
| Cluster computing and the power of edge recognition | 2007-08-23 | Paper |
| Theory and Applications of Models of Computation | 2007-04-30 | Paper |
| Complexity results in graph reconstruction | 2007-02-19 | Paper |
| Dichotomy for voting systems | 2007-01-22 | Paper |
| SOFSEM 2006: Theory and Practice of Computer Science | 2006-11-14 | Paper |
| Theoretical Computer Science | 2006-11-01 | Paper |
| If P \(\neq\) NP then some strongly noninvertible functions are invertible | 2006-10-20 | Paper |
| The complexity of finding top-Toda-equivalence-class members | 2006-10-16 | Paper |
| Computing and Combinatorics | 2006-01-11 | Paper |
| Context-free languages can be accepted with absolutely no space overhead | 2006-01-10 | Paper |
| All superlinear inverse schemes are coNP-hard | 2005-12-06 | Paper |
| ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES | 2005-11-14 | Paper |
| Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries | 2005-09-16 | Paper |
| Mathematical Foundations of Computer Science 2004 | 2005-08-22 | Paper |
| Mathematical Foundations of Computer Science 2004 | 2005-08-22 | Paper |
| Competing provers yield improved Karp-Lipton collapse results | 2005-05-04 | Paper |
| Algebraic Properties for Selector Functions | 2005-02-21 | Paper |
| Lower bounds and the hardness of counting properties | 2005-01-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4452073 | 2004-02-11 | Paper |
| P-immune sets with holes lack self-reducibility properties. | 2003-08-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4418679 | 2003-08-11 | Paper |
| Optimal series-parallel trade-offs for reducing a function to its own graph | 2003-01-14 | Paper |
| Almost-everywhere superiority for quantum polynomial time | 2003-01-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4782706 | 2002-12-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4536344 | 2002-11-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4536375 | 2002-11-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4551344 | 2002-09-05 | Paper |
| Reducing the number of solutions of NP functions | 2002-08-04 | Paper |
| On characterizing the existence of partial one-way permutations | 2002-07-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535082 | 2002-06-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2752147 | 2002-04-21 | Paper |
| Theory of semi-feasible algorithms | 2002-04-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2757852 | 2001-12-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4520757 | 2001-02-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4520762 | 2001-02-27 | Paper |
| On Bounded-Weight Error-Correcting Codes | 2001-02-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4520487 | 2001-02-26 | Paper |
| The complexity theory companion | 2001-02-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4525684 | 2001-01-24 | Paper |
| Restrictive Acceptance Suffices for Equivalence Problems | 2000-09-25 | Paper |
| A second step towards complexity-theoretic analogs of Rice's Theorem | 2000-08-21 | Paper |
| Characterizing the existence of one-way permutations | 2000-08-21 | Paper |
| Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory | 2000-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4934323 | 2000-04-26 | Paper |
| Robust reductions | 2000-03-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4268448 | 1999-10-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4266533 | 1999-10-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4251058 | 1999-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4246719 | 1999-06-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4218419 | 1999-05-18 | Paper |
| Boolean operations, joins, and the extended low hierarchy | 1999-01-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4218116 | 1998-11-11 | Paper |
| Exact analysis of Dodgson elections | 1998-11-04 | Paper |
| \(R_{1-tt}^{{\mathcal SN}}\)(NP) distinguishes robust many-one and Turing completeness | 1998-10-01 | Paper |
| A Downward Collapse within the Polynomial Hierarchy | 1998-09-21 | Paper |
| Query Order | 1998-09-21 | Paper |
| Universally serializable computation | 1998-08-04 | Paper |
| Easy sets and hard certificate schemes | 1997-12-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4366882 | 1997-11-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4348128 | 1997-09-22 | Paper |
| Threshold Computation and Cryptographic Security | 1997-08-17 | Paper |
| Logspace Reducibility: Models and Equivalences | 1997-06-16 | Paper |
| Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets | 1997-05-26 | Paper |
| Pseudorandom generators and the frequency of simplicity | 1997-05-26 | Paper |
| Strong self-reducibility precludes strong immunity | 1997-03-03 | Paper |
| Optimal advice | 1997-02-28 | Paper |
| P-selectivity: Intersections and indices | 1997-02-28 | Paper |
| Reducibility classes of P-selective sets | 1997-02-27 | Paper |
| Computing Solutions Uniquely Collapses the Polynomial Hierarchy | 1996-10-16 | Paper |
| NONDETERMINISTICALLY SELECTIVE SETS | 1996-08-13 | Paper |
| Defying upward and downward separation | 1996-02-20 | Paper |
| Easily Checked Generalized Self-Reducibility | 1996-01-28 | Paper |
| Space-efficient recognition of sparse self-reducible languages | 1995-05-14 | Paper |
| On the complexity of graph reconstruction | 1995-02-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281520 | 1994-12-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281495 | 1994-08-31 | Paper |
| Lower bounds for the low hierarchy | 1994-08-21 | Paper |
| BANISHING ROBUST TURING COMPLETENESS | 1994-04-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4284249 | 1994-03-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281491 | 1994-03-10 | Paper |
| Quasi-injective reductions | 1994-02-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4201936 | 1993-09-06 | Paper |
| On checking versus evaluation of multiple queries | 1993-08-30 | Paper |
| A complexity theory for feasible closure properties | 1993-08-18 | Paper |
| Collapsing degrees via strong computation | 1993-08-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4036580 | 1993-05-18 | Paper |
| Using inductive counting to simulate nondeterministic computation | 1993-05-16 | Paper |
| Polynomial-time compression | 1993-01-16 | Paper |
| Relating Equivalence and Reducibility to Sparse Sets | 1993-01-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4005188 | 1992-09-27 | Paper |
| ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS | 1992-09-27 | Paper |
| Separating complexity classes with tally oracles | 1992-06-28 | Paper |
| Simultaneous strong separations of probabilistic and unambiguous complexity classes | 1992-06-28 | Paper |
| On Sets with Efficient Implicit Membership Tests | 1992-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3975148 | 1992-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3976031 | 1992-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3976034 | 1992-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3972530 | 1992-06-25 | Paper |
| Probabilistic polynomial time is closed under parity reductions | 1991-01-01 | Paper |
| Kolmogorov characterizations of complexity classes | 1991-01-01 | Paper |
| A note on enumerative counting | 1991-01-01 | Paper |
| One-way functions and the nonisomorphism of NP-complete sets | 1991-01-01 | Paper |
| On the power of parity polynomial time | 1990-01-01 | Paper |
| Robust machines accept easy sets | 1990-01-01 | Paper |
| On the complexity of ranking | 1990-01-01 | Paper |
| The strong exponential hierarchy collapses | 1989-01-01 | Paper |
| Enumerative counting is hard | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3356300 | 1989-01-01 | Paper |
| The Boolean Hierarchy II: Applications | 1989-01-01 | Paper |
| Complexity classes without machines: on complete languages for UP | 1988-01-01 | Paper |
| On sparse oracles separating feasible complexity classes | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3805899 | 1988-01-01 | Paper |
| The Boolean Hierarchy I: Structural Properties | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3742716 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3751004 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3802608 | 1986-01-01 | Paper |
