Lance Fortnow

Cited by

	All	Since 2019
Citations	11861	2782
h-index	48	24
i10-index	112	53

520

260

130

390

1990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202467 116 114 144 214 191 171 212 242 245 177 202 169 307 305 328 342 379 374 362 463 460 450 473 462 421 475 467 448 493 505 434 461 505 384

Public access

View all

12 articles

0 articles

available

not available

Based on funding mandates

Co-authors

Harry BuhrmanChief Scientist Q Algorithms @ Quantinuum, Professor Univ. of Amsterdam & Founding Director QuSoftVerified email at quantinuum.com
Rahul SanthanamUniversity of OxfordVerified email at cs.ox.ac.uk
Laszlo BabaiUniversity of ChicagoVerified email at cs.uchicago.edu
Stephen FennerProfessor of Computer Science and Engineering, University of South CarolinaVerified email at cec.sc.edu
Stuart KurtzProfessor of Computer Science, The University of ChicagoVerified email at cs.uchicago.edu
Ronitt RubinfeldProfessor of Computer Science, MIT and Tel Aviv UniversityVerified email at csail.mit.edu
Noam NisanProfessor of Computer Science, Hebrew University of JerusalemVerified email at cs.huji.ac.il
Richard BeigelTemple UniversityVerified email at temple.edu
John RogersAssociate Professor, DePaul UniversityVerified email at depaul.edu
David M PennockProfessor, Rutgers UniversityVerified email at dimacs.rutgers.edu
Joan FeigenbaumGrace Murray Hopper Professor of Computer Science, Yale UniversityVerified email at yale.edu
Luís AntunesPorto UniversityVerified email at dcc.fc.up.pt
Pavan AduriIowa State UniversityVerified email at cs.iastate.edu
Mario SzegedyProfessor of Computer Science, Rutgers UniversityVerified email at cs.rutgers.edu
Ilan NewmanProfessor of Computer Science, University of HaifaVerified email at cs.haifa.ac.il
Tugkan BatuDepartment of Mathematics, London School of EconomicsVerified email at lse.ac.uk
Yiling ChenHarvard UniversityVerified email at seas.harvard.edu
Sophie LaplanteIRIF, Université Paris CitéVerified email at irif.fr
Frank StephanNational University of Singapore, Department of Mathematics and Department of Computer ScienceVerified email at comp.nus.edu.sg
Leen TorenvlietILLC University of Amsterdam (retired)Verified email at uva.nl

Lance Fortnow

Illinois Institute of Technology

Verified email at iit.edu - Homepage

Computational Complexity


Title Sort by citations Sort by year Sort by title	Cited by Cited by	Year
Algebraic methods for interactive proof systems C Lund, L Fortnow, H Karloff, N Nisan Journal of the ACM (JACM) 39 (4), 859-868, 1992	1144	1992
Non-deterministic exponential time has two-prover interactive protocols L Babai, L Fortnow, C Lund Computational complexity 1, 3-40, 1991	1045	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	853	1991
The status of the P versus NP problem L Fortnow Communications of the ACM 52 (9), 78-86, 2009	543	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	477*	2013
BPP has subexponential time simulations unless EXPTIME has publishable proofs L aszl o Babai, L Fortnow, N Nisan, A Wigderson Computational Complexity 3 (4), 307-318, 1993	431	1993
On the power of multi-prover interactive protocols L Fortnow, J Rompel, M Sipser Theoretical Computer Science 134 (2), 545-557, 1994	421	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	372	2008
The complexity of perfect zero-knowledge L Fortnow Proceedings of the nineteenth annual ACM symposium on Theory of computing …, 1987	347	1987
Gap-definable counting classes SA Fenner, LJ Fortnow, SA Kurtz Journal of Computer and System Sciences 48 (1), 116-148, 1994	316	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	260	2001
Random-self-reducibility of complete sets J Feigenbaum, L Fortnow SIAM Journal on Computing 22 (5), 994-1005, 1993	251	1993
Complexity limitations on quantum computation L Fortnow, J Rogers Journal of Computer and System Sciences 59 (2), 240-252, 1999	243	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	197	2002
A short history of computational complexity L Fortnow, S Homer Bulletin of the EATCS 80 (01), 2003, 2003	182	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	151	2013
Arithmetization: A new method in structural complexity theory L Babai, L Fortnow computational complexity 1, 41-66, 1991	140*	1991
Nonrelativizing separations H Buhrman, L Fortnow, T Thierauf Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity …, 1998	121	1998
Are there interactive protocols for co-NP languages? L Fortnow, M Sipser Information Processing Letters 28 (5), 249-251, 1988	120	1988

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow

Cited by

Co-authors