Publications and Manuscripts

Stephen Fenner

(Click here for unpublished manuscripts.)

(Click here for articles posted to arXiv.org.)

  1. S. Fenner, R. Wosti. Implementing the quantum fanout operation with simple pairwise interactions. Quantum Information and Computation. Volume 23(13&14), 2023. pp 1081-1090.
  2. 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.
  3. 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 1-14.
  4. 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. 109-115.
  5. Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf. Bipartite Perfect Matching is in quasi-NC. 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).
  6. Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf. Game values and computational complexity: An analysis via black-white combinatorial games. Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), December 2015. Springer LNCS 9472 (2015), pages 689-699. ECCC TR15-021.
  7. 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.
  8. 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 1221-1234. (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 70-81 2008.) arXiv:cs/0610086.
  9. Stephen Fenner. Functions that preserve p-randomness. Information and Computation. Volume 231 (2013), pages 125-142. Special Issue: Selected Papers of the 18th International Symposium on Fundamentals of Computation Theory (Proceedings version: Springer LNCS Volume 6914 (2011), pages 336-347).
  10. Joshua Cooper, Stephen Fenner, Semmy Purewal. Monochromatic boxes in colored grids. SIAM Journal on Discrete Mathematics. Volume 25, Issue 3 (2011), pages 1054-1068. (An earlier draft is at arXiv.org.)
  11. Debajyoti Bera, Stephen Fenner, Frederic Green, Steven Homer. Efficient universal quantum circuits. Quantum Information and Computation. Volume 10, Nos. 1&2 (2010), pages 16-27. arXiv:0804.2429.
  12. Stephen Fenner, William Gasarch, Brian Postow. The complexity of learning SUBSEQ(A). Journal of Symbolic Logic. Volume 74, Issue 3 (2009), pages 939-975.
  13. Stephen Fenner, William Gasarch, Brian Postow. The complexity of finding SUBSEQ(A). Theory of Computing Systems. Volume 45, Issue 3 (2009), pages 577-612. (Here is a version with two appendices added.)
  14. Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang. Quantum lower bounds for fanout. Quantum Information and Computation. Volume 6 (2006), pages 46-57. arXiv:quant-ph/0312208.
  15. Yong Zhang, Stephen Fenner. Quantum algorithms for a set of group theoretic problems. Proceedings of the Ninth IC-EATCS Italian Conference on Theoretical Computer Science, Siena, Italy, October 2005. Springer LNCS 3701, pages 215-227. arXiv:quant-ph/0408150.
  16. Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang. Bounds on the power of constant-depth quantum circuits. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory, Luebeck, Germany, August 2005. Springer LNCS 3623, pages 44-55. arXiv:quant-ph/0312209.
  17. S. A. Fenner, J. H. Lutz, E. Mayordomo, P. Reardon. Weakly useful sequences. Information and Computation. Volume 197 (2005), pages 41-54. 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 393-404.
  18. S. Fenner, S. Kurtz, J. Royer. Every polynomial-time 1-degree collapses if and only if P = PSPACE. Journal of Symbolic Logic. Volume 69 (2004), pages 713-741. 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 624-29.
  19. S. A. Fenner. A Physics-Free 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 125-145. An earlier version appeared in the Bulletin of the European Association for Theoretical Computer Science, 2003. arXiv:cs/0304008
  20. S. Fenner, L. Fortnow, A. Naik, J. Rogers. Inverting onto functions. Information and Computation. Volume 186 (2003), pages 90-103. An earlier version appeared in Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, Philadelphia, PA, May 1996, pages 213-222.
  21. S. Fenner, L. Fortnow, S. Kurtz, L. Li. An oracle builder's toolkit. Information and Computation. Volume 182 (2003), pages 95-136. An earlier version appeared in Proceedings of the Eighth Annual IEEE Conference on Structure in Complexity Theory, San Diego, CA, May 1993, pages 120-131.
  22. S. Fenner. PP-lowness and a simple definition of AWPP. Theory of Computing Systems. Volume 36 (2003) pages 199-212.
  23. 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 171-219.
  24. H. Buhrman, S. Fenner, L. Fortnow, L. Torenvliet. Two oracles that force a big crunch. Computational Complexity. Volume 10 (2001) pages 93-116. Also appeared as S. Fenner, L. Fortnow. Beyond PNP = NEXP. Proceedings of the 12th Annual GI/AFCET Symposium on Theoretical Aspects of Computer Science, Munich, Germany, March 1995, pages 619-627.
  25. S. Fenner, S. Homer, M. Schaefer, R. Pruim. Hyper-polynomial hierarchies and the polynomial jump. Theoretical Computer Science. Volume 262 (2001), pages 241-256. This is the journal submission version. Also appeared in Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 1997, pages 102-110.
  26. 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 407-418.
  27. 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 260-269.
  28. S. Fenner, M. Schaefer. Bounded immunity and btt-reductions. Mathematical Logic Quarterly. Volume 45 (1999), pages 3-21. (PS,PDF)
  29. 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 3953-3966. E-print archive: arXiv:quant-ph/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."
  30. S. Fenner, S. Homer, M. Ogihara, A. Selman. Oracles that compute values. SIAM Journal on Computing. Volume 26 (1997), pages 1043-1065. Also appeared in Proceedings of the 10th Annual GI/AFCET Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 1993, pages 398-407.
  31. H. Buhrman, S. Fenner, L. Fortnow. Results on resource-bounded measure. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming, volume 1256 of Lecture Notes in Computer Science, pages 188-194. Springer, 1997.
  32. S. Fenner, L. Fortnow, L. Li. Gap-definability as a closure property. Information and Computation. Volume 130 (1996), pages 1-17. Also appeared in Proceedings of the 10th Annual GI/AFCET Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 1993, pages 484-493.
  33. 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 102-110.
  34. S. Fenner, L. Fortnow, S. Kurtz. The isomorphism conjecture holds relative to an oracle. SIAM Journal on Computing. Volume 25 (1996), pages 193-206. Also appeared in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, October 1992, pages 30-39.
  35. S. Fenner. Resource-bounded 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 182-192.
  36. S. Fenner. Almost weakly 2-generic sets. Journal of Symbolic Logic. Volume 59 (1994), pages 868-887.
  37. S. Fenner, L. Fortnow, S. Kurtz. Gap-definable 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. 116-148. Also appeared in Proceedings of the Sixth Annual IEEE Conference on Structure in Complexity Theory, Chicago, IL, July 1991, pages 30-42.
  38. S. Fenner. Notions of resource-bounded category and genericity (proceedings submission version). Proceedings of the Sixth Annual IEEE Conference on Structure in Complexity Theory, Chicago, IL, July 1991, pages 196-212.


Papers on arXiv.org not listed above

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 C-SIGN 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. Fixed-Parameter 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:quant-ph/0407125, 2004.

Stephen A. Fenner, Yong Zhang. A note on the classical lower bound for a quantum walk algorithm. arXiv:quant-ph/0312230, 2003.

Stephen A. Fenner. Implementing the fanout gate by a Hamiltonian. arXiv:quant-ph/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 three-qubit projective measurements. arXiv:quant-ph/0111077, 2001.

Stephen A. Fenner. An intuitive Hamiltonian for quantum search. arXiv:quant-ph/0004091, 2000.


Unpublished Manuscripts

Here are miscellaneous drafts. Some are formal papers, some are informal write-ups 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. Object-free 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.