Learnability beyond AC 0

DOI10.1145/509907.510018MaRDI QIDQ3579219zbMATH OpenOpenAlexFDO

Authors Jeffrey Jackson, Adam R. Klivans, 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

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

Cited in

(9)

• Learning large-alphabet and analog circuits with value injection queries
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• The complexity of properly learning simple concept classes
• Agnostically learning Boolean functions with finite polynomial representation
• Private data release via learning thresholds
• Learning a circuit by injecting values
• On the constant-depth circuit complexity of generating quasigroups
• Constant depth circuit complexity for generating quasigroups
• Learning unions of (1)-dimensional rectangles

This page was built for publication: Learnability beyond AC ⁰

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579219)