Lane A. Hemaspaandra

According to our database1, Lane A. Hemaspaandra
  • authored at least 355 papers between 1986 and 2017.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

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

SIGACT News Complexity Theory Column 94.
SIGACT News, 2017

SIGACT News Complexity Theory Column 93.
SIGACT News, 2017

Computational Social Choice and Computational Complexity: BFFs?
CoRR, 2017

The Opacity of Backbones and Backdoors Under a Weak Assumption.
CoRR, 2017

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

The Opacity of Backbones.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016
Dodgson's Rule and Young's Rule.
Proceedings of the Handbook of Computational Social Choice, 2016

SIGACT News Complexity Theory Column 93.
SIGACT News, 2016

SIGACT News Complexity Theory Column 91.
SIGACT News, 2016

SIGACT News Complexity Theory Column 90: Introduction to Complexity Theory Column 90.
SIGACT News, 2016

More on Compression and Ranking.
CoRR, 2016

Recursion-Theoretic Ranking and Compression.
CoRR, 2016

The Opacity of Backbones.
CoRR, 2016

Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.
Ann. Math. Artif. Intell., 2016

Manipulation Complexity of Same-System Runoff Elections.
Ann. Math. Artif. Intell., 2016

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

2015
SIGACT News Complexity Theory Column 88/89: Introduction to Complexity Theory Column 88/89.
SIGACT News, 2015

SIGACT News Complexity Theory Column 87: Introduction to Complexity Theory Column 87.
SIGACT News, 2015

SIGACT News Complexity Theory Column 86: Introduction to Complexity Theory Column 86.
SIGACT News, 2015

SIGACT News Complexity Theory Column 85.
SIGACT News, 2015

Weighted Electoral Control.
J. Artif. Intell. Res., 2015

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates.
J. Artif. Intell. Res., 2015

The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract).
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

More Natural Models of Electoral Control by Partition.
Proceedings of the Algorithmic Decision Theory - 4th International Conference, 2015

2014
SIGACT News Complexity Theory Column 84.
SIGACT News, 2014

Beautiful structures: an appreciation of the contributions of Alan Selman.
SIGACT News, 2014

SIGACT news complexity theory column 82.
SIGACT News, 2014

SIGACT news complexity theory column 82.
SIGACT News, 2014

SIGACT news complexity theory column 81.
SIGACT News, 2014

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

A Control Dichotomy for Pure Scoring Rules.
CoRR, 2014

Beautiful Structures: An Appreciation of the Contributions of Alan Selman.
CoRR, 2014

More Natural Models of Electoral Control by Partition.
CoRR, 2014

The complexity of manipulative attacks in nearly single-peaked electorates.
Artif. Intell., 2014

Bribery and voter control under voting-rule uncertainty.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2014

A Control Dichotomy for Pure Scoring Rules.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013
SIGACT news complexity theory column 80.
SIGACT News, 2013

SIGACT news complexity theory column 78.
SIGACT News, 2013

SIGACT news complexity theory column 77.
SIGACT News, 2013

Three hierarchies of simple games parameterized by "resource" parameters.
Int. J. Game Theory, 2013

Weighted Electoral Control
CoRR, 2013

X THEN X: Manipulation of Same-System Runoff Elections
CoRR, 2013

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

Control in the Presence of Manipulators: Cooperative and Competitive Cases.
CoRR, 2013

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

Search versus Decision for Election Manipulation Problems.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Control in the Presence of Manipulators: Cooperative and Competitive Cases.
Proceedings of the IJCAI 2013, 2013

Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

Weighted electoral control.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

2012
SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms.
SIGACT News, 2012

SIGACT news complexity theory column 75.
SIGACT News, 2012

SIGACT news complexity theory column 74.
SIGACT News, 2012

SIGACT news complexity theory column 73.
SIGACT News, 2012

An Atypical Survey of Typical-Case Heuristic Algorithms
CoRR, 2012

Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control
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

Search versus Decision for Election Manipulation Problems
CoRR, 2012

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

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

2011
SIGACT news complexity theory column 72.
SIGACT News, 2011

SIGACT news complexity theory column 71.
SIGACT News, 2011

SIGACT news complexity theory column 70.
SIGACT News, 2011

SIGACT news complexity theory column 69.
SIGACT News, 2011

Multimode Control Attacks on Elections.
J. Artif. Intell. Res., 2011

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

