


default search action
Lance Fortnow
Person information
- affiliation: Illinois Institute of Technology, Chicago, IL, USA
- affiliation: Georgia Institute of Technology, Atlanta, USA
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2022
- [j82]Lance Fortnow:
Fifty years of P vs. NP and the possibility of the impossible. Commun. ACM 65(1): 76-85 (2022) - [j81]Lance Fortnow:
Computational Complexity. Bull. EATCS 136 (2022) - 2021
- [j80]Lance Fortnow:
Worlds to Die Harder For Open Oracle Questions for the 21st Century. SIGACT News 52(3): 26-36 (2021) - 2020
- [i41]C. N. P. Slagle, Lance Fortnow:
Matrix Multiplication and Binary Space Partitioning Trees : An Exploration. CoRR abs/2012.05365 (2020)
2010 – 2019
- 2018
- [c103]Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow:
Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching. IEEE CLOUD 2018: 426-433 - [c102]Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow:
2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching. CLOUD 2018: 69-83 - [c101]Liang Liu, Jun (Jim) Xu, Lance Fortnow:
Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks. UCC 2018: 237-246 - 2017
- [j79]Lance Fortnow, Rahul Santhanam:
Robust simulations and significant separations. Inf. Comput. 256: 149-159 (2017) - [c100]Lance Fortnow:
Complexity with Rod. Computability and Complexity 2017: 115-121 - [i40]Stephen A. Fenner, Lance Fortnow:
Compression Complexity. CoRR abs/1702.04779 (2017) - [i39]Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow:
Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers. CoRR abs/1712.06634 (2017) - 2016
- [j78]Lance Fortnow:
David Stifler Johnson: A Tribute by Lance Fortnow. Bull. EATCS 119 (2016) - [j77]Lance Fortnow:
The Golden Ticket P, NP, and the Search for the Impossible. Bull. EATCS 120 (2016) - [c99]Liang Liu, Lance Fortnow, Jin Li, Yating Wang, Jun (Jim) Xu:
Randomized Algorithms for Dynamic Storage Load-Balancing. SoCC 2016: 210-222 - [c98]Lance Fortnow, Rahul Santhanam
:
New Non-Uniform Lower Bounds for Uniform Classes. CCC 2016: 19:1-19:14 - [c97]Liang Liu, Yating Wang, Lance Fortnow, Jin Li, Jun (Jim) Xu:
Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing. SIGMETRICS 2016: 381-382 - 2015
- [c96]Lance Fortnow:
Nondeterministic Separations. TAMC 2015: 10-17 - 2014
- [r1]Lance Fortnow, Steven Homer:
Computational Complexity. Computational Logic 2014: 495-521 - [i38]Lance Fortnow, Rahul Santhanam:
Hierarchies Against Sublinear Advice. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [b1]Lance Fortnow:
The Golden Ticket - P, NP, and the Search for the Impossible. Princeton University Press 2013, ISBN 978-0-691-15649-1, pp. I-X, 1-176 - [j76]Tugkan Batu
, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing Closeness of Discrete Distributions. J. ACM 60(1): 4:1-4:25 (2013) - [c95]Lance Fortnow:
A Personal View of the P versus NP Problem. CiE 2013: 147-148 - [c94]Harry Buhrman, Lance Fortnow, John M. Hitchcock
, Bruno Loff
:
Learning Reductions to Sparse Sets. MFCS 2013: 243-253 - 2012
- [j75]Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
:
Low-Depth Witnesses are Easy to Find. Comput. Complex. 21(3): 479-497 (2012) - [j74]Lance Fortnow:
The Enduring Legacy of the Turing Machine. Comput. J. 55(7): 830-831 (2012) - [j73]Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
:
Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. 51(2): 229-247 (2012) - [i37]Lance Fortnow, Rahul Sami:
Multi-outcome and Multidimensional Market Scoring Rules. CoRR abs/1202.1712 (2012) - 2011
- [j72]Lance Fortnow, John M. Hitchcock
, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
Extracting Kolmogorov complexity with applications to dimension zero-one laws. Inf. Comput. 209(4): 627-636 (2011) - [j71]Lance Fortnow, Joshua A. Grochow:
Complexity classes of equivalence problems revisited. Inf. Comput. 209(4): 748-763 (2011) - [j70]Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011) - [c93]Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580 - [c92]Michele Budinich, Lance Fortnow:
Repeated matching pennies with limited randomness. EC 2011: 111-118 - [e6]Lance Fortnow, Salil P. Vadhan:
Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. ACM 2011, ISBN 978-1-4503-0691-1 [contents] - [i36]Michele Budinich, Lance Fortnow:
Repeated Matching Pennies with Limited Randomness. CoRR abs/1102.1096 (2011) - 2010
- [j69]Yiling Chen, Stanko Dimitrov
, Rahul Sami, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen:
Gaming Prediction Markets: Equilibrium Strategies with a Market Maker. Algorithmica 58(4): 930-969 (2010) - [j68]Harry Buhrman, Lance Fortnow, Michal Koucký
, John D. Rogers, Nikolai K. Vereshchagin
:
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46(1): 143-156 (2010) - [j67]Lance Fortnow:
Ubiquity symposium 'What is computation?': The enduring legacy of the Turing machine. Ubiquity 2010(December): 5 (2010) - [c91]Harry Buhrman, Lance Fortnow, Michal Koucký
, Bruno Loff
:
Derandomizing from Random Strings. CCC 2010: 58-63 - [c90]Lance Fortnow, Rahul Santhanam:
Bounding Rationality by Discounting Time. ICS 2010: 143-155 - [c89]Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
:
Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS 2010: 395-404 - [i35]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010) - [i34]Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. CoRR abs/1012.2034 (2010)
2000 – 2009
- 2009
- [j66]Lance Fortnow:
Viewpoint - Time for computer science to grow up. Commun. ACM 52(8): 33-35 (2009) - [j65]Lance Fortnow:
The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) - [j64]Lance Fortnow, Adam R. Klivans:
Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. 75(1): 27-36 (2009) - [j63]Luis Filipe Coelho Antunes, Lance Fortnow:
Sophistication Revisited. Theory Comput. Syst. 45(1): 150-161 (2009) - [j62]Lance Fortnow:
A Simple Proof of Toda's Theorem. Theory Comput. 5(1): 135-140 (2009) - [j61]Lance Fortnow:
Editor's Foreword. ACM Trans. Comput. Theory 1(1): 1:1-1:2 (2009) - [c88]Lance Fortnow, Rahul Santhanam, Ryan Williams
:
Fixed-Polynomial Size Circuit Bounds. CCC 2009: 19-26 - [c87]Luis Filipe Coelho Antunes, Lance Fortnow:
Worst-Case Running Times for Average-Case Algorithms. CCC 2009: 298-303 - [c86]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209 - [c85]Nikhil R. Devanur, Lance Fortnow:
A computational theory of awareness and decision making. TARK 2009: 99-107 - [c84]Lance Fortnow:
Program equilibria and discounted computation time. TARK 2009: 128-133 - [e5]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009. Dagstuhl Seminar Proceedings 09421, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [e4]John Chuang, Lance Fortnow, Pearl Pu:
Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009. ACM 2009, ISBN 978-1-60558-458-4 [contents] - [i33]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i32]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i31]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity 2009 - [i30]Lance Fortnow, Joshua A. Grochow:
Complexity Classes of Equivalence Problems Revisited. CoRR abs/0907.4775 (2009) - [i29]Lance Fortnow, Rahul Santhanam:
Bounding Rationality by Discounting Time. CoRR abs/0911.3162 (2009) - [i28]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CoRR abs/0912.3162 (2009) - [i27]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j60]Lance Fortnow, Russell Impagliazzo
, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17(3): 353-376 (2008) - [j59]Lance Fortnow, Aduri Pavan, Samik Sengupta:
Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Syst. Sci. 74(3): 358-363 (2008) - [j58]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008) - [j57]Lance Fortnow, Rakesh V. Vohra:
The complexity of forecast testing. SIGecom Exch. 7(3) (2008) - [c83]Lance Fortnow, Rakesh Vohra:
The complexity of forecast testing: abstract. EC 2008: 139 - [c82]Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman:
Complexity of combinatorial market makers. EC 2008: 190-199 - [c81]Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142 - [e3]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007. Dagstuhl Seminar Proceedings 07411, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008 [contents] - [e2]Lance Fortnow, John Riedl, Tuomas Sandholm:
Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008. ACM 2008, ISBN 978-1-60558-169-9 [contents] - [i26]Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman:
Complexity of Combinatorial Market Makers. CoRR abs/0802.1362 (2008) - [i25]Nikhil R. Devanur, Lance Fortnow:
A Computational Theory of Awareness and Decision Making. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j56]Yiling Chen, Lance Fortnow, Evdokia Nikolova
, David M. Pennock:
Combinatorial betting. SIGecom Exch. 7(1): 61-64 (2007) - [c80]Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
:
Low-Depth Witnesses are Easy to Find. CCC 2007: 46-51 - [c79]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103 - [c78]Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock:
Betting on permutations. EC 2007: 326-335 - [c77]Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen:
Bluffing and Strategic Reticence in Prediction Markets. WINE 2007: 70-81 - [i24]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i23]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i22]Lance Fortnow, Rahul Santhanam:
Time Hierarchies: A Survey. Electron. Colloquium Comput. Complex. TR07 (2007) - [i21]Lance Fortnow, Rahul Santhanam:
Infeasibility of Instance Compression and Succinct PCPs for NP. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j55]Richard Beigel, Lance Fortnow, William I. Gasarch:
A tight lower bound for restricted pir protocols. Comput. Complex. 15(1): 82-91 (2006) - [j54]Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan
, Leen Torenvliet:
Enumerations of the Kolmogorov function. J. Symb. Log. 71(2): 501-528 (2006) - [j53]Richard Beigel, Lance Fortnow, Frank Stephan
:
Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006) - [j52]Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran:
Computational depth: Concept and applications. Theor. Comput. Sci. 354(3): 391-404 (2006) - [j51]Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. Theory Comput. 2(9): 173-183 (2006) - [c76]Lance Fortnow, Adam R. Klivans:
Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT 2006: 350-363 - [c75]Lance Fortnow, John M. Hitchcock
, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. ICALP (1) 2006: 335-345 - [c74]Lance Fortnow, Mitsunori Ogihara
:
Very Sparse Leaf Languages. MFCS 2006: 375-386 - [c73]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. STACS 2006: 137-148 - [c72]Lance Fortnow, Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space. STACS 2006: 469-476 - [i20]Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
Low-Depth Witnesses are Easy to Find. Electron. Colloquium Comput. Complex. TR06 (2006) - [i19]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. TR06 (2006) - [i18]Lance Fortnow, Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds. Electron. Colloquium Comput. Complex. TR06 (2006) - [i17]Lance Fortnow, Rakesh Vohra:
The Complexity of Forecast Testing. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j50]Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
:
Betting Boolean-style: a framework for trading in securities based on logical formulas. Decis. Support Syst. 39(1): 87-104 (2005) - [j49]Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas:
Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005) - [j48]Lance Fortnow, Jack H. Lutz:
Prediction and dimension. J. Comput. Syst. Sci. 70(4): 570-589 (2005) - [j47]Harry Buhrman, Lance Fortnow, Aduri Pavan:
Some Results on Derandomization. Theory Comput. Syst. 38(2): 211-227 (2005) - [j46]Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
:
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. 35(1): 91-109 (2005) - [j45]Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami:
Computation in a distributed information market. Theor. Comput. Sci. 343(1-2): 114-132 (2005) - [c71]Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. CCC 2005: 135-140 - [c70]Lance Fortnow, Adam R. Klivans:
NP with Small Advice. CCC 2005: 228-234 - [c69]Lance Fortnow, Russell Impagliazzo
, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. CCC 2005: 323-332 - [c68]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. STACS 2005: 412-421 - [c67]Lance Fortnow:
Beyond NP: the work and legacy of Larry Stockmeyer. STOC 2005: 120-127 - [c66]Lance Fortnow, Rahul Santhanam, Luca Trevisan
:
Hierarchies for semantic classes. STOC 2005: 348-355 - [e1]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005 [contents] - [i16]Lance Fortnow, Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space. Electron. Colloquium Comput. Complex. TR05 (2005) - [i15]Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. Electron. Colloquium Comput. Complex. TR05 (2005) - [i14]Lance Fortnow, Luis Antunes:
Time-Bounded Universal Distributions. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j44]Lance Fortnow:
Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. SIGACT News 35(2): 16-18 (2004) - [c65]Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324 - [i13]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004 - [i12]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the complexity of succinct zero-sum games. Electron. Colloquium Comput. Complex. TR04 (2004) - [i11]Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet:
Enumerations of the Kolmogorov Function. Electron. Colloquium Comput. Complex. TR04 (2004) - [i10]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. Electron. Colloquium Comput. Complex. TR04 (2004) - [i9]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i8]Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Promise Hierarchies. Electron. Colloquium Comput. Complex. TR04 (2004) - [i7]Lance Fortnow, Adam R. Klivans:
NP with Small Advice. Electron. Colloquium Comput. Complex. TR04 (2004) - [i6]Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j43]Lance Fortnow, Steven Homer:
A Short History of Computational Complexity. Bull. EATCS 80: 95-133 (2003) - [j42]