| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Lance Fortnow, Rahul Sami |
Multi-outcome and Multidimensional Market Scoring Rules  |
CoRR  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Jack H. Lutz, Elvira Mayordomo |
Inseparability and Strong Hypotheses for Disjoint NP Pairs. |
Theory Comput. Syst. |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
Extracting Kolmogorov complexity with applications to dimension zero-one laws. |
Inf. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michele Budinich, Lance Fortnow |
Repeated Matching Pennies with Limited Randomness |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Infeasibility of instance compression and succinct PCPs for NP. |
J. Comput. Syst. Sci. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Robust Simulations and Significant Separations. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michele Budinich, Lance Fortnow |
Repeated matching pennies with limited randomness. |
ACM Conference on Electronic Commerce |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Salil P. Vadhan (eds.) |
Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 |
STOC |
2011 |
DBLP BibTeX RDF |
|
| 1 | 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 |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Robust Simulations and Significant Separations |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White |
Testing Closeness of Discrete Distributions |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Jack H. Lutz, Elvira Mayordomo |
Inseparability and Strong Hypotheses for Disjoint NP Pairs. |
STACS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Bounding Rationality by Discounting Time. |
ICS |
2010 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff |
Derandomizing from Random Strings. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Truth-table Reducibility, Kolmogorov Complexity, Derandomization |
| 1 | Lance Fortnow |
Editor's Foreword. |
TOCT |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Rahul Santhanam |
Unconditional Lower Bounds against Advice. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow |
A Simple Proof of Toda's Theorem. |
Theory of Computing |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow |
The status of the P versus NP problem. |
Commun. ACM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow |
Viewpoint - Time for computer science to grow up. |
Commun. ACM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Joshua A. Grochow |
Complexity Classes of Equivalence Problems Revisited |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Bounding Rationality by Discounting Time |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff |
Derandomizing from Random Strings |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Luis Filipe Coelho Antunes, Lance Fortnow |
Sophistication Revisited. |
Theory Comput. Syst. |
2009 |
DBLP DOI BibTeX RDF |
Kolmogorov complexity |
| 1 | Lance Fortnow, Adam R. Klivans |
Efficient learning algorithms yield circuit lower bounds. |
J. Comput. Syst. Sci. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Rahul Santhanam |
Unconditional Lower Bounds against Advice. |
ICALP |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | John Chuang, Lance Fortnow, Pearl Pu (eds.) |
Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009 |
ACM Conference on Electronic Commerce |
2009 |
DBLP BibTeX RDF |
|
| 1 | Nikhil R. Devanur, Lance Fortnow |
A computational theory of awareness and decision making. |
TARK |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow |
Program equilibria and discounted computation time. |
TARK |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam, Ryan Williams |
Fixed-Polynomial Size Circuit Bounds. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luis Filipe Coelho Antunes, Lance Fortnow |
Worst-Case Running Times for Average-Case Algorithms. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil R. Devanur, Lance Fortnow |
A Computational Theory of Awareness and Decision Making. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans |
On the Complexity of Succinct Zero-Sum Games. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
91A05, 68Q17, Subject classification. 68Q15, 03D15, 68Q32 |
| 1 | Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman |
Complexity of Combinatorial Market Makers |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rakesh V. Vohra |
The complexity of forecast testing. |
SIGecom Exchanges |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig |
Quantum Property Testing. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf (eds.) |
Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 |
Algebraic Methods in Computational Complexity |
2008 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rakesh Vohra |
The complexity of forecast testing: abstract. |
ACM Conference on Electronic Commerce |
2008 |
DBLP DOI BibTeX RDF |
forecast testing, interactive proofs |
| 1 | Lance Fortnow, John Riedl, Tuomas Sandholm (eds.) |
Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008 |
ACM Conference on Electronic Commerce |
2008 |
DBLP BibTeX RDF |
|
| 1 | Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman |
Complexity of combinatorial market makers. |
ACM Conference on Electronic Commerce |
2008 |
DBLP DOI BibTeX RDF |
logarithmic market scoring rule market makers, online learning with expert advice, prediction markets |
| 1 | Lance Fortnow, Rahul Santhanam |
Infeasibility of instance compression and succinct PCPs for NP. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
instance compression, succinct PCPs, cryptography, parameterized complexity, polynomial hierarchy |
| 1 | Lance Fortnow, Rahul Santhanam |
Time Hierarchies: A Survey. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Infeasibility of Instance Compression and Succinct PCPs for NP. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock |
Combinatorial betting. |
SIGecom Exchanges |
2007 |
DBLP DOI BibTeX RDF |
expressive betting, order matching, computational complexity, mechanism design, prediction markets |
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin |
Inverting Onto Functions and Polynomial Hierarchy. |
CSR |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen |
Bluffing and Strategic Reticence in Prediction Markets. |
WINE |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf |
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. |
Algebraic Methods in Computational Complexity |
2007 |
DBLP BibTeX RDF |
|
| 1 | Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf |
07411 Executive Summary -- Algebraic Methods in Computational Complexity. |
Algebraic Methods in Computational Complexity |
2007 |
DBLP BibTeX RDF |
|
| 1 | Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock |
Betting on permutations. |
ACM Conference on Electronic Commerce |
2007 |
DBLP DOI BibTeX RDF |
expressive betting, order matching, computational complexity, prediction market |
| 1 | Luis Antunes 0002, Lance Fortnow, Alexandre Pinto, Andre Souto |
Low-Depth Witnesses are Easy to Find. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rakesh Vohra |
The Complexity of Forecast Testing. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin |
Inverting onto functions might not be hard. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Luis Antunes 0002, Lance Fortnow, Alexandre Pinto, Andre Souto |
Low-Depth Witnesses are Easy to Find. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Fixed-Polynomial Size Circuit Bounds. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Luis Antunes 0002, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran |
Computational depth: Concept and applications. |
Theor. Comput. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Lance Fortnow |
Tolerant Versus Intolerant Testing for Boolean Properties. |
Theory of Computing |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2006 |
DBLP BibTeX RDF |
|
| 1 | Richard Beigel, Lance Fortnow, William I. Gasarch |
A tight lower bound for restricted pir protocols. |
Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification |
| 1 | Richard Beigel, Lance Fortnow, Frank Stephan |
Infinitely-Often Autoreducible Sets. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. |
ICALP |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Mitsunori Ogihara |
Very Sparse Leaf Languages. |
MFCS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Adam R. Klivans |
Linear Advice for Randomized Logarithmic Space. |
STACS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin |
Kolmogorov Complexity with Error. |
STACS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Adam R. Klivans |
Efficient Learning Algorithms Yield Circuit Lower Bounds. |
COLT |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Luis Antunes 0002 |
Time-Bounded Universal Distributions |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Adam R. Klivans |
Linear Advice for Randomized Logarithmic Space |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami |
Computation in a distributed information market. |
Theor. Comput. Sci. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman |
Betting Boolean-style: a framework for trading in securities based on logical formulas. |
Decision Support Systems |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas |
Time-space lower bounds for satisfiability. |
J. ACM |
2005 |
DBLP DOI BibTeX RDF |
Complexity of satisfiability, time-space lower bounds |
| 1 | Harry Buhrman, Lance Fortnow, Aduri Pavan |
Some Results on Derandomization. |
Theory Comput. Syst. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Jack H. Lutz |
Prediction and dimension. |
J. Comput. Syst. Sci. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
Increasing Kolmogorov Complexity. |
STACS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Thomas Thierauf (eds.) |
Algebraic Methods in Computational Complexity, 10.-15. October 2004 |
Algebraic Methods in Computational Complexity |
2005 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Adam R. Klivans |
NP with Small Advice. |
IEEE Conference on Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Lance Fortnow |
Tolerant Versus Intolerant Testing for Boolean Properties. |
IEEE Conference on Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans |
On the Complexity of Succinct Zero-Sum Games. |
IEEE Conference on Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam, Luca Trevisan |
Hierarchies for semantic classes. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
hierarchy theorems, semantic classes, advice |
| 1 | Lance Fortnow |
Beyond NP: the work and legacy of Larry Stockmeyer. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
Larry Stockmeyer, aternation, polynomial-time hierarchy |
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
Increasing Kolmogorov Complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin |
Kolmogorov Complexity with Error |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Adam R. Klivans |
NP with Small Advice |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam, Luca Trevisan |
Promise Hierarchies |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | 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 |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Eldar Fischer, Lance Fortnow |
Tolerant Versus Intolerant Testing for Boolean Properties |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans |
On the complexity of succinct zero-sum games |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow |
Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. |
SIGACT News |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Thomas Thierauf |
04421 Abstracts Collection - Algebraic Methods in Computational Complexity. |
Algebraic Methods in Computational Complexity |
2004 |
DBLP BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam |
Hierarchy Theorems for Probabilistic Polynomial Time. |
FOCS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Beigel, Lance Fortnow, William I. Gasarch |
A Nearly Tight Bound for Private Information Retrieval Protocols |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Rodney G. Downey, Lance Fortnow |
Uniformly hard languages. |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow |
One complexity theorist's view of quantum computing. |
Theor. Comput. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers |
Inverting onto functions. |
Inf. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li |
An oracle builder's toolkit. |
Inf. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Steven Homer |
A Short History of Computational Complexity. |
Bulletin of the EATCS |
2003 |
DBLP BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig |
Quantum property testing. |
SODA |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler |
Sublinear-time approximation of Euclidean minimum spanning tree. |
SODA |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Luis Antunes 0002, Lance Fortnow |
Sophistication Revisited. |
ICALP |
2003 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")