Efficient Learning Algorithms Yield Circuit Lower Bounds

DOI10.1007/11776420_27zbMath1143.68415OpenAlexW1616946822MaRDI QIDQ5307579

Adam R. Klivans, Lance J. Fortnow

Publication date: 14 September 2007

Published in: Learning Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11776420_27

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Random arithmetic formulas can be reconstructed efficiently ⋮ Mining circuit lower bound proofs for meta-algorithms

This page was built for publication: Efficient Learning Algorithms Yield Circuit Lower Bounds