Learning $$AC^0$$ Under k-Dependent Distributions

DOI10.1007/978-3-319-55911-7_14zbMath1485.68121OpenAlexW2600155308MaRDI QIDQ2988821

Yanli Ren, Ning Ding, Da-Wu Gu

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_14

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• The expressive power of voting polynomials
• Toward efficient agnostic learning
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• A slight sharpening of LMN
• Polynomial regression under arbitrary product distributions
• Threshold circuits of bounded depth
• Constant depth circuits, Fourier transform, and learnability
• Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
• Agnostically Learning Halfspaces
• Learning and Lower Bounds for AC 0 with Threshold Gates
• A theory of the learnable
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy

This page was built for publication: Learning $$AC^0$$ Under k-Dependent Distributions