# Amir Yehudayoff

According to our database

Collaborative distances:

^{1}, Amir Yehudayoff authored at least 61 papers between 2007 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Separating monotone VP and VNP.

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

On the Communication Complexity of Key-Agreement Protocols.

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

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

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

On Weak epsilon-Nets and the Radon Number.

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

On Communication Complexity of Classification Problems.

Proceedings of the Conference on Learning Theory, 2019

Average-Case Information Complexity of Learning.

Proceedings of the Algorithmic Learning Theory, 2019

2018

Anti-concentration in most directions.

Electronic Colloquium on Computational Complexity (ECCC), 2018

A Direct Sum Result for the Information Complexity of Learning.

Proceedings of the Conference On Learning Theory, 2018

Learners that Use Little Information.

Proceedings of the Algorithmic Learning Theory, 2018

2017

An Elementary Exposition of Topological Overlap in the Plane.

Discrete & Computational Geometry, 2017

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.

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.

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

2016

A Note on Average-Case Sorting.

Order, 2016

Pointer chasing via triangular discrimination.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Distributed Construction of Purely Additive Spanners.

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

Fooling Pairs in Randomized Communication Complexity.

Proceedings of the Structural Information and Communication Complexity, 2016

Supervised learning through the lens of compression.

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.

Proceedings of the 2016 Information Theory and Applications Workshop, 2016

On Isoperimetric Profiles and Computational Complexity.

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

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

Proceedings of the Genetic and Evolutionary Computation Conference, 2016

Sign rank versus VC dimension.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Proper PAC learning is compressing.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Teaching and compressing for low VC-dimension.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Compressing and Teaching for Low VC-Dimension.

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

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.

Proceedings of the 30th Conference on Computational Complexity, 2015

Internal Compression of Protocols to Entropy.

Proceedings of the Approximation, 2015

2014

Inequalities and tail bounds for elementary symmetric polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Sign rank, VC dimension and spectral gaps.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Direct sum fails for zero error average communication.

Proceedings of the Innovations in Theoretical Computer Science, 2014

Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.

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

2013

Pseudorandomness for Width-2 Branching Programs.

Theory of Computing, 2013

A note on average-case sorting.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Lipschitz Functions on Expanders are Typically Flat.

Combinatorics, Probability & Computing, 2013

Direct Product via Round-Preserving Compression.

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

Direct Products in Communication Complexity.

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

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

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Proving expansion in three steps.

SIGACT News, 2012

Linear cover time for trees is exponentially unlikely.

Chicago J. Theor. Comput. Sci., 2012

Separating multilinear branching programs and formulas.

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

Monotone expansion.

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

Restriction access.

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Population Recovery and Partial Identification.

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

2011

Arithmetic Complexity in Ring Extensions.

Theory of Computing, 2011

The maximal probability that

*k*-wise independent bits are all 1.
Random Struct. Algorithms, 2011

Affine extractors over prime fields.

Combinatorica, 2011

Homogeneous Formulas and Symmetric Polynomials.

Computational Complexity, 2011

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

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

2010

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

Foundations and Trends in Theoretical Computer Science, 2010

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

Electronic Colloquium on Computational Complexity (ECCC), 2010

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

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

Pseudorandom Generators for Regular Branching Programs.

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

Relationless Completeness and Separations.

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

2009

Players' Effects Under Limited Independence.

Math. Oper. Res., 2009

Monotone separations for constant degree polynomials.

Inf. Process. Lett., 2009

Pseudorandomness for Width 2 Branching Programs.

Electronic Colloquium on Computational Complexity (ECCC), 2009

2008

t-Wise independence with local dependencies.

Inf. Process. Lett., 2008

Balancing Syntactically Multilinear Arithmetic Circuits.

Computational Complexity, 2008

Hardness-randomness tradeoffs for bounded depth arithmetic circuits.

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

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

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

Lower Bounds and Separations for Constant Depth Multilinear Circuits.

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

2007

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

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007