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.