Barbosa, Uniform Polynomial Time Bounds, and Promises
CoRR, 2011

The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates
CoRR, 2011

The complexity of manipulative attacks in nearly single-peaked electorates.
Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), 2011

2010
On the complexity of kings.
Theor. Comput. Sci., 2010

SIGACT news complexity theory column 68.
SIGACT News, 2010

SIGACT News Complexity Theory Column 67.
SIGACT News, 2010

A Note on Nonuniform versus Uniform ACC^k Circuits for NE
CoRR, 2010

Multimode Control Attacks on Elections
CoRR, 2010

Using complexity to protect elections.
Commun. ACM, 2010

10101 Executive Summary - Computational Foundations of Social Choice.
Proceedings of the Computational Foundations of Social Choice, 07.03. - 12.03.2010, 2010

10101 Abstracts Collection - Computational Foundations of Social Choice.
Proceedings of the Computational Foundations of Social Choice, 07.03. - 12.03.2010, 2010

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates.
Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010

2009
The complexity of power-index comparison.
Theor. Comput. Sci., 2009

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

SIGACT news complexity theory column 65.
SIGACT News, 2009

SIGACT news complexity theory column 64.
SIGACT News, 2009

SIGACT news complexity theory column 63.
SIGACT News, 2009

SIGACT news complexity theory column 62.
SIGACT News, 2009

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

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

How Hard Is Bribery in Elections?
J. Artif. Intell. Res., 2009

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

Guarantees for the success frequency of an algorithm for finding Dodgson-election winners.
J. Heuristics, 2009

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control
CoRR, 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

Multimode Control Attacks on Elections.
Proceedings of the IJCAI 2009, 2009

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

SIGACT news complexity theory column 61.
SIGACT News, 2008

SIGACT news complexity theory column 59: introduction.
SIGACT News, 2008

The consequences of eliminating NP solutions.
Computer Science Review, 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

The Complexity of Power-Index Comparison
CoRR, 2008

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

The Complexity of Power-Index Comparison.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007
Query-monotonic Turing reductions.
Theor. Comput. Sci., 2007

Introduction.
SIGACT News, 2007

Introduction.
SIGACT News, 2007

The Complexity of Computing the Size of an Interval.
SIAM J. Comput., 2007

Dichotomy for voting systems.
J. Comput. Syst. Sci., 2007

Cluster computing and the power of edge recognition.
Inf. Comput., 2007

Complexity results in graph reconstruction.
Discrete Applied Mathematics, 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

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

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

On the Complexity of Kings.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 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

SIGACT news complexity theory column 53.
SIGACT News, 2006

SIGACT news complexity theory column 52.
SIGACT News, 2006

SIGACT news complexity theory column 51.
SIGACT News, 2006

Open questions in the theory of semifeasible computation.
SIGACT News, 2006

The Complexity of Finding Top-Toda-Equivalence-Class Members.
Theory Comput. Syst., 2006

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

How Hard Is Bribery in Elections?
CoRR, 2006

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

The Consequences of Eliminating NP Solutions
CoRR, 2006

Query-Monotonic Turing Reductions
CoRR, 2006

Cluster Computing and the Power of Edge Recognition.
Proceedings of the Theory and Applications of Models of Computation, 2006

P-Selectivity, Immunity, and the Power of One Bit.
Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006

Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

The Consequences of Eliminating NP Solutions.
Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, USA, June 21, 2006

The Complexity of Bribery in Elections.
Proceedings of the Proceedings, 2006

2005
All superlinear inverse schemes are coNP-hard.
Theor. Comput. Sci., 2005

SIGACT news complexity theory column 49.
SIGACT News, 2005

SIGACT news complexity theory column 48.
SIGACT News, 2005

Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries.
SIAM J. Comput., 2005

Advice for semifeasible sets and the complexity-theoretic cost(lessness) of algebraic properties.
Int. J. Found. Comput. Sci., 2005

Context-free languages can be accepted with absolutely no space overhead.
Inf. Comput., 2005

Competing provers yield improved Karp-Lipton collapse results.
Inf. Comput., 2005

Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
CoRR, 2005

Cluster Computing and the Power of Edge Recognition
CoRR, 2005

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

Open Questions in the Theory of Semifeasible Computation
CoRR, 2005

The Complexity of Kings
CoRR, 2005

