Stephen A. Fenner

79 papers A* 5A 7B 4C 2Misc 1Journal 54Unranked 6
YearRankTypeTitle / Venue / Authors
2025 J jnl
Tight bounds on depth-2 QAC-circuits computing parity.
CoRR
Stephen A. Fenner, Daniel Grier, Daniel Padé, Thomas Thierauf
2023 J jnl
Implementing the quantum fanout operation with simple pairwise interactions.
Quantum Inf. Comput.
Stephen A. Fenner, Rabins Wosti
2022 J jnl
Implementing the fanout operation with simple pairwise interactions.
CoRR
Stephen A. Fenner, Rabins Wosti
2022 J jnl
The Complexity of Poset Games.
J. Graph Algorithms Appl.
Stephen A. Fenner, Daniel Grier, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
2022 J jnl
The complexity of regex crosswords.
Inf. Comput.
Stephen A. Fenner, Daniel Padé, Thomas Thierauf
2021 J jnl
Bipartite Perfect Matching is in Quasi-NC.
SIAM J. Comput.
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2021 J jnl
Remembrances of Alan.
SIGACT News
Stephen A. Fenner
2021 J jnl
Review of The Theory of Quantum Information John Watrous.
SIGACT News
Stephen A. Fenner
2020 J jnl
Depth-2 QAC circuits cannot simulate quantum parity.
CoRR
Daniel Padé, Stephen A. Fenner, Daniel Grier, Thomas Thierauf
2019 J jnl
A deterministic parallel algorithm for bipartite perfect matching.
Commun. ACM
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2019 C conf
Complexity of Regex Crosswords.
LATA
Stephen A. Fenner, Daniel Padé
2018 J jnl
Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems.
SIGACT News
Stephen A. Fenner, Frederic Green, Steven Homer
2017 J jnl
Compression Complexity.
CoRR
Stephen A. Fenner, Lance Fortnow
2017 J jnl
Guest Column: Parallel Algorithms for Perfect Matching.
SIGACT News
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2016 J jnl
Bipartite Perfect Matching is in quasi-NC.
CoRR
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2016 A* conf
Bipartite perfect matching is in quasi-NC.
STOC
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2015 J jnl
Bipartite Perfect Matching is in quasi-NC.
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
2015 J jnl
Combinatorial Game Complexity: An Introduction with Poset Games.
CoRR
Stephen A. Fenner, John D. Rogers
2015 J jnl
Combinatorial Game Complexity: An Introduction with Poset Games.
Bull. EATCS
Stephen A. Fenner, John D. Rogers
2015 B conf
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.
ISAAC
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2015 J jnl
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games.
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2015 J jnl
Quantum Algorithms for a Set of Group Theoretic Problems.
Int. J. Found. Comput. Sci.
Stephen A. Fenner, Yong Zhang
2014 J jnl
The complexity of some regex crossword problems.
CoRR
Stephen A. Fenner
2013 J jnl
Functions that preserve p-randomness.
Inf. Comput.
Stephen A. Fenner
2013 J jnl
On Two-Level Poset Games.
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
2013 J jnl
On the Complexity of the Hidden Subgroup Problem.
Int. J. Found. Comput. Sci.
Stephen A. Fenner, Yong Zhang
2012 J jnl
Functions that preserve p-randomness
CoRR
Stephen A. Fenner
2011 B conf
Functions That Preserve p-Randomness.
FCT
Stephen A. Fenner
2011 J jnl
Monochromatic Boxes in Colored Grids.
SIAM J. Discret. Math.
Joshua N. Cooper, Stephen A. Fenner, Semmy Purewal
2010 J jnl
Efficient universal quantum circuits.
Quantum Inf. Comput.
Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer
2009 Misc conf
Efficient Universal Quantum Circuits.
COCOON
Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer
2009 J jnl
The Complexity of Finding SUBSEQ(
Theory Comput. Syst.
Stephen A. Fenner, William I. Gasarch, Brian Postow
2009 J jnl
The complexity of learning SUBSEQ(A).
J. Symb. Log.
Stephen A. Fenner, William I. Gasarch, Brian Postow
2008 C conf
On the Complexity of the Hidden Subgroup Problem.
TAMC
Stephen A. Fenner, Yong Zhang
2008 J jnl
The complexity of learning SUBSEQ(A).
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, William I. Gasarch, Brian Postow
2008 J jnl
Universal Quantum Circuits
CoRR
Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer
2008 J jnl
Universal Quantum Circuits.
Electron. Colloquium Comput. Complex.
Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer
2006 J jnl
Quantum lower bounds for fanout.
Quantum Inf. Comput.
M. Fang, Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang
2006 B conf
The Complexity of Learning SUBSEQ (
ALT
Stephen A. Fenner, William I. Gasarch
2006 J jnl
The central nature of the Hidden Subgroup problem
CoRR
Stephen A. Fenner, Yong Zhang
2005 B conf
Bounds on the Power of Constant-Depth Quantum Circuits.
FCT
Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang
2005 — conf
Quantum Algorithms for a Set of Group Theoretic Problems.
ICTCS
Stephen A. Fenner, Yong Zhang
2005 J jnl
Weakly useful sequences.
Inf. Comput.
Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo, Patrick Reardon
2004 J jnl
Every polynomial-time 1-degree collapses if and only if P = PSPACE.
J. Symb. Log.
Stephen A. Fenner, Stuart A. Kurtz, James S. Royer
2004 J jnl
Simplicity and Strong Reductions
Electron. Colloquium Comput. Complex.
Marcus Schaefer, Stephen A. Fenner
2003 J jnl
A Physics-Free Introduction to the Quantum Computation Model
CoRR
Stephen A. Fenner
2003 J jnl
A physics-free introduction to the quantum computation model, Computational Complexity Column.
Bull. EATCS
Stephen A. Fenner
2003 J jnl
An oracle builder's toolkit.
Inf. Comput.
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li
2003 J jnl
Inverting onto functions.
Inf. Comput.
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
2003 J jnl
PP-Lowness and a Simple Definition of AWPP.
Theory Comput. Syst.
Stephen A. Fenner
2002 J jnl
Gales and supergales are equivalent for defining constructive Hausdorff dimension
CoRR
Stephen A. Fenner
2002 J jnl
PP-lowness and a simple definition of AWPP
Electron. Colloquium Comput. Complex.
Stephen A. Fenner
2001 J jnl
Hyper-polynomial hierarchies and the polynomial jump.
Theor. Comput. Sci.
Stephen A. Fenner, Steven Homer, Randall J. Pruim, Marcus Schaefer
2001 J jnl
Two oracles that force a big crunch.
Comput. Complex.
Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet
2000 A conf
Optimal Proof Systems and Sparse Sets.
STACS
Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek
1999 J jnl
Bounded Immunity and Btt-Reductions.
Math. Log. Q.
Stephen A. Fenner, Marcus Schaefer
1999 J jnl
Complements of Multivalued Functions.
Chic. J. Theor. Comput. Sci.
Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
1999 J jnl
Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy
Electron. Colloquium Comput. Complex.
Stephen A. Fenner, Frederic Green, Steven Homer, Randall J. Pruim
1997 A conf
Hyper-Polynomial Hierarchies and the NP-Jump.
CCC
Stephen A. Fenner, Steven Homer, Randall J. Pruim, Marcus Schaefer
1997 J jnl
Oracles that Compute Values.
SIAM J. Comput.
Stephen A. Fenner, Steven Homer, Mitsunori Ogihara, Alan L. Selman
1997 A* conf
Results on Resource-Bounded Measure.
ICALP
Harry Buhrman, Stephen A. Fenner, Lance Fortnow
1996 A conf
Complements of Multivalued Functions.
CCC
Stephen A. Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, Heribert Vollmer
1996 J jnl
Complexity Theory Newsflash.
SIGACT News
Stephen A. Fenner, Lance Fortnow, William I. Gasarch
1996 J jnl
Gap-Definability as a Closure Property.
Inf. Comput.
Stephen A. Fenner, Lance Fortnow, Lide Li
1996 A conf
Inverting Onto Functions.
CCC
Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers
1996 J jnl
The Isomorphism Conjecture Holds Relative to an Oracle.
SIAM J. Comput.
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1995 A conf
Beyond P^(NP) - NEXP.
STACS
Stephen A. Fenner, Lance Fortnow
1995 — conf
Inverting the Turing Jump in Complexity Theory.
SCT
Stephen A. Fenner
1995 — conf
Resource-Bounded Baire Category: A Stronger Approach.
SCT
Stephen A. Fenner
1995 A* conf
Weakly Useful Sequences.
ICALP
Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo
1994 J jnl
Almost Weakly 2-Generic Sets.
J. Symb. Log.
Stephen A. Fenner
1994 J jnl
Gap-Definable Counting Classes.
J. Comput. Syst. Sci.
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1993 — conf
An Oarcle Builder's Toolkit.
SCT
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li
1993 A conf
Gap-Definability as a Closure Property.
STACS
Stephen A. Fenner, Lance Fortnow, Lide Li
1993 A conf
On Using Oracles That Compute Values.
STACS
Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman
1992 A* conf
The Isomorphism Conjecture Holds Relative to an Oracle
FOCS
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1991 — conf
Gap-Definable Counting Classes.
SCT
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz
1991 — conf
Notions of Resource-Bounded Category and Genericity.
SCT
Stephen A. Fenner
1989 A* conf
Every Polynomial-Time 1-Degree Collapses iff P=PSPACE
FOCS
Stephen A. Fenner, Stuart A. Kurtz, James S. Royer