Every Polynomial-Time 1-Degree Collapses iff P=PSPACE - Stephen A. Fenner; Stuart A. Kurtz; James S. Royer (FOCS, 1989)

Notions of Resource-Bounded Category and Genericity. - Stephen A. Fenner (SCT, 1991)

An Oarcle Builder's Toolkit. - Stephen A. Fenner; Lance Fortnow; Stuart A. Kurtz; Lide Li (SCT, 1993)

On Using Oracles That Compute Values. - Stephen A. Fenner; Steven Homer; Mitsunori Ogiwara; Alan L. Selman (STACS, 1993)

Gap-Definable Counting Classes. - Stephen A. Fenner; Lance Fortnow; Stuart A. Kurtz (J. Comput. Syst. Sci., 1994)

Almost Weakly 2-Generic Sets. - Stephen A. Fenner (J. Symb. Log., 1994)

Inverting the Turing Jump in Complexity Theory. - Stephen A. Fenner (SCT, 1995)

Resource-Bounded Baire Category: A Stronger Approach. - Stephen A. Fenner (SCT, 1995)

Weakly Useful Sequences. - Stephen A. Fenner; Jack H. Lutz; Elvira Mayordomo (ICALP, 1995)

Beyond P^(NP) - NEXP. - Stephen A. Fenner; Lance Fortnow (STACS, 1995)

Gap-Definability as a Closure Property. - Stephen A. Fenner; Lance Fortnow; Lide Li (Inf. Comput., 1996)

The Isomorphism Conjecture Holds Relative to an Oracle. - Stephen A. Fenner; Lance Fortnow; Stuart A. Kurtz (SIAM J. Comput., 1996)

Complexity Theory Newsflash. - Stephen A. Fenner; Lance Fortnow; William I. Gasarch (SIGACT News, 1996)

Hyper-Polynomial Hierarchies and the NP-Jump. - Stephen A. Fenner; Steven Homer; Randall J. Pruim; Marcus Schaefer 001 (CCC, 1997)

Results on Resource-Bounded Measure. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow (ICALP, 1997)

Oracles that Compute Values. - Stephen A. Fenner; Steven Homer; Mitsunori Ogihara; Alan L. Selman (SIAM J. Comput., 1997)

Complements of Multivalued Functions. - Stephen A. Fenner; Frederic Green; Steven Homer; Alan L. Selman; Thomas Thierauf; Heribert Vollmer (Chic. J. Theor. Comput. Sci., 1999)

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy - Stephen A. Fenner; Frederic Green; Steven Homer; Randall J. Pruim (Electron. Colloquium Comput. Complex., 1999)

Bounded Immunity and Btt-Reductions. - Stephen A. Fenner; Marcus Schaefer 001 (Math. Log. Q., 1999)

Optimal Proof Systems and Sparse Sets. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow; Dieter van Melkebeek (STACS, 2000)

Two oracles that force a big crunch. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow; Leen Torenvliet (Comput. Complex., 2001)

Hyper-polynomial hierarchies and the polynomial jump. - Stephen A. Fenner; Steven Homer; Randall J. Pruim; Marcus Schaefer 001 (Theor. Comput. Sci., 2001)

Gales and supergales are equivalent for defining constructive Hausdorff dimension - Stephen A. Fenner (CoRR, 2002)

PP-lowness and a simple definition of AWPP - Stephen A. Fenner (Electron. Colloquium Comput. Complex., 2002)

A Physics-Free Introduction to the Quantum Computation Model - Stephen A. Fenner (CoRR, 2003)

A physics-free introduction to the quantum computation model, Computational Complexity Column. - Stephen A. Fenner (Bull. EATCS, 2003)

An oracle builder's toolkit. - Stephen A. Fenner; Lance Fortnow; Stuart A. Kurtz; Lide Li (Inf. Comput., 2003)

Inverting onto functions. - Stephen A. Fenner; Lance Fortnow; Ashish V. Naik; John D. Rogers (Inf. Comput., 2003)

Simplicity and Strong Reductions - Marcus Schaefer 001; Stephen A. Fenner (Electron. Colloquium Comput. Complex., 2004)

Every polynomial-time 1-degree collapses if and only if P = PSPACE. - Stephen A. Fenner; Stuart A. Kurtz; James S. Royer (J. Symb. Log., 2004)

Bounds on the Power of Constant-Depth Quantum Circuits. - Stephen A. Fenner; Frederic Green; Steven Homer; Yong Zhang 053 (FCT, 2005)

