Fenner

Professor Fenner's research interests are in the core theoretical foundations of computing computability and computational complexity, especially quantum computing and information. Computability theory studies the ultimate limits of what is computable and has close connections to logic and the foundations of mathematics. Computational complexity theory studies the limits of efficient computation. It compares different models of computation (such as deterministic, randomized, and quantum computation), categorizes computational problems according to their inherent difficulty, and shows how the structure of a problem relates to its complexity. Computability and complexity theory are mathematical disciplines that inform almost all other areas of computer science, especially algorithms, cryptography and security, and communications. Professor Fenner's other interests include combinatorics, computational algebra, physics of computation, and cryptography and security.
Education

• Ph. D., University of Chicago(1991)
• M. S., University of Chicago (1988)
• B. A. (Physics), Harvard (1983)

Selected Publications

• S. Fenner, W. Gasarch, B. Postow, "The complexity of learning SUBSEQ(A)," Journal of Symbolic Logic, to appear.
• M. Fang, S. Fenner, F. Green, S. Homer, Y. Zhang, "Quantum lower bounds for fanout," Quantum Information and Computation, 6(2006), 46-57. quant-ph/0312208.
• S. Fenner, J. Lutz, E. Mayordomo, P. Reardon, "Weakly useful sequences," Information and Computation, 197(2005), 41-54.
• S. Fenner, S. Kurtz, J. Royer, "Every polynomial-time 1-degree collapses if and only if P = PSPACE," Journal of Symbolic Logic, 69(2004), 713-741.
• S. Fenner, L. Fortnow, A. Naik, J. Rogers, "Inverting onto functions," Information and Computation 186(2003), 90-103.
• H. Buhrman, S. Fenner, L. Fortnow, L. Torenvliet, "Two oracles that force a big crunch," Computational Complexity, 10(2001) 93-116.
• 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 455(1999), 3953-3966. quant-ph/9812056.