Algebraic methods for interactive proof systems C Lund, L Fortnow, H Karloff, N Nisan Journal of the ACM (JACM) 39 (4), 859-868, 1992 | 1175 | 1992 |
Non-deterministic exponential time has two-prover interactive protocols L Babai, L Fortnow, C Lund Computational complexity 1, 3-40, 1991 | 1064 | 1991 |
Checking computations in polylogarithmic time L Babai, L Fortnow, LA Levin, M Szegedy Proceedings of the twenty-third annual ACM symposium on Theory of computing …, 1991 | 870 | 1991 |
The status of the P versus NP problem L Fortnow Communications of the ACM 52 (9), 78-86, 2009 | 559 | 2009 |
Testing closeness of discrete distributions T Batu, L Fortnow, R Rubinfeld, WD Smith, P White Journal of the ACM (JACM) 60 (1), 1-25, 2013 | 486* | 2013 |
BPP has subexponential time simulations unlessEXPTIME has publishable proofs L Babai, L Fortnow, N Nisan, A Wigderson Computational Complexity 3 (4), 307-318, 1993 | 436 | 1993 |
On the power of multi-prover interactive protocols L Fortnow, J Rompel, M Sipser Theoretical Computer Science 134 (2), 545-557, 1994 | 425 | 1994 |
Infeasibility of instance compression and succinct PCPs for NP L Fortnow, R Santhanam Proceedings of the fortieth annual ACM symposium on Theory of computing, 133-142, 2008 | 376 | 2008 |
The complexity of perfect zero-knowledge L Fortnow Proceedings of the nineteenth annual ACM symposium on Theory of computing …, 1987 | 349 | 1987 |
Gap-definable counting classes SA Fenner, LJ Fortnow, SA Kurtz Journal of Computer and System Sciences 48 (1), 116-148, 1994 | 318 | 1994 |
Testing random variables for independence and identity T Batu, E Fischer, L Fortnow, R Kumar, R Rubinfeld, P White Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 442-451, 2001 | 267 | 2001 |
Random-self-reducibility of complete sets J Feigenbaum, L Fortnow SIAM Journal on Computing 22 (5), 994-1005, 1993 | 259 | 1993 |
Complexity limitations on quantum computation L Fortnow, J Rogers Journal of Computer and System Sciences 59 (2), 240-252, 1999 | 244 | 1999 |
Computational identification of operons in microbial genomes Y Zheng, JD Szustakowski, L Fortnow, RJ Roberts, S Kasif Genome research 12 (8), 1221-1230, 2002 | 199 | 2002 |
A short history of computational complexity L Fortnow, S Homer Bulletin of the EATCS 80 (01), 2003, 2003 | 184 | 2003 |
Gaming prediction markets: Equilibrium strategies with a market maker Y Chen, S Dimitrov, R Sami, DM Reeves, DM Pennock, RD Hanson, ... Algorithmica 58, 930-969, 2010 | 167* | 2010 |
The golden ticket: P, NP, and the search for the impossible L Fortnow Princeton University Press, 2013 | 153 | 2013 |
Arithmetization: A new method in structural complexity theory L Babai, L Fortnow computational complexity 1, 41-66, 1991 | 141* | 1991 |
Nonrelativizing separations H Buhrman, L Fortnow, T Thierauf Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity …, 1998 | 122 | 1998 |
Time–space tradeoffs for satisfiability L Fortnow Journal of Computer and System Sciences 60 (2), 337-353, 2000 | 120* | 2000 |