Learning Decision Trees Using the Fourier Spectrum
From MaRDI portal
Publication:4277547
DOI10.1137/0222080zbMath0799.68159OpenAlexW2095546965MaRDI QIDQ4277547
Eyal Kushilevitz, Yishay Mansour
Publication date: 24 November 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222080
Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)
Related Items (57)
More efficient PAC-learning of DNF with membership queries under the uniform distribution ⋮ Spatio-spectral limiting on Boolean cubes ⋮ Improved sparse Fourier approximation results: Faster implementations and stronger guarantees ⋮ Book Review: A mathematical introduction to compressive sensing ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Exact learning from an honest teacher that answers membership queries ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Simple learning algorithms using divide and conquer ⋮ Evaluating spectral norms for constant depth circuits with symmetric gates ⋮ Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky ⋮ Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\) ⋮ List-decoding Barnes-Wall lattices ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ Erasures versus errors in local decoding and property testing ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Learning random monotone DNF ⋮ Exact learning of subclasses of CDNF formulas with membership queries ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ A recursive procedure for density estimation on the binary hypercube ⋮ Covert learning: how to learn with an untrusted intermediary ⋮ Reliable agnostic learning ⋮ Towards a proof of the Fourier-entropy conjecture? ⋮ The monotone theory for the PAC-model. ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Quantum algorithms for learning and testing juntas ⋮ Preserving Randomness for Adaptive Algorithms ⋮ The power of amnesia: Learning probabilistic automata with variable memory length ⋮ Learning unions of \(\omega(1)\)-dimensional rectangles ⋮ Rapidly computing sparse Legendre expansions via sparse Fourier transforms ⋮ On the structure of Boolean functions with small spectral norm ⋮ Randomized interpolation and approximation of sparse polynomials stPreliminary version ⋮ On the modulo degree complexity of Boolean functions ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ What's the frequency, Kenneth?: sublinear Fourier sampling off the grid ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Separating models of learning with faulty teachers ⋮ Unnamed Item ⋮ Boolean functions with small spectral norm, revisited ⋮ Parameterized learnability of juntas ⋮ Coset decision trees and the Fourier algebra ⋮ Unnamed Item ⋮ Reconstructing Algebraic Functions from Mixed Data ⋮ Learning DNF from random walks ⋮ Learning with queries corrupted by classification noise ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum algorithms for learning Walsh spectra of multi-output Boolean functions ⋮ Quantum learning of concentrated Boolean functions ⋮ Unnamed Item ⋮ Rates of minimization of error functionals over Boolean variable-basis functions ⋮ On the isomorphism problem for decision trees and decision lists ⋮ Population recovery and partial identification ⋮ A note on the high-dimensional sparse Fourier transform in the continuous setting* ⋮ A multiscale sub-linear time Fourier algorithm for noisy data
This page was built for publication: Learning Decision Trees Using the Fourier Spectrum
