Amir Yehudayoff

Discret. Math., 2026

2025

Approximation Depth of Convex Polytopes.

[BibT_eX]

[DOI]

Egor Bakaev

Florestan Brunck

CoRR, July, 2025

Better Neural Network Expressivity: Subdividing the Simplex.

[BibT_eX]

[DOI]

CoRR, May, 2025

On the Depth of Monotone ReLU Neural Networks and ICNNs.

[BibT_eX]

[DOI]

CoRR, May, 2025

On the Space Complexity of Online Convolution.

[BibT_eX]

[DOI]

Joel Daniel Andersson

CoRR, May, 2025

The Algebraic Cost of a Boolean Sum.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Open Problem: Data Selection for Regression Tasks.

[BibT_eX]

[DOI]

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

Data Selection for ERMs.

[BibT_eX]

[DOI]

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

2024

A Lower Bound for Essential Covers of the Cube.

[BibT_eX]

[DOI]

Gal Yehuda

Comb., August, 2024

On Blocky Ranks Of Matrices.

[BibT_eX]

[DOI]

Daniel Avraham

Comput. Complex., June, 2024

Local Borsuk-Ulam, Stability, and Replicability.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Unified Characterization of Private Learnability via Graph Theory.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Dual VC Dimension Obstructs Sample Compression by Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

The sample complexity of ERMs in stochastic convex optimization.

[BibT_eX]

[DOI]

Daniel Carmon

Roi Livni

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

2023

The discrepancy of greater-than.

[BibT_eX]

[DOI]

Srikanth Srinivasan

CoRR, 2023

Replicability and stability in learning.

[BibT_eX]

[DOI]

Zachary Chase

CoRR, 2023

Stability and Replicability in Learning.

[BibT_eX]

[DOI]

Zachary Chase

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Anticoncentration and the Exact Gap-Hamming Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

An Isoperimetric Inequality for Hamming Balls and Local Expansion in Hypercubes.

[BibT_eX]

[DOI]

Zilin Jiang

Electron. J. Comb., 2022

A Characterization of Multiclass Learnability.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Tight bounds on the Fourier growth of bounded functions on the hypercube.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Explicit Exponential Lower Bounds for Exact Hyperplane Covers.

[BibT_eX]

[DOI]

Benjamin E. Diamond

Electron. Colloquium Comput. Complex., 2021

Regularization by Misclassification in ReLU Neural Networks.

[BibT_eX]

[DOI]

Elisabetta Cornacchia

Jan Hazla

CoRR, 2021

Slicing the hypercube is not easy.

[BibT_eX]

[DOI]

Gal Yehuda

CoRR, 2021

A theory of universal learning.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Learnability can be independent of set theory (invited paper).

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Interactive Proofs for Verifying Machine Learning.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Shadows of Newton Polytopes.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials.

[BibT_eX]

[DOI]

Parikshit Gopalan

Theory Comput., 2020

On the covariance-Hessian relation in evolution strategies.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

The Communication Complexity of the Exact Gap-Hamming Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

On Weak ε-Nets and the Radon Number.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

On Symmetry and Initialization for Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

On the Perceptron's Compression.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Horizon of Computability, 2020

2019

Author Correction: Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Separating monotone VP and VNP.

[BibT_eX]

[DOI]

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

On the Communication Complexity of Key-Agreement Protocols.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

On Division Versus Saturation in Pseudo-Boolean Solving.

[BibT_eX]

[DOI]

Stephan Gocht

Jakob Nordström

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.

[BibT_eX]

[DOI]

Sivaramakrishnan Natarajan Ramamoorthy

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

On Weak epsilon-Nets and the Radon Number.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

On Communication Complexity of Classification Problems.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Average-Case Information Complexity of Learning.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2019

2018

Anti-concentration in most directions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

A Direct Sum Result for the Information Complexity of Learning.

[BibT_eX]

[DOI]

Jonathan Shafer

Proceedings of the Conference On Learning Theory, 2018

Learners that Use Little Information.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2018

2017

An Elementary Exposition of Topological Overlap in the Plane.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2017

A learning problem that is independent of the set theory ZFC axioms.

[BibT_eX]

[DOI]

CoRR, 2017

Learners that Leak Little Information.

[BibT_eX]

[DOI]

CoRR, 2017

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.

[BibT_eX]

[DOI]

Noga Alon

