Stephen A. Fenner

Rabins Wosti

Quantum Inf. Comput., November, 2023

2022

The Complexity of Poset Games.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2022

The complexity of regex crosswords.

[BibT_eX]

[DOI]

Daniel Padé

Inf. Comput., 2022

Implementing the fanout operation with simple pairwise interactions.

[BibT_eX]

[DOI]

Rabins Wosti

CoRR, 2022

2021

Remembrances of Alan.

[BibT_eX]

[DOI]

SIGACT News, 2021

Review of The Theory of Quantum Information John Watrous.

[BibT_eX]

[DOI]

SIGACT News, 2021

2020

Depth-2 QAC circuits cannot simulate quantum parity.

[BibT_eX]

[DOI]

CoRR, 2020

2019

A deterministic parallel algorithm for bipartite perfect matching.

[BibT_eX]

[DOI]

Rohit Gurjar

Commun. ACM, 2019

Complexity of Regex Crosswords.

[BibT_eX]

[DOI]

Daniel Padé

Proceedings of the Language and Automata Theory and Applications, 2019

2018

Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems.

[BibT_eX]

[DOI]

Frederic Green

Steven Homer

SIGACT News, 2018

2017

Guest Column: Parallel Algorithms for Perfect Matching.

[BibT_eX]

[DOI]

Rohit Gurjar

SIGACT News, 2017

Compression Complexity.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Bipartite perfect matching is in quasi-NC.

[BibT_eX]

[DOI]

Rohit Gurjar

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Combinatorial Game Complexity: An Introduction with Poset Games.

[BibT_eX]

[DOI]

John D. Rogers

Bull. EATCS, 2015

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

2014

The complexity of some regex crossword problems.

[BibT_eX]

[DOI]

CoRR, 2014

2013

On Two-Level Poset Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2011

Monochromatic Boxes in Colored Grids.

[BibT_eX]

[DOI]

Joshua N. Cooper

Semmy Purewal

SIAM J. Discret. Math., 2011

Functions That Preserve p-Randomness.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

2009

The Complexity of Finding SUBSEQ(<i>A</i>).

[BibT_eX]

[DOI]

Brian Postow

Theory Comput. Syst., 2009

Efficient Universal Quantum Circuits.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

The complexity of learning SUBSEQ(A).

[BibT_eX]

[DOI]

Brian Postow

Electron. Colloquium Comput. Complex., 2008

Universal Quantum Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

On the Complexity of the Hidden Subgroup Problem.

[BibT_eX]

[DOI]

Yong Zhang

Proceedings of the Theory and Applications of Models of Computation, 2008

2006

Quantum lower bounds for fanout.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2006

The central nature of the Hidden Subgroup problem

[BibT_eX]

[DOI]

Yong Zhang

CoRR, 2006

The Complexity of Learning SUBSEQ (<i>A</i>).

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005

Weakly useful sequences.

[BibT_eX]

[DOI]

Inf. Comput., 2005

Quantum Algorithms for a Set of Group Theoretic Problems.

[BibT_eX]

[DOI]

Yong Zhang

Proceedings of the Theoretical Computer Science, 9th Italian Conference, 2005

Bounds on the Power of Constant-Depth Quantum Circuits.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

Every polynomial-time 1-degree collapses if and only if P = PSPACE.

[BibT_eX]

[DOI]

James S. Royer

J. Symb. Log., 2004

Simplicity and Strong Reductions

[BibT_eX]

[DOI]

Marcus Schaefer

Electron. Colloquium Comput. Complex., 2004

2003

PP-Lowness and a Simple Definition of AWPP.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2003

An oracle builder's toolkit.

[BibT_eX]

[DOI]

Inf. Comput., 2003

A physics-free introduction to the quantum computation model, Computational Complexity Column.

[BibT_eX]

Bull. EATCS, 2003

A Physics-Free Introduction to the Quantum Computation Model

[BibT_eX]

[DOI]

CoRR, 2003

2002

Gales and supergales are equivalent for defining constructive Hausdorff dimension

[BibT_eX]

[DOI]

CoRR, 2002

2001

Hyper-polynomial hierarchies and the polynomial jump.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Two oracles that force a big crunch.

[BibT_eX]

[DOI]

Comput. Complex., 2001

2000

Optimal Proof Systems and Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

1999

Bounded Immunity and Btt-Reductions.

[BibT_eX]

[DOI]

Marcus Schaefer

Math. Log. Q., 1999

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

1997

Oracles that Compute Values.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

Results on Resource-Bounded Measure.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Hyper-Polynomial Hierarchies and the NP-Jump.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Complexity Theory Newsflash.

[BibT_eX]

[DOI]

SIGACT News, 1996

Complements of Multivalued Functions.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Inverting Onto Functions.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Beyond P^(NP) - NEXP.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

Weakly Useful Sequences.

[BibT_eX]

[DOI]

Jack H. Lutz

Elvira Mayordomo

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Resource-Bounded Baire Category: A Stronger Approach.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

Inverting the Turing Jump in Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Almost Weakly 2-Generic Sets.

[BibT_eX]

[DOI]

J. Symb. Log., 1994

1993

On Using Oracles That Compute Values.

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

Gap-Definability as a Closure Property.

[BibT_eX]

[DOI]

Lide Li

Proceedings of the STACS 93, 1993

An Oarcle Builder's Toolkit.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

The Isomorphism Conjecture Holds Relative to an Oracle

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Gap-Definable Counting Classes.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

Notions of Resource-Bounded Category and Genericity.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1989

Every Polynomial-Time 1-Degree Collapses iff P=PSPACE

[BibT_eX]

[DOI]