Publications and Manuscripts

Stephen Fenner

(Click here for unpublished manuscripts.)

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. E-print archive quant-ph/0312208.

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. E-print archive quant-ph/0408150.

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. E-print archive quant-ph/0312209.

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)

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)

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.

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)

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)

S. Fenner. PP-lowness and a simple definition of AWPP. Theory of Computing Systems. Volume 36 (2003) pages 199-212. (PS,PDF)

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)

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)

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)

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)

S. Fenner, M. Schaefer. Bounded immunity and btt-reductions. Mathematical Logic Quarterly. Volume 45 (1999), pages 3-21. (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 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)

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

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)

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)

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)

S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, H. Vollmer. Complements of multivalued functions. Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, Philadelphia, PA, May 1996, pages 260-269. (PS,PDF)

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)

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)

S. Fenner. Almost weakly 2-generic sets. Journal of Symbolic Logic. Volume 59 (1994), pages 868-887. (PS,PDF)

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)

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)

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

Debajyoti Bera, Stephen A. Fenner, Frederic Green, and Steven Homer. Universal Quantum Circuits. February 2008.

Stephen A. Fenner. Godel'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.


Back to my home page

Last updated Wednesday March 19, 2008 at 7:3:15 EDT.