| Publication | Date of Publication | Type |
|---|
| Learning deep ReLu networks is fixed-parameter tractable | 2025-08-13 | Paper |
| Learning graphical models using multiplicative weights | 2025-08-06 | Paper |
| A moment-matching approach to testable learning and a new characterization of Rademacher complexity | 2024-05-08 | Paper |
Preserving randomness for adaptive algorithms
(available as arXiv preprint) | 2021-08-04 | Paper |
| Submodular functions are noise stable | 2019-05-10 | Paper |
| Embedding hard learning problems into Gaussian space | 2017-03-22 | Paper |
Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Randomness efficient identity testing of multivariate polynomials
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Learning DNF in time
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Bounding the sensitivity of polynomial threshold functions
Theory of Computing | 2014-10-06 | Paper |
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
An invariance principle for polytopes
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
An FPTAS for #Knapsack and Related Counting Problems
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
An invariance principle for polytopes
Journal of the ACM | 2014-02-17 | Paper |
An explicit VC-theorem for low-degree polynomials
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Learning halfspaces with malicious noise
Journal of Machine Learning Research (JMLR) | 2012-04-17 | Paper |
| Toward attribute efficient learning of decision lists and parities | 2011-10-12 | Paper |
scientific article; zbMATH DE number 5899249 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Lower bounds for agnostic learning via approximate rank
Computational Complexity | 2011-02-18 | Paper |
Learnability beyond AC <sup>0</sup>
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Learning arithmetic circuits via partial derivatives.
Lecture Notes in Computer Science | 2010-03-23 | Paper |
Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Learning Halfspaces with Malicious Noise
Automata, Languages and Programming | 2009-07-14 | Paper |
Unconditional lower bounds for learning intersections of halfspaces
Machine Learning | 2009-03-31 | Paper |
Cryptographic hardness for learning intersections of halfspaces
Journal of Computer and System Sciences | 2009-01-09 | Paper |
Efficient learning algorithms yield circuit lower bounds
Journal of Computer and System Sciences | 2009-01-09 | Paper |
| scientific article; zbMATH DE number 5485565 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485538 (Why is no real title available?) | 2009-01-05 | Paper |
Agnostically Learning Halfspaces
SIAM Journal on Computing | 2008-12-22 | Paper |
Linear Advice for Randomized Logarithmic Space
STACS 2006 | 2008-03-19 | Paper |
A Lower Bound for Agnostically Learning Disjunctions
Learning Theory | 2008-01-03 | Paper |
The complexity of properly learning simple concept classes
Journal of Computer and System Sciences | 2007-11-30 | Paper |
Learning intersections of halfspaces with a margin
Journal of Computer and System Sciences | 2007-11-30 | Paper |
Efficient Learning Algorithms Yield Circuit Lower Bounds
Learning Theory | 2007-09-14 | Paper |
Improved Lower Bounds for Learning Intersections of Halfspaces
Learning Theory | 2007-09-14 | Paper |
Learning Theory
Lecture Notes in Computer Science | 2005-06-13 | Paper |
Learning Theory
Lecture Notes in Computer Science | 2005-06-13 | Paper |
Learning Theory
Lecture Notes in Computer Science | 2005-06-13 | Paper |
Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
Journal of Computer and System Sciences | 2004-11-22 | Paper |
Learning intersections and thresholds of halfspaces
Journal of Computer and System Sciences | 2004-08-06 | Paper |
Boosting and hard-core set construction
Machine Learning | 2003-06-25 | Paper |
| scientific article; zbMATH DE number 1833418 (Why is no real title available?) | 2002-11-21 | Paper |
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
SIAM Journal on Computing | 2002-09-29 | Paper |
