Jörg Rothe

According to our database1, Jörg Rothe
  • authored at least 209 papers between 1994 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
The complexity of controlling candidate-sequential elections.
Theor. Comput. Sci., 2017

Path-Disruption Games: Bribery and a Probabilistic Model.
Theory Comput. Syst., 2017

The complexity of online voter control in sequential elections.
Autonomous Agents and Multi-Agent Systems, 2017

Positional scoring-based allocation of indivisible goods.
Autonomous Agents and Multi-Agent Systems, 2017

Closing the Gap of Control Complexity in Borda Elections: Solving ten open cases.
Proceedings of the Joint Proceedings of the 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic co-located with the 2017 IEEE International Workshop on Measurements and Networking (2017 IEEE M&N), 2017

Approximate Solutions To Max-Min Fair and Proportionally Fair Allocations of Indivisible Goods.
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Complexity of Control by Partition of Voters and of Voter Groups in Veto and Other Scoring Protocols.
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Solving Seven Open Problems of Offline and Online Control in Borda Elections.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016
Control and Bribery in Voting.
Proceedings of the Handbook of Computational Social Choice, 2016

Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games.
Ann. Math. Artif. Intell., 2016

Cost of Stability and Least Core in Path-Disruption Games.
Proceedings of the STAIRS 2016, 2016

Structural Control in Weighted Voting Games.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Complexity of Control by Partitioning Veto and Maximin Elections and of Control by Adding Candidates to Plurality Elections.
Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

Structural Control in Weighted Voting Games: (Extended Abstract).
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

Altruistic Hedonic Games.
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

Local Fairness in Hedonic Games via Individual Threshold Coalitions.
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

Playing, Voting, and Dividing.
Economics and Computation, 2016

Cake-Cutting: Fair Division of Divisible Goods.
Economics and Computation, 2016

Fair Division of Indivisible Goods.
Economics and Computation, 2016

The Complexity of Manipulative Actions in Single-Peaked Societies.
Economics and Computation, 2016

Noncooperative Game Theory.
Economics and Computation, 2016

Cooperative Game Theory.
Economics and Computation, 2016

Preference Aggregation by Voting.
Economics and Computation, 2016

Judgment Aggregation.
Economics and Computation, 2016

2015
Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules.
Mathematical Social Sciences, 2015

Control complexity in Bucklin and fallback voting: An experimental analysis.
J. Comput. Syst. Sci., 2015

Control complexity in Bucklin and fallback voting: A theoretical analysis.
J. Comput. Syst. Sci., 2015

Complexity of manipulation, bribery, and campaign management in Bucklin and fallback voting.
Autonomous Agents and Multi-Agent Systems, 2015

Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Representing and Solving Hedonic Games with Ordinal Preferences and Thresholds.
Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015

Fairness and Rank-Weighted Utilitarianism in Resource Allocation.
Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

Complexity of Bribery and Control for Uniform Premise-Based Quota Rules Under Various Preference Types.
Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

Verification in Argument-Incomplete Argumentation Frameworks.
Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

Verification in Attack-Incomplete Argumentation Frameworks.
Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

2014
The complexity of online manipulation of sequential elections.
J. Comput. Syst. Sci., 2014

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time.
J. Artif. Intell. Res., 2014

The complexity of probabilistic lobbying.
Discrete Optimization, 2014

Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods.
Discrete Applied Mathematics, 2014

Computational complexity and approximability of social welfare optimization in multiagent resource allocation.
Autonomous Agents and Multi-Agent Systems, 2014

The Margin of Victory in Schulze, Cup, and Copeland Elections: Complexity of the Regular and Exact Variants.
Proceedings of the STAIRS 2014, 2014

False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Toward the Complexity of the Existence of Wonderfully Stable Partitions and Strictly Core Stable Coalition Structures in Hedonic Games.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2014

Scoring Rules for the Allocation of Indivisible Goods.
Proceedings of the ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic, 2014

Bribery in multiple-adversary path-disruption games is hard for the second level of the polynomial hierarchy.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2014

