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