# Rocco A. Servedio

According to our database1, Rocco A. Servedio authored at least 271 papers between 1999 and 2019.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
Distribution-free Junta Testing.
ACM Trans. Algorithms, 2019

A Lower Bound on Cycle-Finding in Sparse Digraphs.
CoRR, 2019

Efficient average-case population recovery in the presence of insertions and deletions.
CoRR, 2019

Learning from satisfying assignments under continuous distributions.
CoRR, 2019

Beyond trace reconstruction: Population recovery from the deletion channel.
CoRR, 2019

Fooling polytopes.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Density Estimation for Shift-Invariant Multidimensional Distributions.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Simple and Efficient Pseudorandom Generators from Gaussian Processes.
Proceedings of the 34th Computational Complexity Conference, 2019

Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas.
Proceedings of the Approximation, 2019

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.
Proceedings of the Approximation, 2019

2018
Settling the Query Complexity of Non-adaptive Junta Testing.
J. ACM, 2018

Fooling Polytopes.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Simple and efficient pseudorandom generators from Gaussian processes.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Density estimation for shift-invariant multidimensional distributions.
CoRR, 2018

Learning sparse mixtures of rankings from noisy information.
CoRR, 2018

Fooling Polytopes.
CoRR, 2018

Learning Sums of Independent Random Variables with Sparse Collective Support.
CoRR, 2018

Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits.
CoRR, 2018

Distribution-free Junta Testing.
CoRR, 2018

Improved pseudorandom generators from pseudorandom multi-switching lemmas.
CoRR, 2018

Deterministic search for CNF satisfying assignments in almost polynomial time.
CoRR, 2018

Distribution-free junta testing.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Learning Sums of Independent Random Variables with Sparse Collective Support.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits.
Proceedings of the Approximation, 2018

2017
An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
J. ACM, 2017

The Inverse Shapley value problem.
Games and Economic Behavior, 2017

Settling the query complexity of non-adaptive junta testing.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Fooling intersections of low-weight halfspaces.
CoRR, 2017

Sharp bounds for population recovery.
CoRR, 2017

Settling the query complexity of non-adaptive junta testing.
CoRR, 2017

Sample-based high-dimensional convexity testing.
CoRR, 2017

Adaptivity is exponentially powerful for testing monotonicity of halfspaces.
CoRR, 2017

Optimal mean-based algorithms for trace reconstruction.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Addition is exponentially harder than counting for shallow monotone circuits.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

What Circuit Classes Can Be Learned with Non-Trivial Savings?.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Fooling Intersections of Low-Weight Halfspaces.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Settling the Query Complexity of Non-Adaptive Junta Testing.
Proceedings of the 32nd Computational Complexity Conference, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.
Proceedings of the Approximation, 2017

Sample-Based High-Dimensional Convexity Testing.
Proceedings of the Approximation, 2017

2016
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry.
SIAM J. Discrete Math., 2016

Degree and Sensitivity: tails of two distributions.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Degree and Sensitivity: tails of two distributions.
CoRR, 2016

Optimal mean-based algorithms for trace reconstruction.
CoRR, 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Near-optimal small-depth lower bounds for small distance connectivity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Degree and Sensitivity: Tails of Two Distributions.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.
SIGACT News, 2015

Testing Probability Distributions using Conditional Samples.
SIAM J. Comput., 2015

An average-case depth hierarchy theorem for Boolean circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Addition is exponentially harder than counting for shallow monotone circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2015

An average-case depth hierarchy theorem for Boolean circuits.
CoRR, 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
CoRR, 2015

Near-optimal small-depth lower bounds for small distance connectivity.
CoRR, 2015

Addition is exponentially harder than counting for shallow monotone circuits.
CoRR, 2015

Noise Stable Halfspaces are Close to Very Small Juntas.
Chicago J. Theor. Comput. Sci., 2015

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
Algorithmica, 2015

Learning Poisson Binomial Distributions.
Algorithmica, 2015

Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Learning from satisfying assignments.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Proceedings of the 30th Conference on Computational Complexity, 2015

Learning Circuits with few Negations.
Proceedings of the Approximation, 2015

2014
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions.
Theory of Computing, 2014