Complexity of manipulation, bribery, and campaign management in bucklin and fallback voting.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2014

2013
The Complexity of Computing Minimal Unidirectional Covering Sets.
Theory Comput. Syst., 2013

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time
CoRR, 2013

The Complexity of Online Manipulation of Sequential Elections.
CoRR, 2013

Complexity of Manipulation, Bribery, and Campaign Management in Bucklin and Fallback Voting.
CoRR, 2013

Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey.
Ann. Math. Artif. Intell., 2013

A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation.
Ann. Math. Artif. Intell., 2013

Algorithms, approximation, and empirical studies in behavioral and computational social choice - Preface.
Ann. Math. Artif. Intell., 2013

The Complexity of Online Manipulation of Sequential Elections.
Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), 2013

Envy-ratio and average-nash social welfare optimization in multiagent resource allocation.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

How to Decrease the Degree of Envy in Allocations of Indivisible Goods.
Proceedings of the Algorithmic Decision Theory - Third International Conference, 2013

Computational Aspects of Manipulation and Control in Judgment Aggregation.
Proceedings of the Algorithmic Decision Theory - Third International Conference, 2013

2012
Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules.
Inf. Process. Lett., 2012

Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach
CoRR, 2012

Online Voter Control in Sequential Elections
CoRR, 2012

The Complexity of Online Manipulation of Sequential Elections
CoRR, 2012

Controlling Candidate-Sequential Elections
CoRR, 2012

Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach.
Proceedings of the Experimental Algorithms - 11th International Symposium, 2012

Probabilistic Path-Disruption Games.
Proceedings of the STAIRS 2012, 2012

Complexity and Approximability of Egalitarian Nash Product Social Welfare Optimization in Multiagent Resource Allocation.
Proceedings of the STAIRS 2012, 2012

Control in Judgment Aggregation.
Proceedings of the STAIRS 2012, 2012

Typical-Case Challenges to Complexity Shields That Are Supposed to Protect Elections Against Manipulation and Control: A Survey.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2012

A Survey of Approximability and Inapproximability Results for Social Welfare Optimization in Multiagent Resource Allocation.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2012

Exact Optimization of Social Welfare by the Nash Product is DP-Complete.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2012

Probabilistic Path-Disruption Games.
Proceedings of the ECAI 2012, 2012

Controlling Candidate-Sequential Elections.
Proceedings of the ECAI 2012, 2012

Online Voter Control in Sequential Elections.
Proceedings of the ECAI 2012, 2012

The Possible Winner Problem with Uncertain Weights.
Proceedings of the ECAI 2012, 2012

Complexity and approximability of social welfare optimization in multiagent resource allocation.
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2012

Campaigns for lazy voters: truncated ballots.
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2012

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

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules
CoRR, 2011

Control Complexity in Bucklin and Fallback Voting
CoRR, 2011

The complexity of voter partition in Bucklin and fallback voting: solving three open problems.
Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), 2011

Computational complexity of two variants of the possible winner problem.
Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), 2011

Bribery in Path-Disruption Games.
Proceedings of the Algorithmic Decision Theory - Second International Conference, 2011

How Hard Is it to Bribe the Judges? A Study of the Complexity of Bribery in Judgment Aggregation.
Proceedings of the Algorithmic Decision Theory - Second International Conference, 2011

How to Calibrate the Scores of Biased Reviewers by Quadratic Programming.
Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011

Einführung in Computational Social Choice: Individuelle Strategien und kollektive Entscheidungen beim Spielen, Wählen und Teilen.
Springer Spektrum, ISBN: 978-3-8274-2570-6, 2011

2010
Bucklin Voting is Broadly Resistant to Control
CoRR, 2010

Control Complexity in Fallback Voting
CoRR, 2010

Merging and Splitting for Power Indices in Weighted Voting Games and Network Flow Games on Hypergraphs.
Proceedings of the STAIRS 2010, 2010

Complexity of Merging and Splitting for the Probabilistic Banzhaf Power Index in Weighted Voting Games.
Proceedings of the ECAI 2010, 2010

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules.
Proceedings of the ECAI 2010, 2010

