×

zbMATH — the first resource for mathematics

Fortnow, Lance J.

Compute Distance To:
Author ID: fortnow.lance-j Recent zbMATH articles by "Fortnow, Lance J."
Published as: Fortnow, Lance; Fortnow, Lance J.; Fortnow, L.
Documents Indexed: 120 Publications since 1988, including 2 Books
all top 5

Co-Authors

19 single-authored
22 Buhrman, Harry
10 Fenner, Stephen A.
7 Kurtz, Stuart A.
7 Rogers, John D.
7 Santhanam, Rahul
6 Lund, Carsten
6 Pavan, Aduri
5 Antunes, Luis
5 Beigel, Richard
5 Kummer, Martin
5 Newman, Ilan I.
5 Stephan, Frank
4 Babai, László
4 Feigenbaum, Joan
4 Gasarch, William Ian
4 Laplante, Sophie
4 Lutz, Jack H.
4 Torenvliet, Leen
4 van Melkebeek, Dieter
4 Vinodchandran, N. Variyam
3 Hitchcock, John M.
3 Klivans, Adam R.
3 Li, Lide
3 Rubinfeld, Ronitt
3 Sipser, Michael
2 Czumaj, Artur
2 Downey, Rodney Graham
2 Ergun, Funda
2 Freivalds, Rūsiņš Mārtiņš
2 Koucký, Michal
2 Magen, Avner
2 Mayordomo, Elvira
2 Naik, Ashish V.
2 Nisan, Noam
2 Pennock, David M.
2 Rohrig, Hein
2 Sami, Rahul
2 Sohler, Christian
2 Szegedy, Mario
2 Vereshchagin, Nikolai K.
2 Vereshchagin, Nikolay K.
2 Wang, Fengming
1 Batu, Tuğkan
1 Chang, Richard
1 Chen, Yiling
1 Dimitrov, Stanko
1 Fejer, Peter A.
1 Fenner, Steve
1 Fischer, Eldar
1 Goldsmith, Judy
1 Gonen, Rica
1 Grabowski, Piotr
1 Grochow, Joshua A.
1 Hanson, Robin D.
1 Homer, Steve
1 Homer, Steven
1 Impagliazzo, Russell
1 Jain, Sanjay
1 Kabanets, Valentine
1 Karloff, Howard J.
1 Kinber, Efim B.
1 Lee, Troy
1 Levy, Matthew A.
1 Lipton, Richard J.
1 Loff, Bruno
1 Longpré, Luc
1 Mahaney, Stephen R.
1 Muchnik, Andrej A.
1 Ogihara, Mitsunori
1 Pleszkovich, Mark
1 Reeves, Daniel M.
1 Reingold, Nick
1 Rompel, John
1 Selman, Alan L.
1 Sengupta, Samik
1 Slaman, Theodore A.
1 Smith, Carl H.
1 Smith, Warren D.
1 Solovay, Robert M.
1 Souto, André
1 Spielman, Daniel Alan
1 Thierauf, Thomas
1 Trevisan, Luca
1 Umans, Christopher
1 Viglas, Anastasios
1 Vohra, Rakesh V.
1 Whang, Duke
1 White, Patrick E.
1 Wigderson, Avi
1 Yamakami, Tomoyuki

Publications by Year

Citations contained in zbMATH Open