Learning k-Modal Distributions via Testing.
Theory of Computing, 2014

On the Weight of Halfspaces over Hamming Balls.
SIAM J. Discrete Math., 2014

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.
SIAM J. Comput., 2014

Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces.
J. ACM, 2014

Learning circuits with few negations.
Electronic Colloquium on Computational Complexity (ECCC), 2014

New algorithms and lower bounds for monotonicity testing.
CoRR, 2014

Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries.
CoRR, 2014

Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.
CoRR, 2014

Learning circuits with few negations.
CoRR, 2014

Efficient deterministic approximate counting for low-degree polynomial threshold functions.
Proceedings of the Symposium on Theory of Computing, 2014

Efficient density estimation via piecewise polynomial approximation.
Proceedings of the Symposium on Theory of Computing, 2014

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Testing equivalence between distributions using conditional samples.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

On DNF Approximators for Monotone Boolean Functions.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

New Algorithms and Lower Bounds for Monotonicity Testing.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013
Algorithms and hardness results for parallel large margin learning.
J. Mach. Learn. Res., 2013

Exponentially improved algorithms and lower bounds for testing signed majorities.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Efficient deterministic approximate counting for low degree polynomial threshold functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Efficient Density Estimation via Piecewise Polynomial Approximation
CoRR, 2013

Efficient deterministic approximate counting for low-degree polynomial threshold functions.
CoRR, 2013

Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions.
CoRR, 2013

Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions.
CoRR, 2013

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.
CoRR, 2013

Improved Approximation of Linear Threshold Functions.
Computational Complexity, 2013

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Testing k-Modal Distributions: Optimal Algorithms via Reductions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Learning mixtures of structured distributions over discrete domains.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Low-weight halfspaces for sparse boolean vectors.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Consistency versus Realizable H-Consistency for Multiclass Classification.
Proceedings of the 30th International Conference on Machine Learning, 2013

A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Learning Sums of Independent Integer Random Variables.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009).
SIAM J. Comput., 2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.
Proceedings of the COLT 2012, 2012

Tight Bounds on Proper Equivalence Query Learning of DNF.
Proceedings of the COLT 2012, 2012

On a special case of rigidity.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

The Inverse Shapley Value Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Inverse Problems in Approximate Uniform Generation.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing probability distributions using conditional samples.
Electronic Colloquium on Computational Complexity (ECCC), 2012

The Inverse Shapley Value Problem
CoRR, 2012

Testing probability distributions using conditional samples
CoRR, 2012

Inverse problems in approximate uniform generation
CoRR, 2012

Learning mixtures of structured distributions over discrete domains
CoRR, 2012

A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry.
CoRR, 2012

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces
CoRR, 2012

On the Distribution of the Fourier Spectrum of Halfspaces
CoRR, 2012

A high-dimensional surprise: technical perspective.
Commun. ACM, 2012

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Learning poisson binomial distributions.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Private data release via learning thresholds.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Learning k-modal distributions via testing.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

The Inverse Shapley Value Problem.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
The Chow Parameters Problem.
SIAM J. Comput., 2011

Testing Fourier Dimensionality and Sparsity.
SIAM J. Comput., 2011

Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
Proceedings of the COLT 2011, 2011

Learning random monotone DNF.
Discrete Applied Mathematics, 2011

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions
CoRR, 2011

Tight Bounds on Proper Equivalence Query Learning of DNF
CoRR, 2011

Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms
CoRR, 2011

Learning Poisson Binomial Distributions
CoRR, 2011

Learning $k$-Modal Distributions via Testing
CoRR, 2011

Private Data Release via Learning Thresholds
CoRR, 2011

Learning transformed product distributions
CoRR, 2011

Efficiently Testing Sparse GF(2) Polynomials.
Algorithmica, 2011

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Algorithms and hardness results for parallel large margin learning.
Proceedings of the Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, 2011

Learning large-margin halfspaces with more malicious noise.
Proceedings of the Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, 2011

A Canonical Form for Testing Boolean Function Properties.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Testing Halfspaces.
SIAM J. Comput., 2010

Bounded Independence Fools Halfspaces.
SIAM J. Comput., 2010

Random classification noise defeats all convex potential boosters.
Machine Learning, 2010

