Lance Fortnow

Publication Activity (10 Years)

Years Active: 1987-2022
Publications (10 Years): 17

Top Venues

CoRR

Bull. EATCS

CLOUD

IEEE CLOUD

Publications

Lance Fortnow
Computational Complexity. Bull. EATCS 136 (2022)
Lance Fortnow
Fifty years of P vs. NP and the possibility of the impossible. Commun. ACM 65 (1) (2022)
Lance Fortnow
Worlds to Die Harder For Open Oracle Questions for the 21st Century. SIGACT News 52 (3) (2021)
C. N. P. Slagle, Lance Fortnow
Matrix Multiplication and Binary Space Partitioning Trees : An Exploration. CoRR (2020)
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)
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)
Liang Liu, Jun (Jim) Xu, Lance Fortnow
Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks. UCC (2018)
Lance Fortnow, Rahul Santhanam
Robust simulations and significant separations. Inf. Comput. 256 (2017)
Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow
Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers. CoRR (2017)
Stephen A. Fenner, Lance Fortnow
Compression Complexity. CoRR (2017)
Lance Fortnow
Complexity with Rod. Computability and Complexity (2017)
Lance Fortnow
The Golden Ticket P, NP, and the Search for the Impossible. Bull. EATCS 120 (2016)
Liang Liu, Lance Fortnow, Jin Li, Yating Wang, Jun (Jim) Xu
Randomized Algorithms for Dynamic Storage Load-Balancing. SoCC (2016)
Lance Fortnow, Rahul Santhanam
New Non-Uniform Lower Bounds for Uniform Classes. Computational Complexity Conference (2016)
Liang Liu, Yating Wang, Lance Fortnow, Jin Li, Jun (Jim) Xu
Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing. SIGMETRICS (2016)
Lance Fortnow
David Stifler Johnson: A Tribute by Lance Fortnow. Bull. EATCS 119 (2016)
Lance Fortnow
Nondeterministic Separations. TAMC (2015)
Lance Fortnow, Rahul Santhanam
Hierarchies Against Sublinear Advice. Electron. Colloquium Comput. Complex. 21 (2014)
Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
Learning Reductions to Sparse Sets. MFCS (2013)
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Testing Closeness of Discrete Distributions. J. ACM 60 (1) (2013)
Lance Fortnow
A Personal View of the P versus NP Problem. CiE (2013)
Lance Fortnow, Rahul Sami
Multi-outcome and Multidimensional Market Scoring Rules CoRR (2012)
Lance Fortnow
The Enduring Legacy of the Turing Machine. Comput. J. 55 (7) (2012)
Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. 51 (2) (2012)
Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
Low-Depth Witnesses are Easy to Find. Comput. Complex. 21 (3) (2012)
Michele Budinich, Lance Fortnow
Repeated matching pennies with limited randomness. EC (2011)
Lance Fortnow, Rahul Santhanam
Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77 (1) (2011)
Michele Budinich, Lance Fortnow
Repeated Matching Pennies with Limited Randomness CoRR (2011)
Lance Fortnow, Joshua A. Grochow
Complexity classes of equivalence problems revisited. Inf. Comput. 209 (4) (2011)
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) (2011)
Lance Fortnow, Rahul Santhanam
Robust Simulations and Significant Separations. ICALP (1) (2011)
Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS (2010)
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White
Testing Closeness of Discrete Distributions CoRR (2010)
Lance Fortnow
Ubiquity symposium 'What is computation?': The enduring legacy of the Turing machine. Ubiquity 2010 (December) (2010)
Lance Fortnow, Rahul Santhanam
Bounding Rationality by Discounting Time. ICS (2010)
Lance Fortnow, Rahul Santhanam
Robust Simulations and Significant Separations CoRR (2010)
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) (2010)
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) (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings. Computational Complexity Conference (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings CoRR (2009)
Luis Filipe Coelho Antunes, Lance Fortnow
Worst-Case Running Times for Average-Case Algorithms. Computational Complexity Conference (2009)
Lance Fortnow, Rahul Santhanam, Ryan Williams
Fixed-Polynomial Size Circuit Bounds. Computational Complexity Conference (2009)
Lance Fortnow, Rahul Santhanam
Bounding Rationality by Discounting Time CoRR (2009)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity (2009)
Lance Fortnow, Joshua A. Grochow
Complexity Classes of Equivalence Problems Revisited CoRR (2009)
Lance Fortnow
A Simple Proof of Toda's Theorem. Theory Comput. 5 (1) (2009)
Luis Filipe Coelho Antunes, Lance Fortnow
Sophistication Revisited. Theory Comput. Syst. 45 (1) (2009)
Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2009)
Lance Fortnow
The status of the P versus NP problem. Commun. ACM 52 (9) (2009)
Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans
09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2009)
Lance Fortnow
Program equilibria and discounted computation time. TARK (2009)
Nikhil R. Devanur, Lance Fortnow
A computational theory of awareness and decision making. TARK (2009)
Lance Fortnow, Adam R. Klivans
Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. 75 (1) (2009)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. 16 (2009)
Lance Fortnow
Editor's Foreword. ACM Trans. Comput. Theory 1 (1) (2009)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
Unconditional Lower Bounds against Advice. ICALP (1) (2009)
Lance Fortnow
Viewpoint - Time for computer science to grow up. Commun. ACM 52 (8) (2009)
Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman
Complexity of Combinatorial Market Makers CoRR (2008)
Lance Fortnow, Rakesh V. Vohra
The complexity of forecast testing. SIGecom Exch. 7 (3) (2008)
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) (2008)
Lance Fortnow, Rahul Santhanam
Infeasibility of instance compression and succinct PCPs for NP. STOC (2008)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
Quantum Property Testing. SIAM J. Comput. 37 (5) (2008)
Nikhil R. Devanur, Lance Fortnow
A Computational Theory of Awareness and Decision Making. Electron. Colloquium Comput. Complex. 15 (046) (2008)
Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman
Complexity of combinatorial market makers. EC (2008)
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17 (3) (2008)
Lance Fortnow, Rakesh Vohra
The complexity of forecast testing: abstract. EC (2008)
Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen
Bluffing and Strategic Reticence in Prediction Markets. WINE (2007)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Inverting Onto Functions and Polynomial Hierarchy. CSR (2007)
Lance Fortnow, Rahul Santhanam
Time Hierarchies: A Survey. Electron. Colloquium Comput. Complex. 14 (004) (2007)
Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2007)
Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock
Combinatorial betting. SIGecom Exch. 7 (1) (2007)
Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2007)
Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock
Betting on permutations. EC (2007)
Lance Fortnow, Rahul Santhanam
Infeasibility of Instance Compression and Succinct PCPs for NP. Electron. Colloquium Comput. Complex. 14 (096) (2007)
Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
Low-Depth Witnesses are Easy to Find. Computational Complexity Conference (2007)
Lance Fortnow, Rahul Santhanam
Fixed-Polynomial Size Circuit Bounds. Electron. Colloquium Comput. Complex. 13 (157) (2006)
Lance Fortnow, Mitsunori Ogihara
Very Sparse Leaf Languages. MFCS (2006)
Lance Fortnow, Rakesh Vohra
The Complexity of Forecast Testing. Electron. Colloquium Comput. Complex. 13 (149) (2006)
Lance Fortnow, Adam R. Klivans
Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT (2006)
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)
Eldar Fischer, Lance Fortnow
Tolerant Versus Intolerant Testing for Boolean Properties. Theory Comput. 2 (9) (2006)
Lance Fortnow, Adam R. Klivans
Linear Advice for Randomized Logarithmic Space. STACS (2006)
Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
Kolmogorov Complexity with Error. STACS (2006)
Richard Beigel, Lance Fortnow, Frank Stephan
Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36 (3) (2006)
Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran
Computational depth: Concept and applications. Theor. Comput. Sci. 354 (3) (2006)
Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
Low-Depth Witnesses are Easy to Find. Electron. Colloquium Comput. Complex. 13 (125) (2006)
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) (2006)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. 13 (024) (2006)
Richard Beigel, Lance Fortnow, William I. Gasarch
A tight lower bound for restricted pir protocols. Comput. Complex. 15 (1) (2006)
Lance Fortnow, Jack H. Lutz
Prediction and dimension. J. Comput. Syst. Sci. 70 (4) (2005)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
Computation in a distributed information market. Theor. Comput. Sci. 343 (1-2) (2005)
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans
On the Complexity of Succinct Zero-Sum Games. Computational Complexity Conference (2005)
Eldar Fischer, Lance Fortnow
Tolerant Versus Intolerant Testing for Boolean Properties. Computational Complexity Conference (2005)
Lance Fortnow, Adam R. Klivans
NP with Small Advice. Computational Complexity Conference (2005)
Harry Buhrman, Lance Fortnow, Aduri Pavan
Some Results on Derandomization. Theory Comput. Syst. 38 (2) (2005)
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) (2005)
Lance Fortnow, Luis Antunes
Time-Bounded Universal Distributions Electron. Colloquium Comput. Complex. (144) (2005)
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) (2005)
Lance Fortnow, Adam R. Klivans
Linear Advice for Randomized Logarithmic Space Electron. Colloquium Comput. Complex. (042) (2005)
Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas
Time-space lower bounds for satisfiability. J. ACM 52 (6) (2005)

Lance Fortnow.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Lance Fortnow