On learning embedded midbit functions

DOI10.1016/j.tcs.2005.10.013zbMath1086.68067OpenAlexW2124567957MaRDI QIDQ817826

Rocco A. Servedio

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.013

zbMATH Keywords

PAC learningembedded midbit functions

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Depth reduction for circuits of unbounded fan-in
• On ACC
• The power of the middle bit of a \(\#\)P function
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Finite monoids and the fine structure of NC ¹
• On Learning Ring-Sum-Expansions
• Learning Integer Lattices
• Learning DNF in time