P-Selectivity, Immunity, and the Power of One Bit
CoRR, 2005

Dichotomy for Voting Systems
CoRR, 2005

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

The Complexity of Computing the Size of an Interval
CoRR, 2005

Algebraic Properties for Selector Functions
CoRR, 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

Query-Monotonic Turing Reductions.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

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

2004
Lower bounds and the hardness of counting properties.
Theor. Comput. Sci., 2004

SIGACT news complexity theory column 43.
SIGACT News, 2004

Algebraic Properties for Selector Functions.
SIAM J. Comput., 2004

Overhead-Free Computation, DCFLs, and CFLs
CoRR, 2004

All Superlinear Inverse Schemes are coNP-Hard
CoRR, 2004

Complexity Results in Graph Reconstruction
CoRR, 2004

Complexity Results in Graph Reconstruction.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

All Superlinear Inverse Schemes Are coNP-Hard.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

The Complexity of Finding Top-Toda-Equivalence-Class Members.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Advice for Semifeasible Sets and the Complexity-Theoretic Cost(lessness) of Algebraic Properties.
Proceedings of the 6th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2004, London, Ontario, Canada, July 26, 2004

2003
Theory of Semi-Feasible Algorithms
Monographs in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-05080-4, 2003

P-immune sets with holes lack self-reducibility properties.
Theor. Comput. Sci., 2003

SIGACT news complexity theory column 42.
SIGACT News, 2003

SIGACT News complexity theory column 41.
SIGACT News, 2003

SIGACT news complexity theory column 40.
SIGACT News, 2003

Competing Provers Yield Improved Karp-Lipton Collapse Results.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Computation with Absolutely No Space Overhead.
Proceedings of the Developments in Language Theory, 7th International Conference, 2003

2002
The Complexity Theory Companion
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-04880-1, 2002

SIGACT news complexity theory column 38.
SIGACT News, 2002

SIGACT news complexity theory comun 37.
SIGACT News, 2002

SIGACT news complexity theory column 36.
SIGACT News, 2002

SIGACT news complexity theory column 35.
SIGACT News, 2002

Reducing the Number of Solutions of NP Functions.
J. Comput. Syst. Sci., 2002

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

Almost-Everywhere Superiority for Quantum Polynomial Time.
Inf. Comput., 2002

Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph.
Inf. Comput., 2002

Lower Bounds and the Hardness of Counting Properties.
Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2001
The complexity theory companion.
SIGACT News, 2001

SIGACT news complexity theory column 34.
SIGACT News, 2001

Complexity theory.
SIGACT News, 2001

SIGACT News complexity theory column 32.
SIGACT News, 2001

SIGACT news complexity theory column 31.
SIGACT News, 2001

Using the No-Search Easy-Hard Technique for Downward Collapse
CoRR, 2001

P-Immune Sets with Holes Lack Self-Reducibility Properties
CoRR, 2001

The Complexity of Computing the Size of an Interval.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

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

Algebraic Properties for P-Selectivity.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 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

Erratum to "Reducibility classes of P-selective sets".
Theor. Comput. Sci., 2000

A moment of perfect clarity I: the parallel census technique.
SIGACT News, 2000

A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions.
SIGACT News, 2000

Take-home Complexity
CoRR, 2000

A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
CoRR, 2000

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

A Moment of Perfect Clarity I: The Parallel Census Technique
CoRR, 2000

Reducing the Number of Solutions of NP Functions.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Computational Politics: Electoral Systems.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999
Theoretical Computer Science.
Proceedings of the Handbook of Discrete and Combinatorial Mathematics., 1999

Biomolecular computing: recent theoretical and experimental advances.
SIGACT News, 1999

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

Robust Reductions.
Theory Comput. Syst., 1999

A Note on Bounded-Weight Error-Correcting Codes.
J. UCS, 1999

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

Self-Specifying Machines.
Int. J. Found. Comput. Sci., 1999

Almost-Everywhere Superiority for Quantum Computing
CoRR, 1999

On Bounded-Weight Error-Correcting Codes
CoRR, 1999

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

Translating Equality Downwards
CoRR, 1999

A Downward Collapse within the Polynomial Hierarchy
CoRR, 1999

Self-Specifying Machines
CoRR, 1999

Query Order and the Polynomial Hierarchy
CoRR, 1999

An Introduction to Query Order
CoRR, 1999

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

