On PAC learning algorithms for rich Boolean function classes
From MaRDI portal
Publication:2382283
DOI10.1016/j.tcs.2007.05.018zbMath1124.68052OpenAlexW2524932090MaRDI QIDQ2382283
Rocco A. Servedio, Lisa Hellerstein
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
Related Items
Sign-representation of Boolean functions using a small number of monomials, What Circuit Classes Can Be Learned with Non-Trivial Savings?, Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)], Almost optimal proper learning and testing polynomials, On the complexity of compressing obfuscation, An Algebraic Perspective on Boolean Function Learning, Explaining AI decisions using efficient methods for learning sparse Boolean formulae, Unnamed Item, Agnostically Learning Boolean Functions with Finite Polynomial Representation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On learning width two branching programs
- Learning intersections and thresholds of halfspaces
- Learning regular sets from queries and counterexamples
- Occam's razor
- Approximate inclusion-exclusion
- Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
- Learning with restricted focus of attention
- Computing Boolean functions by polynomials and threshold circuits
- A decision-theoretic generalization of on-line learning and an application to boosting
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Learning decision trees from random examples
- A subexponential exact learning algorithm for DNF using equivalence queries
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- Boosting a weak learning algorithm by majority
- Exact learning Boolean functions via the monotone theory
- Theory of majority decision elements
- Constant depth circuits, Fourier transform, and learnability
- Efficient noise-tolerant learning from statistical queries
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- On Learning Ring-Sum-Expansions
- Learning Integer Lattices
- Learning Decision Trees Using the Fourier Spectrum
- On the Size of Weights for Threshold Gates
- On the Fourier spectrum of monotone functions
- Learning functions represented as multiplicity automata
- Cryptographic hardness of distribution-specific learning
- New degree bounds for polynomial threshold functions
