Lane A. Hemaspaandra

According to our database1, Lane A. Hemaspaandra authored at least 276 papers between 1986 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Search versus Decision for Election Manipulation Problems.
ACM Trans. Comput. Theory, 2020

SIGACT News Complexity Theory Column 105.
SIGACT News, 2020

SIGACT News Complexity Theory Column 104.
SIGACT News, 2020

The Power of Self-Reducibility: Selectivity, Information, and Approximation.
Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

2019
SIGACT News Complexity Theory Column 103.
SIGACT News, 2019

SIGACT News Complexity Theory Column 102.
SIGACT News, 2019

SIGACT News Complexity Theory Column 101.
SIGACT News, 2019

SIGACT News Complexity Theory Column 100.
SIGACT News, 2019

Recursion-theoretic ranking and compression.
J. Comput. Syst. Sci., 2019

The Complexity of Online Bribery in Sequential Elections (Extended Abstract).
Proceedings of the Proceedings Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge, 2019

The Complexity of Online Bribery in Sequential Elections.
CoRR, 2019

Existence Versus Exploitation: The Opacity of Backdoors and Backbones Under a Weak Assumption.
Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019

Closure and Nonclosure Properties of the Compressible and Rankable Sets.
Proceedings of the Language and Automata Theory and Applications, 2019

2018
Column: Team Diagonalization.
SIGACT News, 2018

SIGACT News Complexity Theory Column 99.
SIGACT News, 2018

SIGACT News Complexity Theory Column 98.
SIGACT News, 2018

SIGACT News Complexity Theory Column 97.
SIGACT News, 2018

Team Diagonalization.
CoRR, 2018

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

That Most Important Intersection.
Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

Computational Social Choice and Computational Complexity: BFFs?
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

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

SIGACT News Complexity Theory Column 96.
SIGACT News, 2017

SIGACT News Complexity Theory Column 94.
SIGACT News, 2017

SIGACT News Complexity Theory Column 93.
SIGACT News, 2017

Credimus.
CoRR, 2017

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

The complexity of online voter control in sequential elections.
Auton. Agents Multi Agent Syst., 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 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

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.
Proceedings of the 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 81.
SIGACT News, 2014

The complexity of online manipulation of sequential elections.
J. Comput. Syst. Sci., 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

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

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

A Richer Understanding of the Complexity of Election Systems.
Proceedings of the Fundamental Problems in Computing, 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

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

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

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

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

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.
Comput. Sci. Rev., 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

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

2007
Query-monotonic Turing reductions.
Theor. Comput. Sci., 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.
Discret. Appl. Math., 2007

Anyone but him: The complexity of precluding an alternative.
Artif. Intell., 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

P-Selectivity, Immunity, and the Power of One Bit.
Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 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

The Complexity of Kings
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

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

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

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

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

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

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

R<sub>1-tt</sub><sup>SN</sup>(NP) Distinguishes Robust Many-One and Turing Completeness
CoRR, 1999

Characterizations of the Existence of Partial and Total One-Way Permutations
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

R<sup><i>S N</i></sup><sub>1-tt</sub> (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 J. Exp. Algorithmics, 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

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.
Bull. EATCS, 1997

Easy Sets and Hard Certificate Schemes.
Acta Informatica, 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

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

R<sup>SN</sup><sub>1-tt</sub>(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

Strong Self-Reducibility Precludes Strong Immunity.
Math. Syst. 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

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.
Math. Syst. Theory, 1994

Space-Efficient Recognition of Sparse Self-Reducible Languages.
Comput. Complex., 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

Lowness: a yardstick for NP-P.
SIGACT News, 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

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.
Math. Syst. Theory, 1992

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

Is #P Closed under Substraction?
Bull. EATCS, 1992

Polynomial-Time Compression.
Comput. Complex., 1992

Promise Problems and Access to Unambiguous Computation.
Proceedings of the Mathematical Foundations of Computer Science 1992, 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

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

On the Power of Parity Polynomial Time.
Math. Syst. 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

A Note on Relativizing Complexity Classes with Tally Oracles.
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

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.
Proceedings of the Information Processing 89, Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28, 1989

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

On the Power of Probabilistic Polynomial Time: P<sup>NP[log]</sup> 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

1987
Using simulated annealing to design good codes.
IEEE Trans. Inf. 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
The Boolean Hierarchy: Hardware over NP.
Proceedings of the Structure in Complexity Theory, 1986


  Loading...