Learning and Lower Bounds for AC0 with Threshold Gates.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
CoRR, 2010

New degree bounds for polynomial threshold functions.
Combinatorica, 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Testing by Implicit Learning: A Brief Survey.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing (Subclasses of) Halfspaces.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate.
Proceedings of the 27th International Conference on Machine Learning (ICML-10), 2010

A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

Learning and Lower Bounds for AC0 with Threshold Gates.
Proceedings of the Approximation, 2010

2009
Distribution-Free Testing Lower Bound for Basic Boolean Functions.
Theory of Computing, 2009

Optimal Cryptographic Hardness of Learning Monotone Functions.
Theory of Computing, 2009

Preface.
Theor. Comput. Sci., 2009

Testing monotone high-dimensional distributions.
Random Struct. Algorithms, 2009

Learning Halfspaces with Malicious Noise.
J. Mach. Learn. Res., 2009

Bounded Independence Fools Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Improved Approximation of Linear Threshold Functions
CoRR, 2009

Average sensitivity and noise sensitivity of polynomial threshold functions
CoRR, 2009

A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
CoRR, 2009

Bounded Independence Fools Halfspaces
CoRR, 2009

Testing halfspaces.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Learning Halfspaces with Malicious Noise.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Testing Fourier Dimensionality and Sparsity.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Bounded Independence Fools Halfspaces.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Improved Approximation of Linear Threshold Functions.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Testing ±1-weight halfspace.
Proceedings of the Approximation, 2009

2008
Learning Constant-Depth Circuits.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Learning unions of omega(1)-dimensional rectangles.
Theor. Comput. Sci., 2008

Agnostically Learning Halfspaces.
SIAM J. Comput., 2008

Learning Mixtures of Product Distributions over Discrete Domains.
SIAM J. Comput., 2008

Extremal properties of polynomial threshold functions.
J. Comput. Syst. Sci., 2008

Learning intersections of halfspaces with a margin.
J. Comput. Syst. Sci., 2008

Efficiently Testing Sparse GF(2) Polynomials
CoRR, 2008

The chow parameters problem.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Random classification noise defeats all convex potential boosters.
Proceedings of the Machine Learning, 2008

Efficiently Testing Sparse GF(2) Polynomials.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Optimal Cryptographic Hardness of Learning Monotone Functions.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Learning Geometric Concepts via Gaussian Surface Area.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Learning Random Monotone DNF.
Proceedings of the Approximation, 2008

2007
LP Decoding Corrects a Constant Fraction of Errors.
IEEE Trans. Information Theory, 2007

On PAC learning algorithms for rich Boolean function classes.
Theor. Comput. Sci., 2007

Learning Monotone Decision Trees in Polynomial Time.
SIAM J. Comput., 2007

Quantum Algorithms for Learning and Testing Juntas.
Quantum Information Processing, 2007

DNF are teachable in the average case.
Machine Learning, 2007

Separating Models of Learning from Correlated and Uncorrelated Data.
J. Mach. Learn. Res., 2007

Discriminative learning can succeed where generative learning fails.
Inf. Process. Lett., 2007

Testing Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Learning Random Monotone DNF.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Testing for Concise Representations.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Quantum Algorithms for Learning and Testing Juntas
CoRR, 2007

Every Linear Threshold Function has a Low-Weight Approximator.
Computational Complexity, 2007

Boosting the Area under the ROC Curve.
Proceedings of the Advances in Neural Information Processing Systems 20, 2007

One-Pass Boosting.
Proceedings of the Advances in Neural Information Processing Systems 20, 2007

Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Testing for Concise Representations.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Distribution-Free Testing Lower Bounds for Basic Boolean Functions.
Proceedings of the Approximation, 2007

Editors' Introduction.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006
On Learning Random DNF Formulas Under the Uniform Distribution.
Theory of Computing, 2006

On learning embedded midbit functions.
Theor. Comput. Sci., 2006

Toward Attribute Efficient Learning of Decision Lists and Parities.
J. Mach. Learn. Res., 2006

Polynomial certificates for propositional classes.
Inf. Comput., 2006

PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption
CoRR, 2006

