| Publication | Date of Publication | Type |
|---|
| Interactive proofs for verifying machine learning | 2026-04-15 | Paper |
A LYM inequality for product measures
Discrete Mathematics | 2025-12-16 | Paper |
| Stability and replicability in learning | 2025-08-15 | Paper |
| A characterization of multiclass learnability | 2025-08-15 | Paper |
| Compressing and teaching for low VC-dimension | 2025-08-05 | Paper |
Fixed and periodic points of the intersection body operator
Inventiones Mathematicae | 2025-07-24 | Paper |
| Direct products in communication complexity | 2025-05-20 | Paper |
| Population recovery and partial identification | 2025-05-05 | Paper |
| Pseudorandom generators for regular branching programs | 2025-04-29 | Paper |
| Average-case information complexity of learning | 2025-01-31 | Paper |
A lower bound for essential covers of the cube
Combinatorica | 2024-09-19 | Paper |
On Blocky Ranks Of Matrices
Computational Complexity | 2024-04-21 | Paper |
Random walks on regular trees can not be slowed down
Electronic Journal of Probability | 2024-04-10 | Paper |
Learnability can be independent of set theory (invited paper)
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A theory of universal learning
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Shadows of Newton polytopes
Israel Journal of Mathematics | 2023-10-23 | Paper |
| The discrepancy of greater-than | 2023-09-15 | Paper |
Sharp isoperimetric inequalities for affine quermassintegrals
(available as arXiv preprint) | 2023-07-31 | Paper |
| Shadows of newton polytopes | 2023-07-12 | Paper |
| Dual Systolic Graphs | 2023-04-11 | Paper |
| Replicability and stability in learning | 2023-04-07 | Paper |
On the perceptron's compression
(available as arXiv preprint) | 2022-12-16 | Paper |
On symmetry and initialization for neural networks
(available as arXiv preprint) | 2022-10-13 | Paper |
Explicit exponential lower bounds for exact hyperplane covers
Discrete Mathematics | 2022-08-24 | Paper |
| Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits | 2022-07-21 | Paper |
| On weak -nets and the Radon number | 2022-07-18 | Paper |
On the Communication Complexity of Key-Agreement Protocols.
(available as arXiv preprint) | 2022-07-18 | Paper |
Anticoncentration and the Exact Gap-Hamming Problem
SIAM Journal on Discrete Mathematics | 2022-05-10 | Paper |
An isoperimetric inequality for Hamming balls and local expansion in hypercubes
The Electronic Journal of Combinatorics | 2022-02-01 | Paper |
Anti-concentration and the Exact Gap-Hamming Problem
(available as arXiv preprint) | 2022-01-04 | Paper |
| Tight bounds on the Fourier growth of bounded functions on the hypercube | 2021-07-13 | Paper |
Pointer chasing via triangular discrimination
Combinatorics, Probability and Computing | 2021-06-15 | Paper |
| A lower bound for essential covers of the cube | 2021-05-28 | Paper |
Concentration for limited independence via inequalities for the elementary symmetric polynomials
Theory of Computing | 2021-04-01 | Paper |
| Slicing the hypercube is not easy | 2021-02-10 | Paper |
On weak \(\epsilon\)-nets and the Radon number
Discrete & Computational Geometry | 2021-01-29 | Paper |
| An Elementary Exposition of Pisier's Inequality | 2020-09-22 | Paper |
| Communication Complexity | 2020-02-04 | Paper |
Separating monotone VP and VNP
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
On the covariance-Hessian relation in evolution strategies
Theoretical Computer Science | 2019-11-22 | Paper |
Approximate nonnegative rank is equivalent to the smooth rectangle bound
Computational Complexity | 2019-06-20 | Paper |
| Learners that use little information | 2019-02-06 | Paper |
Learners that use little information
(available as arXiv preprint) | 2019-02-06 | Paper |
| Anti-concentration in most directions | 2018-11-15 | Paper |
Sample Compression Schemes for VC Classes
Journal of the ACM | 2018-08-02 | Paper |
Distributed construction of purely additive spanners
Distributed Computing | 2018-06-01 | Paper |
Sign rank versus Vapnik-Chervonenkis dimension
Sbornik: Mathematics | 2018-04-06 | Paper |
Teaching and Compressing for Low VC-Dimension
A Journey Through Discrete Mathematics | 2018-02-26 | Paper |
| Simplified lower bounds on the multiparty communication complexity of disjointness | 2018-01-24 | Paper |
| scientific article; zbMATH DE number 6820278 (Why is no real title available?) | 2017-12-19 | Paper |
An elementary exposition of topological overlap in the plane
Discrete & Computational Geometry | 2017-10-10 | Paper |
| Internal Compression of Protocols to Entropy | 2017-08-31 | Paper |
On the statistical learning ability of evolution strategies
Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms | 2017-06-13 | Paper |
Direct sum fails for zero error average communication
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Fooling pairs in randomized communication complexity
Structural Information and Communication Complexity | 2016-12-01 | Paper |
Direct sum fails for zero-error average communication
Algorithmica | 2016-11-29 | Paper |
| On statistical learning via the lens of compression | 2016-10-11 | Paper |
Geometric stability via information theory
Discrete Analysis | 2016-10-10 | Paper |
Restriction access
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
Population recovery and partial identification
Machine Learning | 2016-03-09 | Paper |
A note on average-case sorting
Order | 2016-03-02 | Paper |
Sign rank versus VC dimension
(available as arXiv preprint) | 2015-03-26 | Paper |
Containing internal diffusion limited aggregation
Electronic Communications in Probability | 2014-09-22 | Paper |
Grounded Lipschitz functions on trees are typically flat
Electronic Communications in Probability | 2014-09-22 | Paper |
Pseudorandom generators for regular branching programs
SIAM Journal on Computing | 2014-09-18 | Paper |
Non-commutative circuits and the sum-of-squares problem
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Fractional Sylvester–Gallai theorems
Proceedings of the National Academy of Sciences | 2014-07-25 | Paper |
Approximate nonnegative rank is equivalent to the smooth rectangle bound
Automata, Languages, and Programming | 2014-07-01 | Paper |
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Separating multilinear branching programs and formulas
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Monotone expansion
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
scientific article; zbMATH DE number 6292624 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
Direct product via round-preserving compression
Automata, Languages, and Programming | 2013-08-06 | Paper |
Lipschitz functions on expanders are typically flat
Combinatorics, Probability and Computing | 2013-07-26 | Paper |
Expansion in SL₂( R) and monotone expanders
Geometric and Functional Analysis. GAFA | 2013-07-04 | Paper |
An asymptotic bound on the composition number of integer sums of squares formulas
Canadian Mathematical Bulletin | 2013-03-07 | Paper |
Affine extractors over prime fields
Combinatorica | 2011-12-20 | Paper |
Homogeneous formulas and symmetric polynomials
Computational Complexity | 2011-11-30 | Paper |
Loop-erased random walk and Poisson kernel on planar graphs
The Annals of Probability | 2011-10-10 | Paper |
The maximal probability that k-wise independent bits are all 1
Random Structures & Algorithms | 2011-08-09 | Paper |
Non-commutative circuits and the sum-of-squares problem
Journal of the American Mathematical Society | 2011-06-27 | Paper |
Arithmetic complexity in ring extensions
Theory of Computing | 2011-05-24 | Paper |
Players' effects under limited independence
Mathematics of Operations Research | 2011-04-27 | Paper |
Entropy of random walk range
Annales de l'Institut Henri Poincaré. Probabilités et Statistiques | 2011-03-10 | Paper |
Entropy of random walk range
Annales de l'Institut Henri Poincaré. Probabilités et Statistiques | 2011-03-10 | Paper |
Lower bounds and separations for constant depth multilinear circuits
Computational Complexity | 2011-02-18 | Paper |
Arithmetic circuits: a survey of recent results and open questions
Foundations and Trends® in Theoretical Computer Science | 2011-01-24 | Paper |
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Hardness-randomness tradeoffs for bounded depth arithmetic circuits
SIAM Journal on Computing | 2010-09-06 | Paper |
Monotone separations for constant degree polynomials
Information Processing Letters | 2010-09-02 | Paper |
\(t\)-wise independence with local dependencies
Information Processing Letters | 2010-04-19 | Paper |
Balancing syntactically multilinear arithmetic circuits
Computational Complexity | 2010-03-15 | Paper |
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
SIAM Journal on Computing | 2009-08-20 | Paper |
| scientific article; zbMATH DE number 5485588 (Why is no real title available?) | 2009-01-05 | Paper |
| The Player's Effect | 2008-05-04 | Paper |
Random graph-homomorphisms and logarithmic degree
Electronic Journal of Probability | 2007-11-23 | Paper |
Random graph-homomorphisms and logarithmic degree
Electronic Journal of Probability | 2007-11-23 | Paper |
