Stephen A. Fenner

Publication Activity (10 Years)

Years Active: 1989-2023
Publications (10 Years): 14

Top Topics

Pairwise Interactions

Correspondence Matching

Parallel Algorithm

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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