Weakly useful sequences. - Stephen A. Fenner; Jack H. Lutz; Elvira Mayordomo; Patrick Reardon (Inf. Comput., 2005)

The Complexity of Learning SUBSEQ (A). - Stephen A. Fenner; William I. Gasarch (ALT, 2006)

The central nature of the Hidden Subgroup problem - Stephen A. Fenner; Yong Zhang 053 (CoRR, 2006)

Quantum lower bounds for fanout. - M. Fang; Stephen A. Fenner; Frederic Green; Steven Homer; Yong Zhang 053 (Quantum Inf. Comput., 2006)

Universal Quantum Circuits. - Debajyoti Bera; Stephen A. Fenner; Frederic Green; Steven Homer (Electron. Colloquium Comput. Complex., 2008)

The complexity of learning SUBSEQ(A). - Stephen A. Fenner; William I. Gasarch; Brian Postow (J. Symb. Log., 2009)

The Complexity of Finding SUBSEQ(A). - Stephen A. Fenner; William I. Gasarch; Brian Postow (Theory Comput. Syst., 2009)

Efficient universal quantum circuits. - Debajyoti Bera; Stephen A. Fenner; Frederic Green; Steven Homer (Quantum Inf. Comput., 2010)

Monochromatic Boxes in Colored Grids. - Joshua N. Cooper; Stephen A. Fenner; Semmy Purewal (SIAM J. Discret. Math., 2011)

On Two-Level Poset Games. - Stephen A. Fenner; Rohit Gurjar; Arpita Korwar; Thomas Thierauf (Electron. Colloquium Comput. Complex., 2013)

Functions that preserve p-randomness. - Stephen A. Fenner (Inf. Comput., 2013)

On the Complexity of the Hidden Subgroup Problem. - Stephen A. Fenner; Yong Zhang 053 (Int. J. Found. Comput. Sci., 2013)

The complexity of some regex crossword problems. - Stephen A. Fenner (CoRR, 2014)

Combinatorial Game Complexity: An Introduction with Poset Games. - Stephen A. Fenner; John D. Rogers (Bull. EATCS, 2015)

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. - Stephen A. Fenner; Daniel Grier; Jochen Messner; Luke Schaeffer; Thomas Thierauf (Electron. Colloquium Comput. Complex., 2015)

Quantum Algorithms for a Set of Group Theoretic Problems. - Stephen A. Fenner; Yong Zhang 053 (Int. J. Found. Comput. Sci., 2015)

Compression Complexity. - Stephen A. Fenner; Lance Fortnow (CoRR, 2017)

Guest Column: Parallel Algorithms for Perfect Matching. - Stephen A. Fenner; Rohit Gurjar; Thomas Thierauf (SIGACT News, 2017)

Fixed-Parameter Extrapolation and Aperiodic Order: Open Problems. - Stephen A. Fenner; Frederic Green; Steven Homer (SIGACT News, 2018)

Complexity of Regex Crosswords. - Stephen A. Fenner; Daniel Padé (LATA, 2019)

A deterministic parallel algorithm for bipartite perfect matching. - Stephen A. Fenner; Rohit Gurjar; Thomas Thierauf (Commun. ACM, 2019)

Depth-2 QAC circuits cannot simulate quantum parity. - Daniel Padé; Stephen A. Fenner; Daniel Grier; Thomas Thierauf (CoRR, 2020)

Bipartite Perfect Matching is in Quasi-NC. - Stephen A. Fenner; Rohit Gurjar; Thomas Thierauf (SIAM J. Comput., 2021)

Review of The Theory of Quantum Information John Watrous. - Stephen A. Fenner (SIGACT News, 2021)

Remembrances of Alan. - Stephen A. Fenner (SIGACT News, 2021)

Implementing the fanout operation with simple pairwise interactions. - Stephen A. Fenner; Rabins Wosti (CoRR, 2022)

The complexity of regex crosswords. - Stephen A. Fenner; Daniel Padé; Thomas Thierauf (Inf. Comput., 2022)

The Complexity of Poset Games. - Stephen A. Fenner; Daniel Grier; Rohit Gurjar; Arpita Korwar; Thomas Thierauf (J. Graph Algorithms Appl., 2022)

Implementing the quantum fanout operation with simple pairwise interactions. - Stephen A. Fenner; Rabins Wosti (Quantum Inf. Comput., 2023)

Tight bounds on depth-2 QAC-circuits computing parity. - Stephen A. Fenner; Daniel Grier; Daniel Padé; Thomas Thierauf (CoRR, 2025)