A slight sharpening of LMN

DOI10.1006/jcss.2001.1803zbMath1052.94506OpenAlexW2070540961WikidataQ56959003 ScholiaQ56959003MaRDI QIDQ1604204

Johan T. Håstad

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5acbf94e8679acdca50bac7f5d70f539315cc5aa

zbMATH Keywords

discrete Fourier transformlearnabilityconstant depth circuit

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Numerical methods for discrete and fast Fourier transforms (65T50) Analytic circuit theory (94C05)

Related Items (4)

Paradigms for Unconditional Pseudorandom Generators ⋮ Polynomial regression under arbitrary product distributions ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Variable Influences in Conjunctive Normal Forms

Cites Work

• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Constant depth circuits, Fourier transform, and learnability
• Parity, circuits, and the polynomial-time hierarchy

This page was built for publication: A slight sharpening of LMN