178 citations · 217 across the 15 of their papers we have counts for
17 papers
and a Random-Oracle Proof of Toda's Theorem
Lance Fortnow
Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between -polynomials and the XOR of majorities, we show that $\ma…
How Does Machine Learning Manage Complexity?
Lance Fortnow
We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems. Machine learning models are ofte…
The CFG Complexity of Singleton Sets
Lance Fortnow, William Gasarch
Let G be a context-free grammar (CFG) in Chomsky normal form. We take the number of rules in G to be the size of G. We also assume all CFGs are in Chomsky normal form. We consider…
Compression Complexity
Stephen Fenner, Lance Fortnow
The Kolmogorov complexity of x, denoted C(x), is the length of the shortest program that generates x. For such a simple definition, Kolmogorov complexity has a rich and deep theory…
Multi-outcome and Multidimensional Market Scoring Rules
Lance Fortnow, Rahul Sami
Hanson's market scoring rules allow us to design a prediction market that still gives useful information even if we have an illiquid market with a limited number of budget-constrai…
Repeated Matching Pennies with Limited Randomness
Michele Budinich, Lance Fortnow
We consider a repeated Matching Pennies game in which players have limited access to randomness. Playing the (unique) Nash equilibrium in this n-stage game requires n random bits.…