Amir Yehudayoff

Comput. Complex., June, 2024

2023

The Sample Complexity Of ERMs In Stochastic Convex Optimization.

[BibT_eX]

[DOI]

Daniel Carmon

Roi Livni

CoRR, 2023

Local Borsuk-Ulam, Stability, and Replicability.

[BibT_eX]

[DOI]

CoRR, 2023

The discrepancy of greater-than.

[BibT_eX]

[DOI]

Srikanth Srinivasan

CoRR, 2023

A Unified Characterization of Private Learnability via Graph Theory.

[BibT_eX]

[DOI]

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

A Characterization of Multiclass Learnability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Zilin Jiang

Electron. J. Comb., 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

A lower bound for essential covers of the cube.

[BibT_eX]

[DOI]

Gal Yehuda

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

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

Shadows of Newton polytopes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Interactive Proofs for Verifying Machine Learning.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

On Weak ε-Nets and the Radon Number.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2020

Pointer chasing via triangular discrimination.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 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

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

[BibT_eX]

[DOI]

Sivaramakrishnan Natarajan Ramamoorthy

Electron. Colloquium Comput. Complex., 2019

Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.

[BibT_eX]

[DOI]

Comput. Complex., 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

On Weak epsilon-Nets and the Radon Number.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 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

Separating Monotone VP and VNP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

On the Communication Complexity of Key-Agreement Protocols.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Distributed construction of purely additive spanners.

[BibT_eX]

[DOI]

Distributed Comput., 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

On Communication Complexity of Classification Problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

A Note on Average-Case Sorting.

[BibT_eX]

[DOI]

Order, 2016

Population recovery and partial identification.

[BibT_eX]

[DOI]

Avi Wigderson

Mach. Learn., 2016

Sample Compression Schemes for VC Classes.

[BibT_eX]

[DOI]

J. ACM, 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

Direct Sum Fails for Zero-Error Average Communication.

[BibT_eX]

[DOI]

Algorithmica, 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

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

On isoperimetric profiles and computational complexity.

[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

2014

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Fooling Pairs in Randomized Communication Complexity.

[BibT_eX]

[DOI]

Makrand Sinha

Electron. Colloquium Comput. Complex., 2014

Inequalities and tail bounds for elementary symmetric polynomials.

[BibT_eX]

[DOI]

Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2014

Internal compression of protocols to entropy.

[BibT_eX]

[DOI]

Balthazar Bauer

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

2013

Pseudorandomness for Width-2 Branching Programs.

[BibT_eX]

[DOI]

Theory Comput., 2013

Direct product via round-preserving compression.

[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

2012

Proving expansion in three steps.

[BibT_eX]

[DOI]

SIGACT News, 2012

Formulas are exponentially stronger than monotone circuits in non-commutative setting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Linear cover time for trees is exponentially unlikely.

[BibT_eX]

[DOI]

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

Monotone expansion.

[BibT_eX]

[DOI]

Jean Bourgain

Proceedings of the 44th Symposium on Theory of Computing Conference, 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

Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Restriction Access.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Separating multilinear branching programs and formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Relationless completeness and separations.

[BibT_eX]

[DOI]

Avi Wigderson

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Avi Wigderson

Electron. Colloquium Comput. Complex., 2010

Pseudorandom Generators for Regular Branching Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Lower Bounds and Separations for Constant Depth Multilinear Circuits.

[BibT_eX]

[DOI]

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

2007

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.

[BibT_eX]

[DOI]

Zeev Dvir

Amir Shpilka

Electron. Colloquium Comput. Complex., 2007

2006

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

[BibT_eX]

[DOI]

Amir Shpilka