The Complexity of Computing Minimal Unidirectional Covering Sets.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Control Complexity in Fallback Voting.
Proceedings of the Theory of Computing 2010, 2010

Complexity of social welfare optimization in multiagent resource allocation.
Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010

Exakte Algorithmen für schwere Graphenprobleme.
eXamen.press, Springer, ISBN: 978-3-642-04499-1, 2010

2009
Generalized juntas and NP-hard sets.
Theor. Comput. Sci., 2009

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
Math. Log. Q., 2009

Editorial: Math. Log. Quart. 4/2009.
Math. Log. Q., 2009

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.
Math. Log. Q., 2009

Llull and Copeland Voting Computationally Resist Bribery and Constructive Control.
J. Artif. Intell. Res., 2009

Frequency of correctness versus average polynomial time.
Inf. Process. Lett., 2009

The three-color and two-color TantrixTM rotation puzzle problems are NP-complete via parsimonious reductions.
Inf. Comput., 2009

Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem.
Fundam. Inform., 2009

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control
CoRR, 2009

The Cost of Stability in Coalitional Games
CoRR, 2009

The Complexity of Probabilistic Lobbying
CoRR, 2009

Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols
CoRR, 2009

Deciding Membership in Minimal Upward Covering Sets is Hard for Parallel Access to NP
CoRR, 2009

Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

The shield that never was: societies with single-peaked preferences are more open to manipulation and control.
Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2009), 2009

The Cost of Stability in Coalitional Games.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

The cost of stability in weighted voting games.
Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), 2009

The Complexity of Probabilistic Lobbying.
Proceedings of the Algorithmic Decision Theory, First International Conference, 2009

2008
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions.
Theor. Comput. Sci., 2008

Llull and Copeland Voting Computationally Resist Bribery and Control
CoRR, 2008

Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
CoRR, 2008

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
CoRR, 2008

Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions.
Proceedings of the Language and Automata Theory and Applications, 2008

Copeland Voting Fully Resists Constructive Control.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

Komplexitätstheorie und Kryptologie. Eine Einführung in Kryptokomplexität.
eXamen.press, Springer, ISBN: 978-3-540-79744-9, 2008

2007
Review of "Complexity and Cryptography: An Introduction by John Talbot and Dominic Welsh", Cambridge University Press, 2006, 292 pages.
SIGACT News, 2007

An improved exact algorithm for the domatic number problem.
Inf. Process. Lett., 2007

Quantum cryptography: A survey.
ACM Comput. Surv., 2007

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
CoRR, 2007

Copeland Voting Fully Resists Constructive Control
CoRR, 2007

The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions
CoRR, 2007

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem
CoRR, 2007

Anyone but him: The complexity of precluding an alternative.
Artif. Intell., 2007

Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem.
Proceedings of the Machines, Computations, and Universality, 5th International Conference, 2007

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
Proceedings of the IJCAI 2007, 2007

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Llull and Copeland Voting Broadly Resist Bribery and Control.
Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006
If P neq NP then some strongly noninvertible functions are invertible.
Theor. Comput. Sci., 2006

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
Theory Comput. Syst., 2006

Computational Challenges of Massive Data Sets and Randomness in Computation (J.UCS Special Issue on the First and Second Japanese-German Frontiers of Science Symposia).
J. UCS, 2006

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
J. UCS, 2006

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey.
J. UCS, 2006

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

On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P.
Inf. Process. Lett., 2006

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Richer Understanding of the Complexity of Election Systems
CoRR, 2006

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
CoRR, 2006

An Improved Exact Algorithm for the Domatic Number Problem
CoRR, 2006

2005
Quantum Cryptography: A Survey
Electronic Colloquium on Computational Complexity (ECCC), 2005

Anyone but Him: The Complexity of Precluding an Alternative
CoRR, 2005

An Exact 2.9416n Algorithm for the Three Domatic Number Problem
CoRR, 2005

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
CoRR, 2005

