2 papers
cs.LG2026
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…
cs.FL2024
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…