95 Publications have been cited 955 times in 675 Documents Cited by Year
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
90
1991
Algebraic methods for interactive proof systems. Zbl 0799.68097
Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam
80
1992
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
74
2011
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
49
1993
The complexity of forecast testing. Zbl 1160.91396
Fortnow, Lance; Vohra, Rakesh V.
45
2009
Gap-definable counting classes. Zbl 0802.68051
Fenner, Stephen A.; Fortnow, Lance J.; Kurtz, Stuart A.
43
1994
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133
Fortnow, Lance; Santhanam, Rahul
32
2008
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
22
1991
On the power of multi-prover interactive protocols. Zbl 0938.68824
Fortnow, Lance; Rompel, John; Sipser, Michael
22
1994
Resource-bounded Kolmogorov complexity revisited. Zbl 1017.68061
Buhrman, Harry; Fortnow, Lance; Laplante, Sophie
22
2002
Extremes in the degrees of inferability. Zbl 0813.03026
Fortnow, Lance; Gasarch, William; Jain, Sanjay; Kinber, Efim; Kummer, Martin; Kurtz, Stuart; Pleszkovich, Mark; Slaman, Theodore; Solovay, Robert; Stephan, Frank
20
1994
An oracle builder’s toolkit. Zbl 1025.68041
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide
20
2003
Random-self-reducibility of complete sets. Zbl 0789.68057
Feigenbaum, Joan; Fortnow, Lance
17
1993
Testing closeness of discrete distributions. Zbl 1281.68227
Batu, Tuğkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren D.; White, Patrick
17
2013
Are there interactive protocols for co-NP languages? Zbl 0668.68054
Fortnow, Lance; Sipser, Michael
16
1988
Nonrelativizing separations. Zbl 0935.68032
Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas
16
1998
PP is closed under truth-table reductions. Zbl 0851.68029
Fortnow, Lance; Reingold, Nick
16
1996
Time-space tradeoffs for satisfiability. Zbl 0955.68052
Fortnow, Lance
15
2000
Computational depth: Concept and applications. Zbl 1088.68073
Antunes, Luis; Fortnow, Lance; van Melkebeek, Dieter; Vinodchandran, N. V.
15
2006
Counting complexity. Zbl 0880.68039
Fortnow, Lance
14
1997
The role of relativization in complexity theory. Zbl 0791.68062
Fortnow, Lance
14
1994
Complexity limitations on quantum computation. Zbl 0947.68050
Fortnow, Lance; Rogers, John
13
1999
Approximating the weight of the Euclidean minimum spanning tree in sublinear time. Zbl 1086.68144
Czumaj, Artur; Ergün, Funda; Fortnow, Lance; Magen, Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler, Christian
12
2005
Extracting Kolmogorov complexity with applications to dimension zero-one laws. Zbl 1223.68060
Fortnow, Lance; Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V.; Wang, Fengming
11
2006
Time-space lower bounds for satisfiability. Zbl 1326.68148
Fortnow, Lance; Lipton, Richard; van Melkebeek, Dieter; Viglas, Anastasios
11
2005
Separability and one-way functions. Zbl 0953.68547
Fortnow, Lance; Rogers, John
10
1994
Inverting onto functions. Zbl 1058.68061
Fenner, Stephen A.; Fortnow, Lance; Naik, Ashish V.; Rogers, John D.
9
2003
Enumerations of the Kolmogorov function. Zbl 1165.03025
Beigel, Richard; Buhrman, Harry; Fejer, Peter; Fortnow, Lance; Grabowski, Piotr; Longpré, Luc; Muchnik, Andrej; Stephan, Frank; Torvenvliet, Leen
9
2006
One complexity theorist’s view of quantum computing. Zbl 1026.68056
Fortnow, Lance
8
2003
On the complexity of succinct zero-sum games. Zbl 1162.91302
Fortnow, Lance; Impagliazzo, Russell; Kabanets, Valentine; Umans, Christopher
8
2008
One-sided versus two-sided error in probabilistic computation. Zbl 0928.68052
Buhrman, Harry; Fortnow, Lance
7
1999
Efficient learning algorithms yield circuit lower bounds. Zbl 1162.68532
Fortnow, Lance; Klivans, Adam R.
7
2009
Separating complexity classes using autoreducibility. Zbl 0949.68068
Buhrman, Harry; Fortnow, Lance; van Melkebeek, Dieter; Torenvliet, Leen
7
2000
Uniformly hard languages. Zbl 1051.68091
Downey, Rod; Fortnow, Lance
7
2003
Gaming prediction markets: equilibrium strategies with a market maker. Zbl 1200.91120
Chen, Yiling; Dimitrov, Stanko; Sami, Rahul; Reeves, Daniel M.; Pennock, David M.; Hanson, Robin D.; Fortnow, Lance; Gonen, Rica
7
2010
Two queries. Zbl 0947.68064
Buhrman, Harry; Fortnow, Lance
6
1999
Proving SAT does not have small circuits with an application to the two queries problem. Zbl 1135.68022
Fortnow, Lance; Pavan, A.; Sengupta, Samik
6
2008
Complexity limitations on quantum computation. Zbl 0935.68042
Fortnow, Lance; Rogers, John
5
1998
The isomorphism conjecture holds relative to an oracle. Zbl 0841.68046
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.
5
1996
Relativized worlds with an infinite hierarchy. Zbl 1002.68060
Fortnow, Lance
5
1999
NP might not be as easy as detecting unique solutions. Zbl 1027.68607
Beigel, Richard; Buhrman, Harry; Fortnow, Lance
5
1998
Prediction and dimension. Zbl 1161.68490
Fortnow, Lance; Lutz, Jack H.
5
2005
Separability and one-way functions. Zbl 1137.68407
Fortnow, Lance; Rogers, John D.
5
2002
Quantum property testing. Zbl 1225.68088
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
5
2008
Sophistication revisited. Zbl 1175.68209
Antunes, Luís; Fortnow, Lance
5
2009
The isomorphism conjecture holds relative to an oracle. Zbl 0977.68541
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.
4
1992
Extracting Kolmogorov complexity with applications to dimension zero-one laws. Zbl 1215.68114
Fortnow, Lance; Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V.; Wang, Fengming
4
2011
Complexity classes of equivalence problems revisited. Zbl 1238.68061
Fortnow, Lance; Grochow, Joshua A.
4
2011
Interactive proof systems and alternating time-space complexity. Zbl 0777.68039
Fortnow, Lance; Lund, Carsten
4
1993
The power of adaptiveness and additional queries in random-self- reductions. Zbl 0808.68060
Feigenbaum, Joan; Fortnow, Lance; Lund, Carsten; Spielman, Daniel
4
1994
Generic separations. Zbl 0849.68035
Fortnow, Lance; Yamakami, Tomoyuki
4
1996
Computation in a distributed information market. Zbl 1079.68106
Feigenbaum, Joan; Fortnow, Lance; Pennock, David M.; Sami, Rahul
4
2005
Increasing Kolmogorov complexity. Zbl 1117.68039
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Vereshchagin, Nikolai
4
2005
On resource-bounded instance complexity. Zbl 0872.68044
Fortnow, Lance; Kummer, Martin
4
1996
Quantum property testing. Zbl 1092.68615
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
4
2003
Unconditional lower bounds against advice. Zbl 1248.68212
Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul
4
2009
Robust simulations and significant separations. Zbl 1333.68118
Fortnow, Lance; Santhanam, Rahul
4
2011
On the relative sizes of learnable sets. Zbl 0902.68159
Fortnow, Lance; Freivalds, Rūsiņš; Gasarch, William I.; Kummer, Martin; Kurtz, Stuart A.
3
1998
Addendum to: Non-deterministic exponential time has two-prower interactive protocols. Zbl 0796.68096
Babai, L.; Fortnow, L.; Lund, C.
3
1992
Optimal proof systems and sparse sets. Zbl 0962.68071
Buhrman, Harry; Fenner, Steve; Fortnow, Lance; van Melkebeek, Dieter
3
2000
Diagonalization. Zbl 0973.68086
Fortnow, Lance
3
2000
Prediction and dimension. Zbl 1050.68061
Fortnow, Lance; Lutz, Jack H.
3
2002
Does the polynomial hierarchy collapse if onto functions are invertible? Zbl 1183.68296
Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay
3
2010
A simple proof of Toda’s theorem. Zbl 1213.68292
Fortnow, Lance
3
2009
New non-uniform lower bounds for uniform classes. Zbl 1380.68196
Fortnow, Lance; Santhanam, Rahul
3
2016
L-printable sets. Zbl 0915.68067
Fortnow, Lance; Goldsmith, Judy; Levy, Matthew A.; Mahaney, Stephen
2
1998
Some results on derandomization. Zbl 1035.68052
Buhrman, Harry; Fortnow, Lance; Pavan, A.
2
2003
One bit of advice. Zbl 1035.68051
Buhrman, Harry; Chang, Richard; Fortnow, Lance
2
2003
One complexity theorist’s view of quantum computing. Zbl 0967.68078
Fortnow, Lance
2
2000
Gap-definability as a closure property. Zbl 0876.68045
Fenner, Stephen; Fortnow, Lance; Li, Lide
2
1996
Efficient learning algorithms yield circuit lower bounds. Zbl 1143.68415
Fortnow, Lance; Klivans, Adam R.
2
2006
Infinitely-often autoreducible sets. Zbl 1205.68161
Beigel, Richard; Fortnow, Lance; Stephan, Frank
2
2003
Hierarchies for semantic classes (extended abstract). Zbl 1192.68292
Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca
2
2005
Tolerant versus intolerant testing for Boolean properties. Zbl 1213.68414
Fischer, Eldar; Fortnow, Lance
2
2006
Inseparability and strong hypotheses for disjoint NP pairs. Zbl 1230.68079
Fortnow, Lance; Lutz, Jack H.; Mayordomo, Elvira
2
2010
On coherence, random-self-reducibility, and self-correction. Zbl 0917.68074
Feigenbaum, Joan; Fortnow, Lance; Laplante, Sophie; Naik, Ashish
2
1998
Optimality and domination in repeated games with bounded players. Zbl 1345.91001
Fortnow, Lance; Whang, Duke
2
1994
Robust simulations and significant separations. Zbl 1376.68049
Fortnow, Lance; Santhanam, Rahul
2
2017
Low-depth witnesses are easy to find. Zbl 1283.68169
Antunes, Luís; Fortnow, Lance; Pinto, Alexandre; Souto, André
2
2012
The golden ticket. P, NP, and the search for the impossible. Zbl 1267.68003
Fortnow, Lance
2
2013
Results on resource-bounded measure. Zbl 1401.68087
Buhrman, Harry; Fenner, Stephen; Fortnow, Lance
2
1997
Nearly optimal language compression using extractors. Zbl 0894.68080
Fortnow, Lance; Laplante, Sophie
1
1998
Using autoreducibility to separate complexity classes. Zbl 0938.68667
Buhrman, Harry; Fortnow, Lance; Torenvliet, Leen
1
1995
Two queries. Zbl 0935.68033
Buhrman, Harry; Fortnow, Lance
1
1998
Circuit lower bounds à la Kolmogorov. Zbl 1096.68632
Fortnow, Lance; Laplante, Sophie
1
1995
On the power of two-local random reductions. Zbl 0795.68076
Fortnow, Lance; Szegedy, Mario
1
1992
Gap-definability as a closure property. Zbl 0822.68031
Fenner, Stephen; Fortnow, Lance; Li, Lide
1
1993
Kolmogorov complexity and computational complexity. Zbl 1083.68052
Fortnow, Lance
1
2004
Sublinear-time approximation of Euclidean minimum spanning tree. Zbl 1092.68622
Czumaj, Artur; Ergün, Funda; Fortnow, Lance; Magen, Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler, Christian
1
2003
Linear advice for randomized logarithmic space. Zbl 1136.68404
Fortnow, Lance; Klivans, Adam R.
1
2006
Inverting onto functions and polynomial hierarchy. Zbl 1188.68144
Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay
1
2007
Using depth to capture average-case complexity. Zbl 1278.68091
Antunes, Luís; Fortnow, Lance; Vinodchandran, N. V.
1
2003
Beyond {NP}: the work and legacy of Larry Stockmeyer. Zbl 1192.68003
Fortnow, Lance
1
2005
A short history of computational complexity. Zbl 1169.68429
Fortnow, Lance; Homer, Steve
1
2003
Nondeterministic separations. Zbl 1459.68075
Fortnow, Lance
1
2015
Robust simulations and significant separations. Zbl 1376.68049
Fortnow, Lance; Santhanam, Rahul
2
2017
New non-uniform lower bounds for uniform classes. Zbl 1380.68196
Fortnow, Lance; Santhanam, Rahul
3
2016
Nondeterministic separations. Zbl 1459.68075
Fortnow, Lance
1
2015
Testing closeness of discrete distributions. Zbl 1281.68227
Batu, Tuğkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren D.; White, Patrick
17
2013
The golden ticket. P, NP, and the search for the impossible. Zbl 1267.68003
Fortnow, Lance
2
2013
Low-depth witnesses are easy to find. Zbl 1283.68169
Antunes, Luís; Fortnow, Lance; Pinto, Alexandre; Souto, André
2
2012
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
74
2011
Extracting Kolmogorov complexity with applications to dimension zero-one laws. Zbl 1215.68114
Fortnow, Lance; Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V.; Wang, Fengming
4
2011
Complexity classes of equivalence problems revisited. Zbl 1238.68061
Fortnow, Lance; Grochow, Joshua A.
4
2011
Robust simulations and significant separations. Zbl 1333.68118
Fortnow, Lance; Santhanam, Rahul
4
2011
Gaming prediction markets: equilibrium strategies with a market maker. Zbl 1200.91120
Chen, Yiling; Dimitrov, Stanko; Sami, Rahul; Reeves, Daniel M.; Pennock, David M.; Hanson, Robin D.; Fortnow, Lance; Gonen, Rica
7
2010
Does the polynomial hierarchy collapse if onto functions are invertible? Zbl 1183.68296
Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay
3
2010
Inseparability and strong hypotheses for disjoint NP pairs. Zbl 1230.68079
Fortnow, Lance; Lutz, Jack H.; Mayordomo, Elvira
2
2010
The complexity of forecast testing. Zbl 1160.91396
Fortnow, Lance; Vohra, Rakesh V.
45
2009
Efficient learning algorithms yield circuit lower bounds. Zbl 1162.68532
Fortnow, Lance; Klivans, Adam R.
7
2009
Sophistication revisited. Zbl 1175.68209
Antunes, Luís; Fortnow, Lance
5
2009
Unconditional lower bounds against advice. Zbl 1248.68212
Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul
4
2009
A simple proof of Toda’s theorem. Zbl 1213.68292
Fortnow, Lance
3
2009
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133
Fortnow, Lance; Santhanam, Rahul
32
2008
On the complexity of succinct zero-sum games. Zbl 1162.91302
Fortnow, Lance; Impagliazzo, Russell; Kabanets, Valentine; Umans, Christopher
8
2008
Proving SAT does not have small circuits with an application to the two queries problem. Zbl 1135.68022
Fortnow, Lance; Pavan, A.; Sengupta, Samik
6
2008
Quantum property testing. Zbl 1225.68088
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
5
2008
Inverting onto functions and polynomial hierarchy. Zbl 1188.68144
Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay
1
2007
Computational depth: Concept and applications. Zbl 1088.68073
Antunes, Luis; Fortnow, Lance; van Melkebeek, Dieter; Vinodchandran, N. V.
15
2006
Extracting Kolmogorov complexity with applications to dimension zero-one laws. Zbl 1223.68060
Fortnow, Lance; Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V.; Wang, Fengming
11
2006
Enumerations of the Kolmogorov function. Zbl 1165.03025
Beigel, Richard; Buhrman, Harry; Fejer, Peter; Fortnow, Lance; Grabowski, Piotr; Longpré, Luc; Muchnik, Andrej; Stephan, Frank; Torvenvliet, Leen
9
2006
Efficient learning algorithms yield circuit lower bounds. Zbl 1143.68415
Fortnow, Lance; Klivans, Adam R.
2
2006
Tolerant versus intolerant testing for Boolean properties. Zbl 1213.68414
Fischer, Eldar; Fortnow, Lance
2
2006
Linear advice for randomized logarithmic space. Zbl 1136.68404
Fortnow, Lance; Klivans, Adam R.
1
2006
Approximating the weight of the Euclidean minimum spanning tree in sublinear time. Zbl 1086.68144
Czumaj, Artur; Ergün, Funda; Fortnow, Lance; Magen, Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler, Christian
12
2005
Time-space lower bounds for satisfiability. Zbl 1326.68148
Fortnow, Lance; Lipton, Richard; van Melkebeek, Dieter; Viglas, Anastasios
11
2005
Prediction and dimension. Zbl 1161.68490
Fortnow, Lance; Lutz, Jack H.
5
2005
Computation in a distributed information market. Zbl 1079.68106
Feigenbaum, Joan; Fortnow, Lance; Pennock, David M.; Sami, Rahul
4
2005
Increasing Kolmogorov complexity. Zbl 1117.68039
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Vereshchagin, Nikolai
4
2005
Hierarchies for semantic classes (extended abstract). Zbl 1192.68292
Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca
2
2005
Beyond {NP}: the work and legacy of Larry Stockmeyer. Zbl 1192.68003
Fortnow, Lance
1
2005
Kolmogorov complexity and computational complexity. Zbl 1083.68052
Fortnow, Lance
1
2004
An oracle builder’s toolkit. Zbl 1025.68041
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide
20
2003
Inverting onto functions. Zbl 1058.68061
Fenner, Stephen A.; Fortnow, Lance; Naik, Ashish V.; Rogers, John D.
9
2003
One complexity theorist’s view of quantum computing. Zbl 1026.68056
Fortnow, Lance
8
2003
Uniformly hard languages. Zbl 1051.68091
Downey, Rod; Fortnow, Lance
7
2003
Quantum property testing. Zbl 1092.68615
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
4
2003
Some results on derandomization. Zbl 1035.68052
Buhrman, Harry; Fortnow, Lance; Pavan, A.
2
2003
One bit of advice. Zbl 1035.68051
Buhrman, Harry; Chang, Richard; Fortnow, Lance
2
2003
Infinitely-often autoreducible sets. Zbl 1205.68161
Beigel, Richard; Fortnow, Lance; Stephan, Frank
2
2003
Sublinear-time approximation of Euclidean minimum spanning tree. Zbl 1092.68622
Czumaj, Artur; Ergün, Funda; Fortnow, Lance; Magen, Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler, Christian
1
2003
Using depth to capture average-case complexity. Zbl 1278.68091
Antunes, Luís; Fortnow, Lance; Vinodchandran, N. V.
1
2003
A short history of computational complexity. Zbl 1169.68429
Fortnow, Lance; Homer, Steve
1
2003
Resource-bounded Kolmogorov complexity revisited. Zbl 1017.68061
Buhrman, Harry; Fortnow, Lance; Laplante, Sophie
22
2002
Separability and one-way functions. Zbl 1137.68407
Fortnow, Lance; Rogers, John D.
5
2002
Prediction and dimension. Zbl 1050.68061
Fortnow, Lance; Lutz, Jack H.
3
2002
Time-space tradeoffs for satisfiability. Zbl 0955.68052
Fortnow, Lance
15
2000
Separating complexity classes using autoreducibility. Zbl 0949.68068
Buhrman, Harry; Fortnow, Lance; van Melkebeek, Dieter; Torenvliet, Leen
7
2000
Optimal proof systems and sparse sets. Zbl 0962.68071
Buhrman, Harry; Fenner, Steve; Fortnow, Lance; van Melkebeek, Dieter
3
2000
Diagonalization. Zbl 0973.68086
Fortnow, Lance
3
2000
One complexity theorist’s view of quantum computing. Zbl 0967.68078
Fortnow, Lance
2
2000
Complexity limitations on quantum computation. Zbl 0947.68050
Fortnow, Lance; Rogers, John
13
1999
One-sided versus two-sided error in probabilistic computation. Zbl 0928.68052
Buhrman, Harry; Fortnow, Lance
7
1999
Two queries. Zbl 0947.68064
Buhrman, Harry; Fortnow, Lance
6
1999
Relativized worlds with an infinite hierarchy. Zbl 1002.68060
Fortnow, Lance
5
1999
Nonrelativizing separations. Zbl 0935.68032
Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas
16
1998
Complexity limitations on quantum computation. Zbl 0935.68042
Fortnow, Lance; Rogers, John
5
1998
NP might not be as easy as detecting unique solutions. Zbl 1027.68607
Beigel, Richard; Buhrman, Harry; Fortnow, Lance
5
1998
On the relative sizes of learnable sets. Zbl 0902.68159
Fortnow, Lance; Freivalds, Rūsiņš; Gasarch, William I.; Kummer, Martin; Kurtz, Stuart A.
3
1998
L-printable sets. Zbl 0915.68067
Fortnow, Lance; Goldsmith, Judy; Levy, Matthew A.; Mahaney, Stephen
2
1998
On coherence, random-self-reducibility, and self-correction. Zbl 0917.68074
Feigenbaum, Joan; Fortnow, Lance; Laplante, Sophie; Naik, Ashish
2
1998
Nearly optimal language compression using extractors. Zbl 0894.68080
Fortnow, Lance; Laplante, Sophie
1
1998
Two queries. Zbl 0935.68033
Buhrman, Harry; Fortnow, Lance
1
1998
Counting complexity. Zbl 0880.68039
Fortnow, Lance
14
1997
Results on resource-bounded measure. Zbl 1401.68087
Buhrman, Harry; Fenner, Stephen; Fortnow, Lance
2
1997
PP is closed under truth-table reductions. Zbl 0851.68029
Fortnow, Lance; Reingold, Nick
16
1996
The isomorphism conjecture holds relative to an oracle. Zbl 0841.68046
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.
5
1996
Generic separations. Zbl 0849.68035
Fortnow, Lance; Yamakami, Tomoyuki
4
1996
On resource-bounded instance complexity. Zbl 0872.68044
Fortnow, Lance; Kummer, Martin
4
1996
Gap-definability as a closure property. Zbl 0876.68045
Fenner, Stephen; Fortnow, Lance; Li, Lide
2
1996
Using autoreducibility to separate complexity classes. Zbl 0938.68667
Buhrman, Harry; Fortnow, Lance; Torenvliet, Leen
1
1995
Circuit lower bounds à la Kolmogorov. Zbl 1096.68632
Fortnow, Lance; Laplante, Sophie
1
1995
Gap-definable counting classes. Zbl 0802.68051
Fenner, Stephen A.; Fortnow, Lance J.; Kurtz, Stuart A.
43
1994
On the power of multi-prover interactive protocols. Zbl 0938.68824
Fortnow, Lance; Rompel, John; Sipser, Michael
22
1994
Extremes in the degrees of inferability. Zbl 0813.03026
Fortnow, Lance; Gasarch, William; Jain, Sanjay; Kinber, Efim; Kummer, Martin; Kurtz, Stuart; Pleszkovich, Mark; Slaman, Theodore; Solovay, Robert; Stephan, Frank
20
1994
The role of relativization in complexity theory. Zbl 0791.68062
Fortnow, Lance
14
1994
Separability and one-way functions. Zbl 0953.68547
Fortnow, Lance; Rogers, John
10
1994
The power of adaptiveness and additional queries in random-self- reductions. Zbl 0808.68060
Feigenbaum, Joan; Fortnow, Lance; Lund, Carsten; Spielman, Daniel
4
1994
Optimality and domination in repeated games with bounded players. Zbl 1345.91001
Fortnow, Lance; Whang, Duke
2
1994
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
49
1993
Random-self-reducibility of complete sets. Zbl 0789.68057
Feigenbaum, Joan; Fortnow, Lance
17
1993
Interactive proof systems and alternating time-space complexity. Zbl 0777.68039
Fortnow, Lance; Lund, Carsten
4
1993
Gap-definability as a closure property. Zbl 0822.68031
Fenner, Stephen; Fortnow, Lance; Li, Lide
1
1993
Algebraic methods for interactive proof systems. Zbl 0799.68097
Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam
80
1992
The isomorphism conjecture holds relative to an oracle. Zbl 0977.68541
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.
4
1992
Addendum to: Non-deterministic exponential time has two-prower interactive protocols. Zbl 0796.68096
Babai, L.; Fortnow, L.; Lund, C.
3
1992
On the power of two-local random reductions. Zbl 0795.68076
Fortnow, Lance; Szegedy, Mario
1
1992
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
90
1991
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
22
1991
Are there interactive protocols for co-NP languages? Zbl 0668.68054
Fortnow, Lance; Sipser, Michael
16
1988
all top 5