On PAC Learning Algorithms for Rich Boolean Function Classes.
Proceedings of the Theory and Applications of Models of Computation, 2006

Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions.
Proceedings of the Advances in Neural Information Processing Systems 19, 2006

Discriminative Learning Can Succeed Where Generative Learning Fails.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

DNF Are Teachable in the Average Case.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

Every Linear Threshold Function has a Low-Weight Approximator.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Learning Monotone Decision Trees in Polynomial Time.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Learning Unions of omega(1)-Dimensional Rectangles.
Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005
Learning Random Log-Depth Decision Trees under Uniform Distribution.
SIAM J. Comput., 2005

Improved Bounds on Quantum Learning Algorithms.
Quantum Information Processing, 2005

Maximum Margin Algorithms with Boolean Kernels.
J. Mach. Learn. Res., 2005

Boosting in the presence of noise.
J. Comput. Syst. Sci., 2005

Learning DNF from random walks.
J. Comput. Syst. Sci., 2005

Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms.
J. Artif. Intell. Res., 2005

Computing sparse permanents faster.
Inf. Process. Lett., 2005

Learning Unions of $\omega(1)$-Dimensional Rectangles
CoRR, 2005

Every decision tree has an influential variable
CoRR, 2005

Testing monotone high-dimensional distributions.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Unsupervised evidence integration.
Proceedings of the Machine Learning, 2005

Learning mixtures of product distributions over discrete domains.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Every decision tree has an in.uential variable.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Agnostically Learning Halfspaces.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Martingale Boosting.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

Separating Models of Learning from Correlated and Uncorrelated Data.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

On Learning Random DNF Formulas Under the Uniform Distribution.
Proceedings of the Approximation, 2005

2004
Equivalences and Separations Between Quantum and Classical Learnability.
SIAM J. Comput., 2004

Learning functions of k relevant variables.
J. Comput. Syst. Sci., 2004

Learning DNF in time 2Õ(n1/3).
J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.
J. Comput. Syst. Sci., 2004

On learning monotone DNF under product distributions.
Inf. Comput., 2004

Monotone Boolean formulas can approximate monotone linear threshold functions.
Discrete Applied Mathematics, 2004

Improved Bounds on Quantum Learning Algorithms
CoRR, 2004

LP decoding corrects a constant fraction of errors.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Toward Attribute Efficient Learning of Decision Lists and Parities.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

Perceptron-Like Performance for Intersections of Halfspaces.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

Learning Intersections of Halfspaces with a Margin.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003
Boosting and Hard-Core Set Construction.
Machine Learning, 2003

Smooth Boosting and Learning with Malicious Noise.
J. Mach. Learn. Res., 2003

Toward Attribute Efficient Learning Algorithms
CoRR, 2003

New degree bounds for polynomial threshold functions.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Learning juntas.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Boosting in the presence of noise.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Learning DNF from Random Walks.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Maximum Margin Algorithms with Boolean Kernels.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Learning Random Log-Depth Decision Trees under the Uniform Distribution.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Polynomial Certificates for Propositional Classes.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Extremal properties of polynomial threshold functions.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Perceptron, Winnow, and PAC Learning.
SIAM J. Comput., 2002

PAC Analogues of Perceptron and Winnow Via Boosting the Margin.
Machine Learning, 2002

Learning Intersections and Thresholds of Halfspaces.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Learnability beyond AC0.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

On Learning Embedded Midbit Functions.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002

2001
On the limits of efficient teachability.
Inf. Process. Lett., 2001

On Learning Monotone DNF under Product Distributions
Electronic Colloquium on Computational Complexity (ECCC), 2001

Learning DNF in time 2Õ(n1/3).
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms.
Proceedings of the Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, 2001

Separating Quantum and Classical Learning.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

On Learning Monotone DNF under Product Distributions.
Proceedings of the Computational Learning Theory, 2001

Smooth Boosting and Learning with Malicious Noise.
Proceedings of the Computational Learning Theory, 2001

Quantum versus Classical Learnability.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
Computational Sample Complexity and Attribute-Efficient Learning.
J. Comput. Syst. Sci., 2000

PAC Analogues of Perceptron and Winnow via Boosting the Margin.
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999
Computational Sample Complexity and Attribute-Efficient Learning.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Boosting and Hard-Core Sets.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999