Lifting uniform learners via distributional decomposition

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Learning intersections and thresholds of halfspaces
Learnability with respect to fixed distributions
Selection of relevant features and examples in machine learning
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Toward efficient agnostic learning
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
Learning decision trees from random examples
PAC learning with nasty noise.
Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
Polynomial regression under arbitrary product distributions
Improving and extending the testing of distributions for shape-restricted properties
Cryptographic hardness for learning intersections of halfspaces
Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model
On the power of conditional samples in distribution testing
Constant depth circuits, Fourier transform, and learnability
Property testing and its connection to learning and approximation
Big Data on the Rise?
Learning Mixtures of Product Distributions over Discrete Domains
Agnostically Learning Halfspaces
A discriminative model for semi-supervised learning
Streaming and sublinear approximation of entropy and information distances
Testing monotone high‐dimensional distributions
A theory of the learnable
Probably Approximate Learning over Classes of Distributions
Learning Decision Trees Using the Fourier Spectrum
Faster Sublinear Algorithms using Conditional Sampling
Robust Characterizations of Polynomials with Applications to Program Testing
Analysis of Boolean Functions
Testing Probability Distributions Underlying Aggregated Data
Distribution Testing Lower Bounds via Reductions from Communication Complexity
Property Testing of Joint Distributions using Conditional Samples
Beyond the low-degree algorithm: mixtures of subcubes and their applications
Testing Probability Distributions using Conditional Samples
A Chasm Between Identity and Equivalence Testing with Conditional Queries
The Intersection of Two Halfspaces Has High Threshold Degree
The Power of Linear Estimators
The Complexity of Approximating the Entropy

This page was built for publication: Lifting uniform learners via distributional decomposition