×

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, L.; Fortnow, Lance; Fortnow, Lance J.
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 Santhanam, Rahul
6 Lund, Carsten
6 Pavan, Aduri
6 Rogers, John D.
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 Pinto, Alexandre Miranda
1 Pleszkovich, Mark
1 Reeves, Daniel M.
1 Reingold, Nick
1 Rogers, John H.
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

96 Publications have been cited 953 times in 663 Documents Cited by Year
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
94
1991
Algebraic methods for interactive proof systems. Zbl 0799.68097
Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam
76
1992
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
69
2011
Gap-definable counting classes. Zbl 0802.68051
Fenner, Stephen A.; Fortnow, Lance J.; Kurtz, Stuart A.
48
1994
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
47
1993
The complexity of forecast testing. Zbl 1160.91396
Fortnow, Lance; Vohra, Rakesh V.
45
2009
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133
Fortnow, Lance; Santhanam, Rahul
32
2008
On the power of multi-prover interactive protocols. Zbl 0938.68824
Fortnow, Lance; Rompel, John; Sipser, Michael
24
1994
Resource-bounded Kolmogorov complexity revisited. Zbl 1017.68061
Buhrman, Harry; Fortnow, Lance; Laplante, Sophie
23
2002
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
22
1991
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
18
2003
PP is closed under truth-table reductions. Zbl 0851.68029
Fortnow, Lance; Reingold, Nick
17
1996
Time-space tradeoffs for satisfiability. Zbl 0955.68052
Fortnow, Lance
16
2000
Nonrelativizing separations. Zbl 0935.68032
Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas
16
1998
Random-self-reducibility of complete sets. Zbl 0789.68057
Feigenbaum, Joan; Fortnow, Lance
16
1993
Computational depth: Concept and applications. Zbl 1088.68073
Antunes, Luis; Fortnow, Lance; van Melkebeek, Dieter; Vinodchandran, N. V.
15
2006
Are there interactive protocols for co-NP languages? Zbl 0668.68054
Fortnow, Lance; Sipser, Michael
15
1988
Counting complexity. Zbl 0880.68039
Fortnow, Lance
14
1997
Testing closeness of discrete distributions. Zbl 1281.68227
Batu, Tuğkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren D.; White, Patrick
12
2013
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
The role of relativization in complexity theory. Zbl 0791.68062
Fortnow, Lance
12
1994
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
Inverting onto functions. Zbl 1058.68061
Fenner, Stephen A.; Fortnow, Lance; Naik, Ashish V.; Rogers, John D.
11
2003
Complexity limitations on quantum computation. Zbl 0947.68050
Fortnow, Lance; Rogers, John
11
1999
On the complexity of succinct zero-sum games. Zbl 1162.91302
Fortnow, Lance; Impagliazzo, Russell; Kabanets, Valentine; Umans, Christopher
10
2008
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
10
2006
Separability and one-way functions. Zbl 0953.68547
Fortnow, Lance; Rogers, John
10
1994
One complexity theorist’s view of quantum computing. Zbl 1026.68056
Fortnow, Lance
8
2003
Efficient learning algorithms yield circuit lower bounds. Zbl 1162.68532
Fortnow, Lance; Klivans, Adam R.
7
2009
Uniformly hard languages. Zbl 1051.68091
Downey, Rod; Fortnow, Lance
7
2003
Separating complexity classes using autoreducibility. Zbl 0949.68068
Buhrman, Harry; Fortnow, Lance; van Melkebeek, Dieter; Torenvliet, Leen
7
2000
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
6
2010
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
Prediction and dimension. Zbl 1161.68490
Fortnow, Lance; Lutz, Jack H.
6
2005
Two queries. Zbl 0947.68064
Buhrman, Harry; Fortnow, Lance
6
1999
One-sided versus two-sided error in probabilistic computation. Zbl 0928.68052
Buhrman, Harry; Fortnow, Lance
6
1999
Sophistication revisited. Zbl 1175.68209
Antunes, Luís; Fortnow, Lance
5
2009
Quantum property testing. Zbl 1225.68088
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
5
2008
Computation in a distributed information market. Zbl 1079.68106
Feigenbaum, Joan; Fortnow, Lance; Pennock, David M.; Sami, Rahul
5
2005
Separability and one-way functions. Zbl 1137.68407
Fortnow, Lance; Rogers, John D.
5
2002
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
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
New non-uniform lower bounds for uniform classes. Zbl 1380.68196
Fortnow, Lance; Santhanam, Rahul
4
2016
Robust simulations and significant separations. Zbl 1333.68118
Fortnow, Lance; Santhanam, Rahul
4
2011
Complexity classes of equivalence problems revisited. Zbl 1238.68061
Fortnow, Lance; Grochow, Joshua A.
4
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
Unconditional lower bounds against advice. Zbl 1248.68212
Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul
4
2009
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
Generic separations. Zbl 0849.68035
Fortnow, Lance; Yamakami, Tomoyuki
4
1996
The power of adaptiveness and additional queries in random-self- reductions. Zbl 0808.68060
Feigenbaum, Joan; Fortnow, Lance; Lund, Carsten; Spielman, Daniel
4
1994
Interactive proof systems and alternating time-space complexity. Zbl 0777.68039
Fortnow, Lance; Lund, Carsten
4
1993
The isomorphism conjecture holds relative to an oracle. Zbl 0977.68541
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.
4
1992
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
Prediction and dimension. Zbl 1050.68061
Fortnow, Lance; Lutz, Jack H.
3
2002
Diagonalization. Zbl 0973.68086
Fortnow, Lance
3
2000
Optimal proof systems and sparse sets. Zbl 0962.68071
Buhrman, Harry; Fenner, Steve; Fortnow, Lance; van Melkebeek, Dieter
3
2000
Retraction of “Probabilistic computation and linear time”. Zbl 0967.68500
Fortnow, Lance; Sipser, Michael
3
1999
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
Robust simulations and significant separations. Zbl 1376.68049
Fortnow, Lance; Santhanam, Rahul
2
2017
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
Inseparability and strong hypotheses for disjoint NP pairs. Zbl 1230.68079
Fortnow, Lance; Lutz, Jack H.; Mayordomo, Elvira
2
2010
Tolerant versus intolerant testing for Boolean properties. Zbl 1213.68414
Fischer, Eldar; Fortnow, Lance
2
2006
Efficient learning algorithms yield circuit lower bounds. Zbl 1143.68415
Fortnow, Lance; Klivans, Adam R.
2
2006
Hierarchies for semantic classes (extended abstract). Zbl 1192.68292
Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca
2
2005
Infinitely-often autoreducible sets. Zbl 1205.68161
Beigel, Richard; Fortnow, Lance; Stephan, Frank
2
2003
Quantum property testing. Zbl 1092.68615
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
2
2003
One bit of advice. Zbl 1035.68051
Buhrman, Harry; Chang, Richard; Fortnow, Lance
2
2003
Some results on derandomization. Zbl 1035.68052
Buhrman, Harry; Fortnow, Lance; Pavan, A.
2
2003
One complexity theorist’s view of quantum computing. Zbl 0967.68078
Fortnow, Lance
2
2000
On coherence, random-self-reducibility, and self-correction. Zbl 0917.68074
Feigenbaum, Joan; Fortnow, Lance; Laplante, Sophie; Naik, Ashish
2
1998
L-printable sets. Zbl 0915.68067
Fortnow, Lance; Goldsmith, Judy; Levy, Matthew A.; Mahaney, Stephen
2
1998
Results on resource-bounded measure. Zbl 1401.68087
Buhrman, Harry; Fenner, Stephen; Fortnow, Lance
2
1997
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
2
1995
Optimality and domination in repeated games with bounded players. Zbl 1345.91001
Fortnow, Lance; Whang, Duke
2
1994
Nondeterministic separations. Zbl 06487875
Fortnow, Lance
1
2015
Inverting onto functions and polynomial hierarchy. Zbl 1188.68144
Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay
1
2007
Linear advice for randomized logarithmic space. Zbl 1136.68404
Fortnow, Lance; Klivans, Adam R.
1
2006
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
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
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
Two queries. Zbl 0935.68033
Buhrman, Harry; Fortnow, Lance
1
1998
Nearly optimal language compression using extractors. Zbl 0894.68080
Fortnow, Lance; Laplante, Sophie
1
1998
Circuit lower bounds à la Kolmogorov. Zbl 1096.68632
Fortnow, Lance; Laplante, Sophie
1
1995
Gap-definability as a closure property. Zbl 0822.68031
Fenner, Stephen; Fortnow, Lance; Li, Lide
1
1993
On the power of two-local random reductions. Zbl 0795.68076
Fortnow, Lance; Szegedy, Mario
1
1992
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
4
2016
Nondeterministic separations. Zbl 06487875
Fortnow, Lance
1
2015
Testing closeness of discrete distributions. Zbl 1281.68227
Batu, Tuğkan; Fortnow, Lance; Rubinfeld, Ronitt; Smith, Warren D.; White, Patrick
12
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
69
2011
Robust simulations and significant separations. Zbl 1333.68118
Fortnow, Lance; Santhanam, Rahul
4
2011
Complexity classes of equivalence problems revisited. Zbl 1238.68061
Fortnow, Lance; Grochow, Joshua A.
4
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
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
6
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
10
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
10
2006
Tolerant versus intolerant testing for Boolean properties. Zbl 1213.68414
Fischer, Eldar; Fortnow, Lance
2
2006
Efficient learning algorithms yield circuit lower bounds. Zbl 1143.68415
Fortnow, Lance; Klivans, Adam R.
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.
6
2005
Computation in a distributed information market. Zbl 1079.68106
Feigenbaum, Joan; Fortnow, Lance; Pennock, David M.; Sami, Rahul
5
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
18
2003
Inverting onto functions. Zbl 1058.68061
Fenner, Stephen A.; Fortnow, Lance; Naik, Ashish V.; Rogers, John D.
11
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
Infinitely-often autoreducible sets. Zbl 1205.68161
Beigel, Richard; Fortnow, Lance; Stephan, Frank
2
2003
Quantum property testing. Zbl 1092.68615
Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein
2
2003
One bit of advice. Zbl 1035.68051
Buhrman, Harry; Chang, Richard; Fortnow, Lance
2
2003
Some results on derandomization. Zbl 1035.68052
Buhrman, Harry; Fortnow, Lance; Pavan, A.
2
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
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
Resource-bounded Kolmogorov complexity revisited. Zbl 1017.68061
Buhrman, Harry; Fortnow, Lance; Laplante, Sophie
23
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
16
2000
Separating complexity classes using autoreducibility. Zbl 0949.68068
Buhrman, Harry; Fortnow, Lance; van Melkebeek, Dieter; Torenvliet, Leen
7
2000
Diagonalization. Zbl 0973.68086
Fortnow, Lance
3
2000
Optimal proof systems and sparse sets. Zbl 0962.68071
Buhrman, Harry; Fenner, Steve; Fortnow, Lance; van Melkebeek, Dieter
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
11
1999
Two queries. Zbl 0947.68064
Buhrman, Harry; Fortnow, Lance
6
1999
One-sided versus two-sided error in probabilistic computation. Zbl 0928.68052
Buhrman, Harry; Fortnow, Lance
6
1999
Relativized worlds with an infinite hierarchy. Zbl 1002.68060
Fortnow, Lance
5
1999
Retraction of “Probabilistic computation and linear time”. Zbl 0967.68500
Fortnow, Lance; Sipser, Michael
3
1999
Nonrelativizing separations. Zbl 0935.68032
Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas
16
1998
NP might not be as easy as detecting unique solutions. Zbl 1027.68607
Beigel, Richard; Buhrman, Harry; Fortnow, Lance
5
1998
Complexity limitations on quantum computation. Zbl 0935.68042
Fortnow, Lance; Rogers, John
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
On coherence, random-self-reducibility, and self-correction. Zbl 0917.68074
Feigenbaum, Joan; Fortnow, Lance; Laplante, Sophie; Naik, Ashish
2
1998
L-printable sets. Zbl 0915.68067
Fortnow, Lance; Goldsmith, Judy; Levy, Matthew A.; Mahaney, Stephen
2
1998
Two queries. Zbl 0935.68033
Buhrman, Harry; Fortnow, Lance
1
1998
Nearly optimal language compression using extractors. Zbl 0894.68080
Fortnow, Lance; Laplante, Sophie
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
17
1996
The isomorphism conjecture holds relative to an oracle. Zbl 0841.68046
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.
5
1996
On resource-bounded instance complexity. Zbl 0872.68044
Fortnow, Lance; Kummer, Martin
4
1996
Generic separations. Zbl 0849.68035
Fortnow, Lance; Yamakami, Tomoyuki
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
2
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.
48
1994
On the power of multi-prover interactive protocols. Zbl 0938.68824
Fortnow, Lance; Rompel, John; Sipser, Michael
24
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
12
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
47
1993
Random-self-reducibility of complete sets. Zbl 0789.68057
Feigenbaum, Joan; Fortnow, Lance
16
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
76
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
94
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
15
1988
all top 5

