Photo

Lance Fortnow

Former Faculty
Department of Computer Science

Contact Information

No longer at the University of Chicago.

Office:
Phone:
Fax:
lance@fortnow.com

Personal Homepage

http://lance.fortnow.com

Technical Reports

TR-98-05
One-sided Versus Two-sided Randomness. Fortnow, Lance; Buhrman, Harry. 4 May, 1998.
TR-98-03
Relativized Worlds with an Infinite Hierarchy. Fortnow, L.. 20 March, 1998.
TR-97-11
Nonrelativizing Separations. Thierauf, Thomas; Fortnow, Lance; Buhrman, Harry. 10 September, 1997.
TR-97-02
NP Might Not Be As Easy As Detecting Unique Solution. Fortnow, L.; Buhrman, H.; Beigel, R.. 28 April, 1997.
TR-96-25
Extractors for Kolmogorov Complexity. Laplante, S.; Fortnow, L.. 4 December, 1996.
TR-96-24
Nondeterministic Polynomial Time versus Nondeterministic Logartithmic Space. Fortnow, Lance. 4 December, 1996.
TR-96-20
Two Queries. Fortnow, L; Buhrman, H.. 25 September, 1996.
TR-96-16
Two Results on Resource-Bounded Measure. Fortnow, L.; Fenner, S.; Buhrman, Harry. 30 August, 1996.
TR-96-12
Uniformly Hard Languages. Fortnow, L.; Downey, R.. 10 May, 1996.
TR-95-11
Distinguishing Complexity and Symmetry of Information. Fortnow, Lance; Buhrman, Harry. 8 November, 1995.
TR-95-07
Easy Sets Without Easy Small Subsets. Fortnow, Lance. 21 August, 1995.
TR-95-05
On Inverting Onto Functions. Rogers, John D.; Naik, Ashish V.; Fortnow, Lance; Fenner, Stephen A.. 8 June, 1995.
TR-95-04
Using Autoreducibility to Separate Complex Classes. Torenvliet, Leen; Fortnow, Lance; Buhrman, Harry. 26 April, 1995.
TR-95-01
Measure, Category and Learning Theory. Stephan, Frank; Smith, Carl; Kurtz, Stuart A.; Kummer, Martin; Gasarch, William I.; Freivalds, Rusins; Fortnow, Lance. 6 January, 1995. Communicated by Stuart Kurtz.
TR-94-21
Beating A Finite Automaton in the Big Match. Kimmel, Peter; Fortnow, Lance. 23 November, 1994.
TR-94-19
A note on adaptiveness and advice in coherence. Laplante, Sophie; Fortnow, Lance. 21 November, 1994.
TR-94-14
Beyond P^NP = NEXP. Fortnow, Lance; Fenner, Stephen. 9 August, 1994.
TR-94-09
Resource-Bounded Instance Complexity. Kammer, Martin; Fortnow, Lance. 7 June, 1994.
TR-94-01
Optimality and Domination in Repeated Games. Whang, Duke; Fortnow, Lance. 20 April, 1994.
TR-93-16
Optimality and Domination in Repeated Games with Bounded Players. Whang, Duke; Fortnow, Lance. 15 November, 1993.
TR-93-14
Separability and One-way Functions. Rogers, John; Fortnow, Lance. 30 August, 1993.
TR-93-08
A Generic Separation. Fortnow, Lance. 21 July, 1993.
TR-92-26
An Oracle Builder's Toolkit. Li, Lide; Kurtz, Stuart A.; Fortnow, Lance; Fenner, Stephen. 21 December, 1992. Communicated by Stuart Kurtz.
TR-92-25
Oracles, Proofs and Checking. Fortnow, Lance. 21 December, 1992.
TR-92-13
Gap-Definability as a Closure Property. Li, Lide; Fortnow, Lance; Fenner, Stephen. 17 August, 1992.
TR-92-08
An Oracle to which the Isomorphism Conjecture Holds. Kurtz, Stuart A.; Fortnow, Lance; Fenner, Stephen. 28 April, 1992. Communicated by Stuart Kurtz.
TR-91-30
Gap-Definable Counting Classes. Kurtz, Stuart; Fortnow, Lance; Fenner, Steve. 22 November, 1991. Communicated by Stuart Kurtz.
TR-91-10
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. Lund, Carsten; Fortnow, Lance; Babai, Laszlo. 5 April, 1991. Communicated by Laszlo Babai.
TR-91-09
Arithmetization: A New Method in Structural Complexity Theory. Fortnow, Lance; Babai, Laszlo. 5 April, 1991. Communicated by Laszlo Babai.
TR-91-08
Checking Computations in Polylogarithmic Time. Szegedy, Mario; Levin, Leonid A.; Fortnow, Lance; Babai, Laszlo. 22 March, 1991. Communicated by Laszlo Babai.
TR-91-06
Checking Computations in Polylogarithmic Time. Szegedy, Mario; Levin, Leonid A.; Fortnow, Lance; Babai, Laszlo. 7 March, 1991. Communicated by Laszlo Babai.
TR-90-32
Gap-definable counting classes. Kurtz, Stuart; Fortnow, Lance; Fenner, Steve. 7 November, 1990. Communicated by Stuart Kurtz.
TR-90-30
PP is Closed Under Truth-Table Reductions. Reingold, Nick; Fortnow, Lance. 25 September, 1990.
TR-90-22
On the Random-Self-Reducibility of Complete Sets. Fortnow, Lance; Feigenbaum, Joan. 20 August, 1990.
TR-90-16
Algebraic Methods for Interactive Proof Systems. Nisan, Noam; Karloff, Howard; Fortnow, Lance; Lund, Carsten. 30 April, 1990.
TR-90-14
BPP has Weak Subexponential Time Simulations unless EXPTIME has Publishable Proofs. Wigderson, Avi; Nisan, Noam; Fortnow, Lance; Babai, Laszlo. 23 April, 1990. Communicated by Laszlo Babai.
TR-90-11
Interactive Proof Systems and Alternating Time-Space Complexity. Lund, Carsten; Fortnow, Lance. 22 March, 1990.