Cited by 865 Authors

32 Fortnow, Lance J.
18 Hemaspaandra, Lane A.
17 Stephan, Frank
16 Saurabh, Saket
15 Allender, Eric W.
15 Kratsch, Stefan
13 Jansen, Bart M. P.
12 Hitchcock, John M.
11 Arvind, Vikraman
11 Goldreich, Oded
11 Jain, Sanjay
11 van Melkebeek, Dieter
11 Vinodchandran, N. Variyam
10 Buhrman, Harry
10 Cygan, Marek
10 Köbler, Johannes
9 Pavan, Aduri
9 Williams, Richard Ryan
9 Zimand, Marius
8 Glaßer, Christian
8 Lokshtanov, Daniel
8 Pilipczuk, Marcin
8 Pilipczuk, Michał
8 Rubinfeld, Ronitt
8 Shaltiel, Ronen
8 Wigderson, Avi
7 Beigel, Richard
7 Bodlaender, Hans L.
7 Cai, Jin-Yi
7 Chiesa, Alessandro
7 Downey, Rodney Graham
7 Hermelin, Danny
7 Kabanets, Valentine
7 Misra, Neeldhara
7 Rothe, Jörg-Matthias
7 Sudan, Madhu
7 Vidick, Thomas
7 Yamakami, Tomoyuki
6 Agrawal, Manindra
6 Antunes, Luis
6 Babai, László
6 Fellows, Michael Ralph
6 Raman, Venkatesh
6 Shen, Alexander
6 Wahlström, Magnus
6 Watanabe, Osamu
5 Fomin, Fedor V.
5 Impagliazzo, Russell
5 Moser, Philippe
5 Müller, Moritz
5 Musatov, Daniil
5 Niedermeier, Rolf
5 Ogihara, Mitsunori
5 Raz, Ran
5 Ron, Dana
5 Santhanam, Rahul
5 Selman, Alan L.
5 Souto, André
5 Spakowski, Holger
5 Vereshchagin, Nikolay K.
5 Vollmer, Heribert
4 Chang, Richard
4 Chen, Yijia
4 Chen, Yiling
4 Feigenbaum, Joan
4 Fenner, Stephen A.
4 Flum, Jörg
4 Grochow, Joshua A.
4 Gur, Tom
4 Heggernes, Pinar
4 Kinber, Efim B.
4 Le Gall, François
4 Lipton, Richard J.
4 Lund, Carsten
4 Nishimura, Harumichi
4 Ogiwara, Mitsunori
4 Ramanujan, M. S.
4 Rogers, John D.
4 Romashchenko, Andrei
4 Rothblum, Guy N.
4 Rothblum, Ron D.
4 Sau, Ignasi
4 Seshadhri, Comandur
4 Sohler, Christian
4 Szeider, Stefan
4 Teutsch, Jason
4 Torenvliet, Leen
4 Van Leeuwen, Erik Jan
4 Wagner, Klaus W.
4 Zuckerman, David
3 Ambainis, Andris
3 Artemenko, Sergei
3 Atserias, Albert
3 Bellare, Mihir
3 Ben-Sasson, Eli
3 Beyersdorff, Olaf
3 Bhattacharyya, Arnab
3 Bienvenu, Laurent
3 Blum, Manuel
3 Bredereck, Robert
...and 765 more Authors
all top 5

