Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)

DOI10.1016/j.jcss.2003.07.007zbMath1073.68036OpenAlexW1517311456MaRDI QIDQ1887713

Adam R. Klivans, Rocco A. Servedio

Publication date: 22 November 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.07.007

zbMATH Keywords

Computational learning theoryDisjunctive Normal FormPolynomial threshold function

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (36)

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Approximate Degree in Classical and Quantum Computing ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ On (simple) decision tree rank ⋮ Linear threshold functions in decision lists, decision trees, and depth-2 circuits ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions ⋮ Algorithmic Polynomials ⋮ Solving linear constraints over real and rational fields ⋮ The hardest halfspace ⋮ Learning unions of \(\omega(1)\)-dimensional rectangles ⋮ Maximum patterns in datasets ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ Degree-uniform lower bound on the weights of polynomials with given sign function ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ On the modulo degree complexity of Boolean functions ⋮ Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ Sign rank vs discrepancy ⋮ Unnamed Item ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast learning of \(k\)-term DNF formulas with queries.
• The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant
• Approximate inclusion-exclusion
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Majority gates vs. general weighted threshold gates
• A polynomial-time algorithm for learning noisy linear threshold functions
• A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
• Worst-case analysis of the Perceptron and Exponentiated Update algorithms
• On using the Fourier transform to learn disjoint DNF
• On learning monotone DNF formulae under uniform distributions
• The expressive power of voting polynomials
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Learning decision trees from random examples
• A general lower bound on the number of examples needed for learning
• A subexponential exact learning algorithm for DNF using equivalence queries
• Classification by polynomial surfaces
• Boosting a weak learning algorithm by majority
• On learning visual concepts and DNF formulae
• Large margin classification using the perceptron algorithm
• Learning monotone log-term DNF formulas under the uniform distribution
• Queries and concept learning
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Efficient noise-tolerant learning from statistical queries
• Parity, circuits, and the polynomial-time hierarchy
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• SeparatingPH fromPP by relativization

This page was built for publication: Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)