Learning intersections and thresholds of halfspaces

DOI10.1016/j.jcss.2003.11.002zbMath1074.68026OpenAlexW2110503949MaRDI QIDQ598257

Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio

Publication date: 6 August 2004

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.11.002

zbMATH Keywords

Fourier analysisComputational learning theoryHalfspacesNoise sensitivityPolynomial threshold functions

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (32)

A characterization of 2-threshold functions via pairs of prime segments ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ On the proliferation of support vectors in high dimensions* ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Fooling Polytopes ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ On the hardness of learning intersections of two halfspaces ⋮ The regularized least squares algorithm and the problem of learning halfspaces ⋮ Polynomial regression under arbitrary product distributions ⋮ Algorithmic Polynomials ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ Learning intersections of halfspaces with a margin ⋮ Noise stability of weighted majority ⋮ The hardest halfspace ⋮ Noise stability and correlation with half spaces ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning regular sets from queries and counterexamples
• PAC learning intersections of halfspaces with membership queries
• Learning with unreliable boundary queries
• Harmonic analysis and Boolean function complexity
• On using the Fourier transform to learn disjoint DNF
• The expressive power of voting polynomials
• Learning an intersection of a constant number of halfspaces over a uniform distribution
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• A simple algorithm for learning O(log n)-term DNF
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• PP is closed under intersection
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Learning monotone log-term DNF formulas under the uniform distribution
• Queries and concept learning
• Threshold circuits of bounded depth
• Rational approximation to \(|x|\)
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Constant depth circuits, Fourier transform, and learnability
• The Perceptron: A Model for Brain Functioning. I
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• On the Fourier spectrum of monotone functions
• Learning DNF in time
• Cryptographic hardness of distribution-specific learning
• Hardness amplification within NP
• Noise sensitivity of Boolean functions and applications to percolation

This page was built for publication: Learning intersections and thresholds of halfspaces