Publications and Manuscripts

Stephen Fenner

(Click here for unpublished manuscripts.)

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

  1. Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf. Bipartite Perfect Matching is in quasi-NC. Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), June 2016. ACM New York (2016), pages 754-763. arXiv:1601.06319.
  2. 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.
  3. 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.
  4. 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.
  5. Stephen Fenner. Functions that preserve p-randomness. Information and Computation. Volume 231 (2013), pages 125-142. This was one of the papers selected from the 18th International Symposium on Fundamentals of Computation Theory (Proceedings version: Springer LNCS Volume 6914 (2011), pages 336-347).
  6. 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.)
  7. 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.
  8. Stephen Fenner, William Gasarch, Brian Postow. The complexity of learning SUBSEQ(A). Journal of Symbolic Logic. Volume 74, Issue 3 (2009), pages 939-975.
  9. 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.)
  10. 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.
  11. 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.
  12. 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.
  13. 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. (PS,PDF)
  14. 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. (PS,PDF)
  15. 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. (PS,PDF)
  16. 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. (draft PS,PDF)
  17. 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. (PS,PDF)
  18. S. Fenner. PP-lowness and a simple definition of AWPP. Theory of Computing Systems. Volume 36 (2003) pages 199-212. (PS,PDF)
  19. 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. (PS,PDF)
  20. 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. (PS,PDF)
  21. 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. (PS,PDF)
  22. 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. (PS,PDF)
  23. 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. (PS,PDF)
  24. S. Fenner, M. Schaefer. Bounded immunity and btt-reductions. Mathematical Logic Quarterly. Volume 45 (1999), pages 3-21. (PS,PDF)
  25. 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: 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." (PS,PDF)
  26. 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. (PS,PDF)
  27. 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. (PS,PDF)
  28. 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. (PS,PDF)
  29. 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. (PS,PDF)
  30. 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. (PS,PDF)
  31. 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. (PS,PDF)
  32. S. Fenner. Almost weakly 2-generic sets. Journal of Symbolic Logic. Volume 59 (1994), pages 868-887. (PS,PDF)
  33. 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. (PS,PDF)
  34. 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. (PS,PDF)



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, Yong Zhang. Implementing fanout, parity, and Mod gates via spin exchange interactions. E-print archive quant-ph/0407125, 2004.

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

Stephen A. Fenner. Implementing the fanout gate by a Hamiltonian. E-print archive quant-ph/0309163, 2003.

Stephen A. Fenner, Yong Zhang. Universal quantum computation with two- and three-qubit projective measurements. E-print archive quant-ph/0111077, 2001.

Stephen A. Fenner. An intuitive Hamiltonian for quantum search. E-print archive quant-ph/0004091, 2000.

Stephen A. Fenner. Object-free categories. 2009.

S. Fenner, M. Schaefer. Simplicity and Strong Reductions. May 1998. (PS,PDF)

[Loading papers ...]



Back to my home page

Last updated Sunday August 28, 2016 at 15:02:27 EDT.