Pseudorandom generators and learning algorithms for AC^0

DOI10.1145/195058.195236MaRDI QIDQ2817639zbMATH OpenOpenAlexFDO

Authors Meera Sitharam

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20)

Recommendations

• Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
• PAC learning depth-3 \(\mathrm{AC}^0\) circuits of bounded top fanin
• Constant depth circuits, Fourier transform, and learnability
• scientific article; zbMATH DE number 2080214
• Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions

Cited in

(5)

• Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
• Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions
• Constant depth circuits, Fourier transform, and learnability
• AC0 unpredictability
• On Fourier analysis of sparse Boolean functions over certain abelian groups

This page was built for publication: Pseudorandom generators and learning algorithms for \(\mathrm{AC}^0\)

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