Lance Fortnow
Lance Fortnow
School of Computer Science, Georgia Institute of Technology
Email verificata su - Home page
TitoloCitata daAnno
Non-deterministic exponential time has two-prover interactive protocols
L Babai, L Fortnow, C Lund
Computational complexity 1 (1), 3-40, 1991
Algebraic methods for interactive proof systems
C Lund, L Fortnow, H Karloff, N Nisan
Journal of the ACM (JACM) 39 (4), 859-868, 1992
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
On the power of multi-prover interactive protocols
L Fortnow, J Rompel, M Sipser
Theoretical Computer Science 134 (2), 545-557, 1994
BPP has subexponential time simulations unless EXPTIME has publishable proofs
L Babai, L Fortnow, N Nisan, A Wigderson
[1991] Proceedings of the Sixth Annual Structure in Complexity Theory …, 1991
The status of the P versus NP problem
L Fortnow
Communications of the ACM 52 (9), 78-86, 2009
Testing closeness of discrete distributions
T Batu, L Fortnow, R Rubinfeld, WD Smith, P White
Journal of the ACM (JACM) 60 (1), 4, 2013
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Journal of Computer and System Sciences 77 (1), 91-106, 2011
The complexity of perfect zero-knowledge
L Fortnow
Proceedings of the nineteenth annual ACM symposium on Theory of computing …, 1987
Gap-definable counting classes
SA Fenner, LJ Fortnow, SA Kurtz
Journal of Computer and System Sciences 48 (1), 116-148, 1994
Complexity limitations on quantum computation
L Fortnow, J Rogers
Journal of Computer and System Sciences 59 (2), 240-252, 1999
Random-self-reducibility of complete sets
J Feigenbaum, L Fortnow
SIAM Journal on Computing 22 (5), 994-1005, 1993
Computational identification of operons in microbial genomes
Y Zheng, JD Szustakowski, L Fortnow, RJ Roberts, S Kasif
Genome research 12 (8), 1221-1230, 2002
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
Gaming prediction markets: Equilibrium strategies with a market maker
Y Chen, S Dimitrov, R Sami, DM Reeves, DM Pennock, RD Hanson, ...
Algorithmica 58 (4), 930-969, 2010
A short history of computational complexity
L Fortnow, S Homer
Boston University Computer Science Department, 2003
Arithmetization: A new method in structural complexity theory
L Babai, L Fortnow
Computational Complexity 1 (1), 41-66, 1991
Time–space tradeoffs for satisfiability
L Fortnow
Journal of Computer and System Sciences 60 (2), 337-353, 2000
PP is closed under truth-table reductions
L Fortnow, N Reingold
[1991] Proceedings of the Sixth Annual Structure in Complexity Theory …, 1991
An oracle builder’s toolkit
S Fenner, L Fortnow, SA Kurtz, L Li
Information and Computation 182 (2), 95-136, 2003
Il sistema al momento non può eseguire l'operazione. Riprova più tardi.
Articoli 1–20