An Exact 2.9416n Algorithm for the Three Domatic Number Problem.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.
Proceedings of the Theoretical Computer Science, 9th Italian Conference, 2005

Anyone but Him: The Complexity of Precluding an Alternative.
Proceedings of the Proceedings, 2005

Complexity Theory and Cryptology. An Introduction to Cryptocomplexity.
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-28520-5, 2005

2004
Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy.
Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

2003
Exact Complexity of the Winner Problem for Young Elections.
Theory Comput. Syst., 2003

Exact complexity of Exact-Four-Colorability.
Inf. Process. Lett., 2003

2002
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.
Theory Comput. Syst., 2002

On characterizing the existence of partial one-way permutations.
Inf. Process. Lett., 2002

Kryptographische Protokolle und Null-Information.
Informatik Spektrum, 2002

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
Electronic Colloquium on Computational Complexity (ECCC), 2002

Some facets of complexity theory and cryptography: A five-lecture tutorial.
ACM Comput. Surv., 2002

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
CoRR, 2002

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.
Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2001
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
Electronic Colloquium on Computational Complexity (ECCC), 2001

Exact Complexity of the Winner Problem for Young Elections
CoRR, 2001

Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
CoRR, 2001

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP
CoRR, 2001

Exact Complexity of Exact-Four-Colorability
CoRR, 2001

A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
CoRR, 2001

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
CoRR, 2001

Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.
Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

If P != NP Then Some Strongly Noninvertible Functions Are Invertible.
Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000
Characterizing the existence of one-way permutations.
Theor. Comput. Sci., 2000

A second step towards complexity-theoretic analogs of Rice's Theorem.
Theor. Comput. Sci., 2000

Corrigendum to "Upward separation for FewP and related classes".
Inf. Process. Lett., 2000

Tally NP Sets and Easy Census Functions.
Inf. Comput., 2000

If P \neq NP then Some Strongly Noninvertible Functions are Invertible
CoRR, 2000

Heuristics Versus Completeness for Graph Coloring.
Chicago J. Theor. Comput. Sci., 2000

1999
One-way functions in worst-case cryptography: algebraic and security properties are on the house.
SIGACT News, 1999

Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory.
J. Comput. Syst. Sci., 1999

Immunity and simplicity for exact counting and other counting classes.
ITA, 1999

One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties
CoRR, 1999

Restrictive Acceptance Suffices for Equivalence Problems
CoRR, 1999

Characterizations of the Existence of Partial and Total One-Way Permutations
CoRR, 1999

Raising NP Lower Bounds to Parallel NP Lower Bounds
CoRR, 1999

A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
CoRR, 1999

Boolean Operations, Joins, and the Extended Low Hierarchy
CoRR, 1999

Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP
CoRR, 1999

Easy Sets and Hard Certificate Schemes
CoRR, 1999

Polynomial-Time Multi-Selectivity
CoRR, 1999

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
CoRR, 1999

Restrictive Acceptance Suffices for Equivalence Problems.
Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

1998
Boolean Operations, Joins, and the Extended Low Hierarchy.
Theor. Comput. Sci., 1998

Recognizing when Greed can Approximate Maximum Independent Sets is Complete for Parallel Access to NP.
Inf. Process. Lett., 1998

Tally NP Sets and Easy Census Functions
CoRR, 1998

Immunity and Simplicity for Exact Counting and Other Counting Classes
CoRR, 1998

Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function
CoRR, 1998

A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Tally NP Sets and Easy Census Functions.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
Raising NP lower bounds to parallel NP lower bounds.
SIGACT News, 1997

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets.
SIAM J. Comput., 1997

Polynomial-Time Multi-Selectivity.
J. UCS, 1997

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

Easy Sets and Hard Certificate Schemes.
Acta Inf., 1997

Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

On Sets with Easy Certificates and the Existence of One-Way Permutations.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1996
Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Join Can Lower Complexity.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
On some promise classes in structural complexity theory.
PhD thesis, 1995

Intersection Suffices for Boolean Hierarchy Equivalence.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994
Upward Separation for FewP and Related Classes.
Inf. Process. Lett., 1994


  Loading...