On PAC learning algorithms for rich Boolean function classes

DOI10.1016/J.TCS.2007.05.018zbMATH Open1124.68052OpenAlexW2524932090MaRDI QIDQ2382283FDOQ2382283

Authors: Lisa Hellerstein, Rocco A. Servedio 

Publication date: 28 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.018

Recommendations

• Learning juntas
• What circuit classes can be learned with non-trivial savings?
• Learning functions of \(k\) relevant variables
• Learning sparse polynomial functions
• Learning from satisfying assignments

zbMATH Keywords

computational learning theoryPAC learningpolynomial threshold function

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Cites Work

• A decision-theoretic generalization of on-line learning and an application to boosting
• Learnability and the Vapnik-Chervonenkis dimension
• Learning Decision Trees Using the Fourier Spectrum
• Title not available (Why is that?)
• Learning regular sets from queries and counterexamples
• Title not available (Why is that?)
• Title not available (Why is that?)
• Boosting a weak learning algorithm by majority
• Exact learning Boolean functions via the monotone theory
• Constant depth circuits, Fourier transform, and learnability
• A theory of the learnable
• Occam's razor
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• On learning width two branching programs
• Efficient noise-tolerant learning from statistical queries
• Title not available (Why is that?)
• PP is closed under intersection
• On the Size of Weights for Threshold Gates
• Approximate inclusion-exclusion
• Computing Boolean functions by polynomials and threshold circuits
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Theory of majority decision elements
• On the Fourier spectrum of monotone functions
• New degree bounds for polynomial threshold functions
• Learning intersections and thresholds of halfspaces
• Learning decision trees from random examples
• Learning functions represented as multiplicity automata
• Cryptographic hardness of distribution-specific learning
• On Learning Ring-Sum-Expansions
• A subexponential exact learning algorithm for DNF using equivalence queries
• Learning Integer Lattices
• Learning with restricted focus of attention
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Title not available (Why is that?)

Cited In (13)

• An Algebraic Perspective on Boolean Function Learning
• Title not available (Why is that?)
• Sign-representation of Boolean functions using a small number of monomials
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• Title not available (Why is that?)
• On the complexity of compressing obfuscation
• Private data release via learning thresholds
• Agnostically learning Boolean functions with finite polynomial representation
• Learning sparse polynomial functions
• What circuit classes can be learned with non-trivial savings?
• Explaining AI decisions using efficient methods for learning sparse Boolean formulae
• Almost optimal proper learning and testing polynomials
• On learning embedded midbit functions

Uses Software

• AdaBoost.MH

This page was built for publication: On PAC learning algorithms for rich Boolean function classes

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