Cited by 861 Authors

33 Fortnow, Lance J.
18 Stephan, Frank
16 Allender, Eric W.
16 Hemaspaandra, Lane A.
16 Saurabh, Saket
15 Kratsch, Stefan
13 Vinodchandran, N. Variyam
12 Arvind, Vikraman
12 Hitchcock, John M.
12 Jain, Sanjay
12 Jansen, Bart M. P.
11 van Melkebeek, Dieter
10 Buhrman, Harry
10 Cygan, Marek
10 Köbler, Johannes
9 Goldreich, Oded
9 Pavan, Aduri
9 Williams, Richard Ryan
9 Zimand, Marius
8 Beigel, Richard
8 Cai, Jin-Yi
8 Glaßer, Christian
8 Lokshtanov, Daniel
8 Pilipczuk, Marcin
8 Pilipczuk, Michał
8 Rothe, Jörg-Matthias
8 Rubinfeld, Ronitt
8 Shaltiel, Ronen
8 Wigderson, Avi
7 Bodlaender, Hans L.
7 Downey, Rodney Graham
7 Hermelin, Danny
7 Kabanets, Valentine
7 Misra, Neeldhara
7 Vidick, Thomas
7 Yamakami, Tomoyuki
6 Agrawal, Manindra
6 Antunes, Luis
6 Babai, László
6 Chiesa, Alessandro
6 Fellows, Michael Ralph
6 Ogihara, Mitsunori
6 Raman, Venkatesh
6 Shen, Alexander
6 Sudan, Madhu
6 Wahlström, Magnus
5 Fomin, Fedor V.
5 Impagliazzo, Russell
5 Lipton, Richard J.
5 Moser, Philippe
5 Müller, Moritz
5 Musatov, Daniil
5 Niedermeier, Rolf
5 Raz, Ran
5 Ron, Dana
5 Santhanam, Rahul
5 Selman, Alan L.
5 Souto, André
5 Teutsch, Jason
5 Vereshchagin, Nikolay K.
5 Vollmer, Heribert
4 Ambainis, Andris
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 Heggernes, Pinar
4 Kinber, Efim B.
4 Lund, Carsten
4 Ogiwara, Mitsunori
4 Ramanujan, M. S.
4 Romashchenko, Andrei
4 Seshadhri, Comandur
4 Sohler, Christian
4 Szeider, Stefan
4 Torenvliet, Leen
4 Wagner, Klaus W.
4 Watanabe, Osamu
4 Watson, Thomas C.
4 Zuckerman, David
3 Aaronson, Scott
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
3 Cai, Leizhen
3 Calude, Cristian S.
3 Case, John
3 Chakaravarthy, Venkatesan T.
3 Condon, Anne E.
3 de Wolf, Ronald Michiel
3 Dell, Holger
...and 761 more Authors
all top 5

Cited in 85 Serials

93 Theoretical Computer Science
74 Journal of Computer and System Sciences
47 Computational Complexity
38 Information and Computation
35 Algorithmica
30 Information Processing Letters
27 Theory of Computing Systems
23 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 Artificial Intelligence
4 The Journal of Symbolic Logic
4 Journal of Combinatorial Optimization
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 International Journal of Approximate Reasoning
2 The Annals of Applied Probability
2 Games and Economic Behavior
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 Communications in Mathematical Physics
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 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 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 European Journal of Mathematics

Citations by Year