What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses
CoRR, 1999

Query Order
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

Robust Reductions
CoRR, 1999

Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries.
Proceedings of the STACS 99, 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

Writing and editing complexity theory: tales and tools.
SIGACT News, 1998

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

Take-home complexity.
SIGACT News, 1998

Query Order.
SIAM J. Comput., 1998

A Downward Collapse within the Polynomial Hierarchy.
SIAM J. Comput., 1998

RS N1-tt (NP) Distinguishes Robust Many-One and Turing Completeness.
Theory Comput. Syst., 1998

A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets.
J. UCS, 1998

Query Order and the Polynomial Hierarchy.
J. UCS, 1998

Power Balance and Apportionment Algorithms for the United States Congress.
ACM Journal of Experimental Algorithmics, 1998

Writing and Editing Complexity Theory: Tales and Tools
CoRR, 1998

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

Downward Collapse from a Weaker Hypothesis
CoRR, 1998

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

Robust Reductions.
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

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

SIGACT News complexity theory column 18.
SIGACT News, 1997

Journals to Die For.
SIGACT News, 1997

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

Threshold Computation and Cryptographic Security.
SIAM J. Comput., 1997

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

Universally Serializable Computation.
J. Comput. Syst. Sci., 1997

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

Logspace Reducibility: Models and Equivalences.
Int. J. Found. Comput. Sci., 1997

An Introduction to Query Order.
Bulletin of the EATCS, 1997

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

A Downward Translation in the Polynomial Hierarchy.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 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

Query Order in the Polynomial Hierarchy.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

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

RSN1-tt(NP) Distinguishes Robust Many-One and Turing Completeness.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1996
Optimal Advice.
Theor. Comput. Sci., 1996

Reducibility Classes of P-Selective Sets.
Theor. Comput. Sci., 1996

SIGACT News Complexity Theory Column 12.
SIGACT News, 1996

Computing Solutions Uniquely Collapses the Polynomial Hierarchy.
SIAM J. Comput., 1996

Strong Self-Reducibility Precludes Strong Immunity.
Mathematical Systems Theory, 1996

Pseudorandom Generators and the Frequency of Simplicity.
J. Cryptology, 1996

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

Computing Solutions Uniquely Collapses the Polynomial Hierarchy
Electronic Colloquium on Computational Complexity (ECCC), 1996

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

1995
Defying Upward and Downward Separation
Inf. Comput., August, 1995

P-Selectivity: Intersections and Indices.
Theor. Comput. Sci., 1995

The satanic notations: counting classes beyond #P and other definitional adventures.
SIGACT News, 1995

Worlds to die for.
SIGACT News, 1995

SIGACT News Complexity Theory Column 10.
SIGACT News, 1995

Easily Checked Generalized Self-Reducibility.
SIAM J. Comput., 1995

Nondeterministically Selective Sets.
Int. J. Found. Comput. Sci., 1995

Pseudorandom Generators and the Frequency of Simplicity.
STACS, 1995

Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

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

1994
Quasi-injective Reductions.
Theor. Comput. Sci., 1994

Teaching Computational Complexity: Resources to Treasure.
SIGACT News, 1994

Complexity theory column 5: the not-ready-for-prime-time conjectures.
SIGACT News, 1994

Semi-membership algorithms: some recent advances.
SIGACT News, 1994

On the Complexity of Graph Reconstruction.
Mathematical Systems Theory, 1994

Space-Efficient Recognition of Sparse Self-Reducible Languages.
Computational Complexity, 1994

Computing Solutions Uniquely collapses the Polynomial Hierarchy.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993
On Checking Versus Evaluation of Multiple Queries
Inf. Comput., July, 1993

Using Inductive Counting to Simulate Nondeterministic Computation
Inf. Comput., January, 1993

Is #P Closed Under Subtraction?
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

A Complexity Theory for Feasible Closure Properties.
J. Comput. Syst. Sci., 1993

Collapsing Degrees via Strong Computation.
J. Comput. Syst. Sci., 1993

Banishing Robust Turing Completeness.
Int. J. Found. Comput. Sci., 1993

Defying Upward and Downward Separation.
Proceedings of the STACS 93, 1993

Threshold Computation and Cryptographic Security.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Selectivity.
Proceedings of the Computing and Information, 1993

