A Slight Sharpening of LMN

No abstract is available for this paper.

• Publication year

  2001

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2001-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1006/JCSS.2001.1803
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• The Probabilistic Method

  1998cited by this paper
• A switching lemma primer

  1994cited by this paper
• An O(nlog log n) learning algorithm for DNF under the uniform distribution

  1992cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989influential reference
• Computational limitations of small-depth circuits

  1987cited by this paper
• Almost optimal lower bounds for small depth circuits

  1986cited by this paper
• ∑11-Formulae on finite structures

  1983cited by this paper
• Parity, circuits, and the polynomial-time hierarchy

  1981cited by this paper

• The Probably Approximately Correct Learning Model in Computational Learning Theory

  2025cites this paper
• Learning junta distributions, quantum junta states, and QAC$^0$ circuits

  2024cites this paper
• Optimal Non-adaptive Tolerant Junta Testing via Local Estimators

  2024cites this paper
• A Technique for Hardness Amplification Against $\mathrm{AC}^0$

  2023cites this paper
• On the Pauli Spectrum of QAC0

  2023cites this paper
• Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees

  2022cites this paper
• Discrete Analysis

  2022cites this paper
• Low-degree learning and the metric entropy of polynomials

  2022cites this paper
• From Local Pseudorandom Generators to Hardness of Learning

  2021cites this paper
• Quantum State Classification via Quantum Fourier

  2021cites this paper
• A Low Degree Learning Algorithm for Quantum Data via Quantum Fourier

  2021cites this paper
• Coin Theorems and the Fourier Expansion

  2019cites this paper
• Learning AC0 Under k-Dependent Distributions

  2017cites this paper
• PAC Learning Depth-3 AC 0 Circuits of Bounded Top Fanin

  2017cites this paper
• Tight bounds on The Fourier Spectrum of AC0

  2017cites this paper
• Learning Constant-Depth Circuits (1993; Linial, Mansour, Nisan).

  2015cites this paper
• Analysis of Boolean Functions

  2014cites this paper
• The Distinguishability of Product Distributions by Read-Once Branching Programs

  2013cites this paper
• On the Average Sensitivity and Density of k-CNF Formulas

  2013cites this paper
• On K-wise Independent Distributions and Boolean Functions

  2012cites this paper
• Learning, cryptography, and the average case

  2010cites this paper
• Polynomial regression under arbitrary product distributions

  2010cites this paper
• Learning and Lower Bounds for AC0 with Threshold Gates

  2010cites this paper
• Poly-logarithmic Independence Fools AC^0 Circuits

  2009cites this paper
• Variable Influences in Conjunctive Normal Forms

  2009cites this paper
• Learning Constant-Depth Circuits

  2008cites this paper
• Threshold Phenomena and Influence, with Some Perspectives from Mathematics, Computer Science, and Economics

  2005cites this paper
• Threshold Phenomena and Influence

  2005cites this paper
• Threshold Phenomena and Influence with Some Perspectives from Mathematics , Computer Science , and Economics

  2005cites this paper