Publications and Manuscripts
Stephen Fenner
(Click here for unpublished manuscripts.)
(Click here for articles posted to arXiv.org.)

S. Fenner, R. Wosti. Implementing the quantum fanout operation with simple pairwise interactions. Quantum Information and Computation. Volume 23(13&14), 2023. pp 10811090.

Stephen Fenner, Daniel Pade, Thomas Thierauf.
The complexity
of regex crosswords. Information and Computation. Volume 286
(2022), 104777. Special Issue: Selected Papers of the 13th
International Conference on Language and Automata Theory and
Applications, LATA 2019.

Stephen A. Fenner, Daniel Grier, Rohit Gurjar, Arpita Korwar, Thomas
Thierauf. The
complexity of poset games. Journal of Graph
Algorithms and Applications. Volume 26(1), 2022. Pages 114.

Stephen Fenner, Rohit Gurjar, Thomas Thierauf.
A deterministic
parallel algorithm for bipartite perfect matching.
Communications of the ACM (Research Highlights section), Volume
62(3), March 2019, pp. 109115.

Stephen A. Fenner, Rohit Gurjar, Thomas
Thierauf. Bipartite
Perfect Matching is in quasiNC. SIAM Journal on
Computing. Volume 50(3), 2021, doi:10.1137/16M1097870. Special
issue of selected papers from the 48th Annual ACM SIGACT Symposium
on Theory of Computing (STOC '16).

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas
Thierauf. Game
values and computational complexity: An analysis via
blackwhite combinatorial games. Proceedings of the 26th International
Symposium on Algorithms and Computation (ISAAC), December 2015. Springer
LNCS 9472 (2015), pages 689699.
ECCC TR15021.

Stephen A. Fenner, John Rogers.
Combinatorial
Game Complexity: An Introduction with Poset Games.
Invited
article in the Bulletin of the European Association for Theoretical
Computer Science (EATCS) (The Computational Complexity Column  Yuri Gurevich,
ed.). Number 116, June 2015. An extended version is at
arXiv:1505.07416.

Stephen Fenner, Yong Zhang.
On the complexity of the
Hidden Subgroup problem. International Journal of Foundations of
Computer Science. Volume 24, Number 8 (2013), pages 12211234. (An
earlier version appeared in Proceedings of the 5th Annual Conference on
Theory and Applications of Models of Computation, Xi'an, China,
April 2008. Springer LNCS 4978, pages 7081 2008.)
arXiv:cs/0610086.

Stephen Fenner. Functions that preserve
prandomness.
Information and Computation. Volume 231 (2013), pages 125142.
Special Issue: Selected Papers of the 18th International Symposium
on Fundamentals of Computation Theory (Proceedings version: Springer
LNCS Volume 6914 (2011), pages 336347).

Joshua Cooper, Stephen Fenner, Semmy Purewal.
Monochromatic boxes in colored grids.
SIAM Journal on Discrete Mathematics. Volume 25, Issue 3 (2011),
pages 10541068. (An earlier draft is at
arXiv.org.)

Debajyoti Bera, Stephen Fenner, Frederic Green, Steven Homer.
Efficient universal
quantum circuits.
Quantum Information and Computation. Volume 10, Nos. 1&2
(2010), pages 1627.
arXiv:0804.2429.

Stephen Fenner, William Gasarch, Brian Postow.
The complexity of learning
SUBSEQ(A). Journal of Symbolic Logic. Volume 74, Issue 3
(2009), pages 939975.

Stephen Fenner, William Gasarch, Brian Postow.
The complexity of finding
SUBSEQ(A). Theory of Computing Systems. Volume 45, Issue 3
(2009), pages 577612. (Here is a
version with two
appendices added.)

Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, Yong
Zhang. Quantum
lower bounds for fanout. Quantum
Information and Computation. Volume 6 (2006), pages 4657.
arXiv:quantph/0312208.

Yong Zhang, Stephen Fenner.
Quantum algorithms
for a set of group
theoretic problems. Proceedings of the Ninth ICEATCS
Italian Conference on Theoretical Computer Science, Siena, Italy,
October 2005. Springer LNCS 3701, pages 215227.
arXiv:quantph/0408150.

Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang.
Bounds
on the power of constantdepth quantum circuits. Proceedings of
the 15th International Symposium on Fundamentals of Computation Theory,
Luebeck, Germany, August 2005. Springer LNCS 3623, pages 4455.
arXiv:quantph/0312209.

S. A. Fenner, J. H. Lutz, E. Mayordomo, P. Reardon.
Weakly useful
sequences. Information and Computation. Volume 197 (2005),
pages 4154. An earlier version appeared with authors Fenner, Lutz,
and Mayordomo in Proceedings of the 22nd EATCS International
Colloquium on Automata, Languages, and Programming, Szeged, Hungary,
July 1995, Springer LNCS 944, pages 393404.

S. Fenner, S. Kurtz, J. Royer. Every
polynomialtime 1degree collapses if and only if P = PSPACE.
Journal of Symbolic Logic. Volume 69 (2004), pages 713741.
Significantly expanded from a version that appeared in Proceedings
of the 30th Annual IEEE Symposium on Foundations of Computer Science,
Research Triangle Park, NC, October 1989, pages 62429.

S. A. Fenner. A
PhysicsFree Introduction to the Quantum Computation
Model. In Current Trends in Theoretical Computer Science: The
Challenge of the New Century, G. Paun, G. Rozenberg, A. Salomaa, eds.
Volume 1 (Algorithms and Complexity). World Scientific, 2004, pages
125145. An earlier version appeared in the Bulletin of the European
Association for Theoretical Computer Science, 2003.
arXiv:cs/0304008

S. Fenner, L. Fortnow, A. Naik, J. Rogers.
Inverting onto functions. Information and Computation.
Volume 186 (2003), pages 90103. An earlier version appeared in
Proceedings of the Eleventh Annual IEEE Conference on
Computational Complexity, Philadelphia, PA, May 1996, pages 213222.

S. Fenner, L. Fortnow, S. Kurtz, L. Li.
An oracle builder's toolkit.
Information and Computation. Volume 182 (2003), pages 95136.
An earlier version appeared in Proceedings of
the Eighth Annual IEEE Conference on Structure in
Complexity Theory, San Diego, CA, May 1993, pages 120131.

S. Fenner. PPlowness and a simple definition of AWPP.
Theory of Computing Systems. Volume 36 (2003) pages 199212.

S. Fenner. Counting Complexity and Quantum Computation. Draft of
chapter 8 in Mathematics of Quantum Computation, R. K. Brylinski
and G. Chen, eds. CRC Press, 2002, pages 171219.

H. Buhrman, S. Fenner, L. Fortnow, L. Torenvliet.
Two oracles that force a big
crunch. Computational Complexity. Volume 10 (2001) pages
93116. Also appeared as S. Fenner, L. Fortnow. Beyond
P^{NP} = NEXP. Proceedings of the 12th Annual GI/AFCET
Symposium on Theoretical Aspects of Computer Science, Munich, Germany,
March 1995, pages 619627.

S. Fenner, S. Homer, M. Schaefer, R. Pruim.
Hyperpolynomial hierarchies and the
polynomial jump. Theoretical Computer Science. Volume
262 (2001), pages 241256. This is the journal submission version.
Also appeared in Proceedings of the Twelfth Annual IEEE Conference
on Computational Complexity, Ulm, Germany, June 1997, pages
102110.

H. Buhrman, S. Fenner, L. Fortnow, D. van Melkebeek.
Optimal proof
systems and sparse sets. Proceedings of the 17th Annual GI/AFCET
Symposium on Theoretical Aspects of Computer Science, Lille, France,
February 2000. Lecture Notes in Computer Science, volume 1770 (2000),
Springer, Berlin, pages 407418.

S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, H. Vollmer.
Complements of multivalued functions.
Chicago Journal of
Theoretical Computer Science. Volume 1999(3) (1999). A previous
version appeared in
Proceedings of the Eleventh Annual IEEE Conference on Computational
Complexity, Philadelphia, PA, May 1996, pages 260269.

S. Fenner, M. Schaefer.
Bounded immunity and
bttreductions. Mathematical Logic Quarterly. Volume 45
(1999), pages 321. (PS,PDF)

S. Fenner, F. Green, S. Homer, R. Pruim.
Determining acceptance
possibility for a quantum computation is hard for the polynomial
hierarchy. Proceedings of the Royal Society, London A
(1999) Volume 455, pages 39533966. Eprint archive:
arXiv:quantph/9812056. Appeared earlier in Proceedings of the Sixth
Italian Conference on Theoretical Computer Science, November 1998
as "Quantum NP is hard for the polynomial hierarchy."

S. Fenner, S. Homer, M. Ogihara, A. Selman.
Oracles that compute values. SIAM
Journal on Computing. Volume 26 (1997), pages 10431065. Also
appeared in Proceedings of the 10th Annual GI/AFCET Symposium on
Theoretical Aspects of Computer Science, Würzburg, Germany,
February 1993, pages 398407.

H. Buhrman, S. Fenner, L. Fortnow.
Results on resourcebounded
measure. In Proceedings of the 24th International Colloquium on
Automata, Languages and Programming, volume 1256 of Lecture Notes in
Computer Science, pages 188194. Springer, 1997.

S. Fenner, L. Fortnow, L. Li.
Gapdefinability as a closure property.
Information and Computation. Volume 130 (1996), pages 117.
Also appeared in Proceedings of the 10th Annual GI/AFCET Symposium
on Theoretical Aspects of Computer Science, Würzburg,
Germany, February 1993, pages 484493.

S. Fenner. Inverting the Turing jump in
complexity theory. Proceedings of the Tenth Annual IEEE Conference
on Structure in Complexity Theory, Minneapolis, MN, June 1995, pages
102110.

S. Fenner, L. Fortnow, S. Kurtz. The
isomorphism conjecture holds relative to an oracle. SIAM Journal on
Computing. Volume 25 (1996), pages 193206. Also appeared in
Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer
Science, Pittsburgh, PA, October 1992, pages 3039.

S. Fenner. Resourcebounded Baire
category: A stronger approach. Journal Draft. An earlier
version appeared in Proceedings of the Tenth Annual IEEE Conference on
Structure in Complexity Theory, Minneapolis, MN, June 1995, pages
182192.

S. Fenner. Almost weakly 2generic
sets. Journal of Symbolic Logic. Volume 59 (1994), pages
868887.

S. Fenner, L. Fortnow, S. Kurtz.
Gapdefinable counting classes.
Journal of Computer and System Sciences, special issue of best
papers from the 1991 IEEE Conference on Structure in Complexity
Theory. Volume 48 (1994), pp. 116148. Also appeared in
Proceedings of the Sixth Annual IEEE Conference on Structure in
Complexity Theory, Chicago, IL, July 1991, pages 3042.

S. Fenner. Notions of resourcebounded
category and genericity (proceedings submission version).
Proceedings of the Sixth Annual IEEE Conference on Structure in
Complexity Theory, Chicago, IL, July 1991, pages 196212.
Stephen Fenner, Rabins Wosti. Implementing the fanout operation
with simple pairwise interactions. arXiv:2203.01141, 2022.
Stephen A. Fenner. A note on the entangling properties of the
CSIGN and related quantum gates.
arXiv:1910.01175, 2019.
Stephen Fenner, Lance Fortnow. Compression Complexity.
arXiv:1702.04779, 2017.
Stephen A. Fenner. The complexity of some regex crossword problems.
arXiv:1411.5437, 2014.
Stephen Fenner, Frederic Green, Steven Homer. FixedParameter Extrapolation and Aperiodic Order.
arXiv:1212.2889, 2012.
Stephen Fenner, William Gasarch. A Statement in Combinatorics that is Independent of ZFC (an exposition).
arXiv:1201.1207, 2012.
Stephen Fenner, William Gasarch, Charles Glover, Semmy Purewal. Rectangle Free Coloring of Grids.
arXiv:1005.3750, 2010.
S. A. Fenner, Y. Zhang. The central nature of the Hidden Subgroup problem.
arXiv:cs/0610086, 2006.
Stephen A. Fenner, Yong Zhang. Implementing fanout, parity, and Mod
gates via spin exchange interactions.
arXiv:quantph/0407125,
2004.
Stephen A. Fenner, Yong Zhang. A note on the classical lower bound
for a quantum walk algorithm.
arXiv:quantph/0312230,
2003.
Stephen A. Fenner. Implementing the fanout gate by a
Hamiltonian.
arXiv:quantph/0309163,
2003.
Stephen A. Fenner. Gales and supergales are equivalent for
defining constructive Hausdorff dimension.
arXiv:cs/0208044, 2002.
Stephen A. Fenner, Yong Zhang. Universal quantum computation with
two and threequbit projective measurements.
arXiv:quantph/0111077,
2001.
Stephen A. Fenner. An intuitive Hamiltonian for quantum search.
arXiv:quantph/0004091,
2000.
Here are miscellaneous drafts. Some are formal papers, some are
informal writeups of known results for the purposes of
exposition/pedagogy.
Stephen A. Fenner. Gödel's
Incompleteness Theorem for Computer Users. Pedagogical exposition.
October 2003; revised November 2007.
Stephen A. Fenner.
Objectfree categories.
2009.
S. Fenner, M. Schaefer.
Simplicity and Strong Reductions. May 1998.
(PS,PDF)
Back to my home page
Last updated Sunday June 9, 2024 at 15:26:49 EDT.