Moshe Babaioff

Yannai A. Gonczarowski

Yishay Mansour

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

On the Statistical Learning Ability of Evolution Strategies.

[BibT_eX]

[DOI]

Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2017

2016

Pointer chasing via triangular discrimination.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

On the Theoretical Capacity of Evolution Strategies to Statistically Learn the Landscape Hessian.

[BibT_eX]

[DOI]

Jonathan Roslund

CoRR, 2016

On statistical learning via the lens of compression.

[BibT_eX]

[DOI]

Ofir David

CoRR, 2016

Distributed Construction of Purely Additive Spanners.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Fooling Pairs in Randomized Communication Complexity.

[BibT_eX]

[DOI]

Makrand Sinha

Proceedings of the Structural Information and Communication Complexity, 2016

Supervised learning through the lens of compression.

[BibT_eX]

[DOI]

Ofir David

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Sample compression schemes for VC classes.

[BibT_eX]

[DOI]

Proceedings of the 2016 Information Theory and Applications Workshop, 2016

On Isoperimetric Profiles and Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

On the Capacity of Evolution Strategies to Statistically Learn the Landscape.

[BibT_eX]

[DOI]

Jonathan Roslund

Proceedings of the Genetic and Evolutionary Computation Conference, 2016

Sign rank versus VC dimension.

[BibT_eX]

[DOI]

Noga Alon

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Proper PAC learning is compressing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Teaching and compressing for low VC-dimension.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Geometric stability via information theory.

[BibT_eX]

[DOI]

CoRR, 2015

Compressing and Teaching for Low VC-Dimension.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

Internal Compression of Protocols to Entropy.

[BibT_eX]

[DOI]

Balthazar Bauer

Proceedings of the Approximation, 2015

2014

Inequalities and tail bounds for elementary symmetric polynomials.

[BibT_eX]

[DOI]

Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2014

Sign rank, VC dimension and spectral gaps.

[BibT_eX]

[DOI]

Noga Alon

Electron. Colloquium Comput. Complex., 2014

Inequalities and tail bounds for elementary symmetric polynomial.

[BibT_eX]

[DOI]

Parikshit Gopalan

CoRR, 2014

Direct sum fails for zero error average communication.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

A note on average-case sorting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Lipschitz Functions on Expanders are Typically Flat.

[BibT_eX]

[DOI]

Ron Peled

Wojciech Samotij

Comb. Probab. Comput., 2013

Direct Product via Round-Preserving Compression.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Proving expansion in three steps.

[BibT_eX]

[DOI]

SIGACT News, 2012

Linear cover time for trees is exponentially unlikely.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2012

Separating multilinear branching programs and formulas.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Monotone expansion.

[BibT_eX]

[DOI]

Jean Bourgain

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Restriction access.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Population Recovery and Partial Identification.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Arithmetic Complexity in Ring Extensions.

[BibT_eX]

[DOI]

Theory Comput., 2011

The maximal probability that <i>k</i>-wise independent bits are all 1.

[BibT_eX]

[DOI]

Ron Peled

Ariel Yadin

Random Struct. Algorithms, 2011

Affine extractors over prime fields.

[BibT_eX]

[DOI]

Comb., 2011

Homogeneous Formulas and Symmetric Polynomials.

[BibT_eX]

[DOI]

Comput. Complex., 2011

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Arithmetic Circuits: A survey of recent results and open questions.

[BibT_eX]

[DOI]

Amir Shpilka

Found. Trends Theor. Comput. Sci., 2010

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Non-commutative circuits and the sum-of-squares problem.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Pseudorandom Generators for Regular Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Relationless Completeness and Separations.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Players' Effects Under Limited Independence.

[BibT_eX]

[DOI]

Math. Oper. Res., 2009

Monotone separations for constant degree polynomials.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Pseudorandomness for Width 2 Branching Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

t-Wise independence with local dependencies.

[BibT_eX]

[DOI]

Ronen Gradwohl

Inf. Process. Lett., 2008

Balancing Syntactically Multilinear Arithmetic Circuits.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Hardness-randomness tradeoffs for bounded depth arithmetic circuits.

[BibT_eX]

[DOI]

Zeev Dvir

Amir Shpilka

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Lower Bounds and Separations for Constant Depth Multilinear Circuits.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.

[BibT_eX]

[DOI]

Amir Shpilka