Cited in 86 Serials

89 Theoretical Computer Science
74 Journal of Computer and System Sciences
49 Computational Complexity
36 Algorithmica
36 Information and Computation
27 Theory of Computing Systems
24 Information Processing Letters
24 SIAM Journal on Computing
9 Annals of Pure and Applied Logic
9 ACM Transactions on Computation Theory
8 International Journal of Foundations of Computer Science
7 Mathematical Systems Theory
5 Discrete Applied Mathematics
5 SIAM Journal on Discrete Mathematics
4 The Journal of Symbolic Logic
4 Journal of Combinatorial Optimization
3 Artificial Intelligence
3 Communications in Mathematical Physics
3 The Annals of Statistics
3 Journal of Economic Theory
3 Transactions of the American Mathematical Society
3 Random Structures & Algorithms
3 Combinatorics, Probability and Computing
3 Journal of Mathematical Sciences (New York)
3 Journal of the ACM
3 Computer Science Review
2 Discrete Mathematics
2 Combinatorica
2 The Annals of Applied Probability
2 Bulletin of the American Mathematical Society. New Series
2 Archive for Mathematical Logic
2 Mathematical Logic Quarterly (MLQ)
2 Economic Theory
2 The Bulletin of Symbolic Logic
2 Quantum Information Processing
2 Discrete Optimization
1 Problems of Information Transmission
1 Reports on Mathematical Physics
1 Chaos, Solitons and Fractals
1 Bulletin of the Polish Academy of Sciences. Technical Sciences
1 Acta Mathematica
1 Advances in Mathematics
1 Applied Mathematics and Computation
1 Computing
1 Journal of Statistical Planning and Inference
1 Mathematics of Operations Research
1 European Journal of Combinatorics
1 Advances in Applied Mathematics
1 Journal of Complexity
1 Journal of Computer Science and Technology
1 Journal of Automated Reasoning
1 International Journal of Approximate Reasoning
1 Journal of Cryptology
1 Annals of Operations Research
1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
1 Japan Journal of Industrial and Applied Mathematics
1 International Journal of Computational Geometry & Applications
1 Computational Geometry
1 Games and Economic Behavior
1 RAIRO. Informatique Théorique et Applications
1 Mathematical Programming. Series A. Series B
1 SIAM Journal on Optimization
1 Annals of Mathematics and Artificial Intelligence
1 Parallel Algorithms and Applications
1 Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
1 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
1 New Journal of Physics
1 LMS Journal of Computation and Mathematics
1 RAIRO. Theoretical Informatics and Applications
1 Electronic Commerce Research
1 Entropy
1 Natural Computing
1 International Journal of Quantum Information
1 International Journal of Parallel, Emergent and Distributed Systems
1 Optimization Letters
1 Journal of Mathematical Cryptology
1 Journal of Physics A: Mathematical and Theoretical
1 Logical Methods in Computer Science
1 Discrete Mathematics, Algorithms and Applications
1 Studies in History and Philosophy of Science. Part B. Studies in History and Philosophy of Modern Physics
1 Cryptography and Communications
1 Theory of Computing
1 Decision Analysis
1 Journal of Theoretical Biology
1 Forum of Mathematics, Sigma
1 European Journal of Mathematics

Citations by Year