| Year |
Citation |
Score |
| 2016 |
Fortnow L, Santhanam R. New non-uniform lower bounds for uniform classes Leibniz International Proceedings in Informatics, Lipics. 50: 19:1-19:14. DOI: 10.4230/LIPIcs.CCC.2016.19 |
0.6 |
|
| 2012 |
Fortnow L. The enduring legacy of the Turing machine Computer Journal. 55: 830-831. DOI: 10.1093/Comjnl/Bxs073 |
0.321 |
|
| 2011 |
Fortnow L, Santhanam R. Infeasibility of instance compression and succinct PCPs for NP Journal of Computer and System Sciences. 77: 91-106. DOI: 10.1016/J.Jcss.2010.06.007 |
0.629 |
|
| 2011 |
Fortnow L, Santhanam R. Robust simulations and significant separations Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6755: 569-580. DOI: 10.1016/J.Ic.2017.07.002 |
0.621 |
|
| 2011 |
Fortnow L, Grochow JA. Complexity classes of equivalence problems revisited Information and Computation. 209: 748-763. DOI: 10.1016/J.Ic.2011.01.006 |
0.394 |
|
| 2011 |
Fortnow L, Hitchcock JM, Pavan A, Vinodchandran NV, Wang F. Extracting Kolmogorov complexity with applications to dimension zero-one laws Information and Computation. 209: 627-636. DOI: 10.1016/J.Ic.2010.09.006 |
0.307 |
|
| 2010 |
Fortnow L, Lutz JH, Mayordomo E. Inseparability and strong hypotheses for disjoint NP pairs Leibniz International Proceedings in Informatics, Lipics. 5: 395-404. DOI: 10.1007/S00224-011-9326-7 |
0.447 |
|
| 2009 |
Fortnow L. Theory of Computing. 5: 135-140. DOI: 10.4086/Toc.2009.V005A007 |
0.349 |
|
| 2009 |
Fortnow L. The status of the P versus NP problem Communications of the Acm. 52: 78-86. DOI: 10.1145/1562164.1562186 |
0.384 |
|
| 2009 |
Fortnow L, Santhanam R, Williams R. Fixed-Polynomial size circuit bounds Proceedings of the Annual Ieee Conference On Computational Complexity. 19-26. DOI: 10.1109/CCC.2009.21 |
0.498 |
|
| 2009 |
Buhrman H, Fortnow L, Koucký M, Rogers JD, Vereshchagin N. Does the polynomial hierarchy collapse if onto functions are invertible? Theory of Computing Systems. 46: 143-156. DOI: 10.1007/S00224-008-9160-8 |
0.383 |
|
| 2009 |
Buhrman H, Fortnow L, Santhanam R. Unconditional lower bounds against advice Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5555: 195-209. DOI: 10.1007/978-3-642-02927-1_18 |
0.622 |
|
| 2008 |
Fortnow L, Impagliazzo R, Kabanets V, Umans C. On the complexity of succinct zero-sum games Computational Complexity. 17: 353-376. DOI: 10.1007/S00037-008-0252-2 |
0.392 |
|
| 2007 |
Antunes L, Fortnow L, Pinto A, Souto A. Low-depth witnesses are easy to find Proceedings of the Annual Ieee Conference On Computational Complexity. 46-51. DOI: 10.1007/S00037-011-0025-1 |
0.381 |
|
| 2007 |
Buhrman H, Fortnow L, Koucký M, Rogers JD, Vereshchagin N. Inverting onto functions and polynomial hierarchy Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4649: 92-103. |
0.306 |
|
| 2006 |
Beigel R, Buhrman H, Fejer P, Fortnow L, Grabowski P, Longpré L, Muchnik A, Stephan F, Torenvliet L. Enumerations of the kolmogorov function Journal of Symbolic Logic. 71: 501-528. DOI: 10.2178/Jsl/1146620156 |
0.32 |
|
| 2006 |
Czumaj A, Ergün F, Fortnow L, Magen A, Newman I, Rubinfeld R, Sohler C. Approximating the weight of the Euclidean minimum spanning tree in sublinear time Siam Journal On Computing. 35: 91-109. DOI: 10.1137/S0097539703435297 |
0.33 |
|
| 2006 |
Antunes L, Fortnow L, Van Melkebeek D, Vinodchandran NV. Computational depth: Concept and applications Theoretical Computer Science. 354: 391-404. DOI: 10.1016/J.Tcs.2005.11.033 |
0.357 |
|
| 2006 |
Fortnow L, Klivans AR. Efficient learning algorithms yield circuit lower bounds Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4005: 350-363. DOI: 10.1016/J.Jcss.2008.07.006 |
0.332 |
|
| 2006 |
Beigel R, Fortnow L, Gasarch W. A Tight lower bound for restricted pir protocols Computational Complexity. 15: 82-91. DOI: 10.1007/S00037-006-0208-3 |
0.315 |
|
| 2006 |
Fortnow L, Ogihara M. Very sparse leaf languages Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4162: 375-386. |
0.349 |
|
| 2005 |
Fischer E, Fortnow L. Tolerant versus intolerant testing for boolean properties Proceedings of the Annual Ieee Conference On Computational Complexity. 135-140. DOI: 10.4086/Toc.2006.V002A009 |
0.31 |
|
| 2005 |
Fortnow L, Lipton R, Van Melkebeek D, Viglas A. Time-space lower bounds for satisfiability Journal of the Acm. 52: 835-865. DOI: 10.1145/1101821.1101822 |
0.407 |
|
| 2005 |
Fortnow L, Santhanam R, Trevisan L. Hierarchies for semantic classes Proceedings of the Annual Acm Symposium On Theory of Computing. 348-355. DOI: 10.1145/1060590.1060642 |
0.519 |
|
| 2004 |
Fortnow L, Santhanam R. Hierarchy theorems for probabilistic polynomial time Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 316-324. |
0.545 |
|
| 2003 |
Buhrman H, Fortnow L, Newman I, Röhrig H. Quantum property testing Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 480-488. DOI: 10.1137/S0097539704442416 |
0.323 |
|
| 2003 |
Beigel R, Fortnow L, Stephan F. Infinitely-often autoreducible sets Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2906: 98-107. DOI: 10.1137/S0097539704441630 |
0.35 |
|
| 2003 |
Fenner SA, Fortnow L, Naik AV, Rogers JD. Inverting onto functions Information and Computation. 186: 90-103. DOI: 10.1016/S0890-5401(03)00119-6 |
0.38 |
|
| 2003 |
Fenner S, Fortnow L, Kurtz SA, Li L. An oracle builder's toolkit Information and Computation. 182: 95-136. DOI: 10.1016/S0890-5401(03)00018-X |
0.406 |
|
| 2003 |
Downey R, Fortnow L. Uniformly hard languages Theoretical Computer Science. 298: 303-315. DOI: 10.1016/S0304-3975(02)00810-1 |
0.386 |
|
| 2003 |
Fortnow L, Pavan A, Sengupta S. Proving SAT does not have small circuits with an application to the two queries problem Proceedings of the Annual Ieee Conference On Computational Complexity. 347-350. DOI: 10.1016/J.Jcss.2007.06.017 |
0.333 |
|
| 2003 |
Buhrman H, Fortnow L, Pavan A. Some results on derandomization Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2607: 212-222. DOI: 10.1007/S00224-004-1194-Y |
0.378 |
|
| 2002 |
Fortnow L, Rogers JD. Separability and one-way functions Computational Complexity. 11: 137-157. DOI: 10.1007/S00037-002-0173-4 |
0.358 |
|
| 2001 |
Fortnow L, Pavan A, Selman AL. Distributionally hard languages Theory of Computing Systems. 34: 245-261. DOI: 10.1007/S00224-001-0003-0 |
0.442 |
|
| 2001 |
Buhrman H, Fenner S, Fortnow L, Torenvliet L. Two oracles that force a big crunch Computational Complexity. 10: 93-116. DOI: 10.1007/S00037-001-8190-2 |
0.353 |
|
| 2000 |
Buhrman H, Fortnow L, Van Melkebeek D, Torenvliet L. Separating complexity classes using autoreducibility Siam Journal On Computing. 29: 1497-1520. DOI: 10.1137/S0097539798334736 |
0.393 |
|
| 2000 |
Fortnow L. One complexity theorist's view of quantum computing Electronic Notes in Theoretical Computer Science. 31: 58-72. DOI: 10.1016/S1571-0661(05)80330-5 |
0.303 |
|
| 2000 |
Buhrman H, Fenner S, Fortnow L, van Melkebeek D. Optimal proof systems and sparse sets Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1770: 407-418. |
0.316 |
|
| 1999 |
Fortnow L. Relativized worlds with an infinite hierarchy Information Processing Letters. 69: 309-313. DOI: 10.1016/S0020-0190(99)00034-4 |
0.434 |
|
| 1999 |
Fortnow L, Pavan A, Selman AL. Distributionally-hard languages Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1627: 184-193. DOI: 10.1007/3-540-48686-0_18 |
0.337 |
|
| 1999 |
Fortnow L, Rogers J. Complexity limitations on quantum computation Journal of Computer and System Sciences. 59: 240-252. DOI: 10.1006/Jcss.1999.1651 |
0.354 |
|
| 1998 |
Fortnow L, Goldsmith J, Levy MA, Mahaney S. L-Printable sets Siam Journal On Computing. 28: 137-151. DOI: 10.1137/S0097539796300441 |
0.366 |
|
| 1998 |
Fortnow L, Freivalds R, Gasarch WI, Kummer M, Kurtz SA, Smith CH, Stephan F. On the relative sizes of learnable sets Theoretical Computer Science. 197: 139-156. DOI: 10.1016/S0304-3975(97)00175-8 |
0.317 |
|
| 1997 |
Buhrman H, Fortnow L. Resource-bounded kolmogorov complexity revisited Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1200: 105-116. DOI: 10.1137/S009753979834388X |
0.347 |
|
| 1996 |
Fenner S, Fortnow L, Kurtz SA. The Isomorphism Conjecture Holds Relative toan Oracle Siam Journal On Computing. 25: 193-206. DOI: 10.1137/S0097539793248305 |
0.384 |
|
| 1996 |
Fortnow L, Kummer M. On resource-bounded instance complexity Theoretical Computer Science. 161: 123-140. DOI: 10.1016/0304-3975(95)00097-6 |
0.422 |
|
| 1996 |
Fenner S, Fortnow L, Li L. Gap-Definability as a Closure Property Information and Computation. 130: 1-17. DOI: 10.1006/Inco.1996.0080 |
0.344 |
|
| 1996 |
Fortnow L, Reingold N. PP is Closed under Truth-Table Reductions Information and Computation. 124: 1-6. DOI: 10.1006/Inco.1996.0001 |
0.365 |
|
| 1995 |
Fortnow L, Laplante S. Circuit Lower Bounds à la Kolmogorov Information and Computation. 123: 121-126. DOI: 10.1006/Inco.1995.1161 |
0.347 |
|
| 1995 |
Fortnow L, Kummer M. Resource-bounded instance complexity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 900: 597-608. |
0.325 |
|
| 1994 |
Fortnow L, Kurtz S, Whang D. The infinite version of an open communication complexity problem is independent of the axioms of set theory Acm Sigact News. 25: 87-89. DOI: 10.1145/181773.181778 |
0.331 |
|
| 1994 |
Fortnow L, Rompel J, Sipser M. On the power of multi-prover interactive protocols Theoretical Computer Science. 134: 545-557. DOI: 10.1016/0304-3975(94)90251-8 |
0.707 |
|
| 1994 |
Feigenbaum J, Fortnow L, Lund C, Spielman D. The power of adaptiveness and additional queries in random-self-reductions Computational Complexity. 4: 158-174. DOI: 10.1007/BF01202287 |
0.456 |
|
| 1993 |
Feigenbaum J, Fortnow L. Random-self-reducibility of complete sets Siam Journal On Computing. 22: 994-1005. DOI: 10.1137/0222061 |
0.315 |
|
| 1993 |
Babai L, Fortnow L, Nisan N, Wigderson A. BPP has subexponential time simulations unless EXPTIME has publishable proofs Computational Complexity. 3: 307-318. DOI: 10.1007/Bf01275486 |
0.393 |
|
| 1992 |
Lund C, Fortnow L, Karloff H, Nisan N. Algebraic Methods for Interactive Proof Systems Journal of the Acm (Jacm). 39: 859-868. DOI: 10.1145/146585.146605 |
0.344 |
|
| 1992 |
Fortnow L, Szegedy M. On the power of two-local random reductions Information Processing Letters. 44: 303-306. DOI: 10.1016/0020-0190(92)90104-4 |
0.389 |
|
| 1992 |
Babai L, Fortnow L, Lund C. Non-deterministic exponential time has two-prover interactive protocols Computational Complexity. 2: 374. DOI: 10.1007/Bf01200430 |
0.42 |
|
| 1991 |
Babai L, Fortnow L. Arithmetization: A new method in structural complexity theory Computational Complexity. 1: 41-66. DOI: 10.1007/Bf01200057 |
0.384 |
|
| 1988 |
Fortnow L, Sipser M. Are there interactive protocols for co-NP languages? Information Processing Letters. 28: 249-251. DOI: 10.1016/0020-0190(88)90199-8 |
0.707 |
|
| Show low-probability matches. |