Learnability beyond AC 0

DOI10.1145/509907.510018zbMath1192.68390OpenAlexW2112556578MaRDI QIDQ3579219

Adam R. Klivans, Jeffrey C. Jackson, Rocco A. Servedio

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.510018

Mathematics Subject Classification ID

Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

The complexity of properly learning simple concept classes ⋮ Learning unions of \(\omega(1)\)-dimensional rectangles ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Learning large-alphabet and analog circuits with value injection queries ⋮ Learning a circuit by injecting values ⋮ Unnamed Item ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation

This page was built for publication: Learnability beyond AC ⁰