Fault-Tolerance and Complexity (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Easity Checked Self-Reducibility (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

1992
Separating Complexity Classes With Tally Oracles.
Theor. Comput. Sci., 1992

Relating Equivalence and Reducibility to Sparse Sets.
SIAM J. Comput., 1992

Simultaneous Strong Separations of Probabilistic and Unambiguous Complexity Classes.
Mathematical Systems Theory, 1992

Lower Bounds for the Low Hierarchy.
J. ACM, 1992

Is #P Closed under Substraction?
Bulletin of the EATCS, 1992

Polynomial-Time Compression.
Computational Complexity, 1992

Promise Problems and Access to Unambiguous Computation.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Banishing Robust Turing Completeness.
Proceedings of the Logical Foundations of Computer Science, 1992

Reductions to Sets of Low Information Content.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Promise Problems and Guarded Access to Unambiguous Computation.
Proceedings of the Complexity Theory: Current Research, 1992

Reductions to Sets of Low Information Content.
Proceedings of the Complexity Theory: Current Research, 1992

How Hard Are Sparse Sets?
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
Kolmogorov Characterizations of Complexity Classes.
Theor. Comput. Sci., 1991

On Sets Polynomially Enumerable by Iteration.
Theor. Comput. Sci., 1991

One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Theor. Comput. Sci., 1991

On Sets with Efficient Implicit Membership Tests.
SIAM J. Comput., 1991

Near-Testable Sets.
SIAM J. Comput., 1991

A Note on Enumarative Counting.
Inf. Process. Lett., 1991

Probabilistic Polynomial Time is Closed under Parity Reductions.
Inf. Process. Lett., 1991

On the Limitations of Locally Robust Positive Reductions.
Int. J. Found. Comput. Sci., 1991

Collapsing Degrees via Strong Computation (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

On the Structure and Complexity of Infinite Sets with Minimal Perfect Hash Functions.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

On the Complexity of Graph Reconstruction.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

A Complexity Theory for Feasible Closure Properties.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

Relating Equivalence and Reducibility to Sparse Sets.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990
Robust Machines Accept Easy Sets.
Theor. Comput. Sci., 1990

On the Power of Parity Polynomial Time.
Mathematical Systems Theory, 1990

On the Complexity of Ranking.
J. Comput. Syst. Sci., 1990

Algorithms from Complexity Theory: Polynominal-Time Operations for Complex Sets.
Proceedings of the Algorithms, 1990

On Checking Versus Evaluation of Multiple Queries.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Using Inductive Counting to Simulate Nondeterministic Computation.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

A Note on Relativizing Complexity Classes with Tally Oracles.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

On Sets with Efficient Implicit Membership Tests.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Enumerative Counting Is Hard
Inf. Comput., July, 1989

The Boolean Hierarchy II: Applications.
SIAM J. Comput., 1989

The Strong Exponential Hierarchy Collapses.
J. Comput. Syst. Sci., 1989

On the Power of Parity Polynomial Time.
Proceedings of the STACS 89, 1989

Polynomial-Time Functions Generate SAT: On P-Splinters.
Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

Using Randomness to Characterize the Complexity of Computation.
IFIP Congress, 1989

Lower Bounds for the Low Hierarchy (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

On the Limitations of Locally Robust Positive Reductions.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1989

On the Power of Probabilistic Polynomial Time: PNP[log] subseteq PP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Complexity Classes without Machines: On Complete Languages for UP.
Theor. Comput. Sci., 1988

The Boolean Hierarchy I: Structural Properties.
SIAM J. Comput., 1988

On Sparse Oracles Separating Feasible Complexity Classes.
Inf. Process. Lett., 1988

Structure of Complexity Classes: Separations, Collapses, and Completeness.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

On Generating Solved Instances of Computational Problems.
Proceedings of the Advances in Cryptology, 1988

Enumerative counting is hard.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Using simulated annealing to design good codes.
IEEE Trans. Information Theory, 1987

The Strong Exponential Hierarchy Collapses
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

The strong exponential hierarchy collapses.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

On ranking.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

One-way functions, robustness, and the non-isomorphism of NP-complete sets.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986
On Sparse Oracles Separating Feasible Complexity Classes.
Proceedings of the STACS 86, 1986

Complexity Classes Without Machines: On Complete Languages for UP.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

The Boolean Hierarchy: Hardware over NP.
Proceedings of the Structure in Complexity Theory, 1986


  Loading...