Amir Yehudayoff's homepage

A book on communication complexity and its applications

A lower bound for the size of syntactically multilinear arithmetic circuits. Joint with Ran Raz and Amir Shpilka. SIAM J. Comput. 38 (4), pages 1624-1647, 2008
Random graph-homomorphisms and logarithmic degree. Joint with Itai Benjamini and Ariel Yadin. Electronic Journal of Probability 12, pages 926-950, 2007
Balancing syntactically multilinear arithmetic circuits. Joint with Ran Raz. Computational Complexity 17 (4), pages 515-535, 2008
t-wise independence with local dependencies. Joint with Ronen Gradwohl. Information Processing Letters 106, pages 208-212, 2008
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. Joint with Ran Raz. J. Comput. Syst. Sci. 77(1), pages 167-190, 2011
Hardness-randomness tradeoffs for bounded depth arithmetic circuits. Joint with Zeev Dvir and Amir Shpilka. SIAM J. Comput. 39 (4), pages 1279-1293, 2009
The maximal probability that k-wise independent bits are all 1. Joint with Ron Peled and Ariel Yadin. Random Structures and Algorithms 38 (4), pages 502-525, 2009
Lower bounds and separations for constant depth mutilinear circuits. Joint with Ran Raz. CCC, pages 128-139, 2008
The player's effect. Joint with Ronen Gradwohl, Omer Reingold and Ariel Yadin. Mathematics of Operations Research 34, pages 971-980, 2009
Pseudorandomness for width 2 branching programs. Joint with Andrej Bogdanov, Zeev Dvir and Elad Verbin. Theory of Computing 9 (7), pages 283-293, 2013
Loop-erased random walk and poisson kernel on planar graphs. Joint with Ariel Yadin. Annals of Probability 39 (4), pages 1243--1285, 2011
Entropy of random walk range. Joint with Itai Benjamini, Gady Kozma and Ariel Yadin. Annales de l`Institut Henri Poincare 6 (4), pages 1080-1092, 2010
Homogeneous formulas and symmetric polynomials. Joint with Pavel Hrubes. Computational Complexity 20 (3), pages 559-578, 2011
Affine extractors over prime fields. Combinatorica 31 (2), pages 245-256, 2011
Monotone separations for constant degree polynomials. Joint with Pavel Hrubes. Information Processing Letters 110 (1), pages 1-3, 2009
Arithmetic complexity in ring extensions. Joint with Pavel Hrubes. Theory of Computing 7 (8), pages 119-129, 2011
Non-commutative circuits and the sum-of-squares problem. Joint with Pavel Hrubes and Avi Wigderson. JAMS 24, pages 871-898, 2011
Relationless completeness and separations. Joint with Pavel Hrubes and Avi Wigderson. CCC, pages 280-290, 2010
Pseudorandom generators for regular branching programs. Joint with Mark Braverman, Anup Rao and Ran Raz. SIAM J. Comput. 43(3), pages 973-986, 2014
An asymptotic bound on integer sum of squares. Joint with Pavel Hrubes and Avi Wigderson. Canadian Mathematical Bulletin 56, pages 70-79, 2013
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. Joint with Boaz Barak, Zeev Dvir and Avi Wigderson. STOC, pages 519-528, 2011
Fractional Sylvester-Gallai theorems. Joint with Boaz Barak, Zeev Dvir and Avi Wigderson. PNAS 110 (48), pages 19213-19219, 2012
Arithmetic circuits: a survey of recent results and open questions. Joint with Amir Shpilka. Foundations and Trends in Theoretical Computer Science 2010
Expansion in $SL_2(R)$ and monotone expansion. Joint with Jean Bourgain. GAFA 23 (1), pages 1-41, 2013
Separating multilinear branching programs and formulas. Joint with Zeev Dvir, Guillaume Malod and Sylvain Perifel. STOC, pages 615-624, 2012
Containing internal diffusion limited aggregation. Joint with Hugo Duminil-Copin, Cyrille Lucas and Ariel Yadin. ECP 18, article 50, 2013
Restriction access. Joint with Zeev Dvir, Anup Rao and Avi Wigderson. ITCS, pages 19-33, 2012
Lipschitz functions on expanders are typically flat. Joint with Ron Peled and Wojciech Samotij. Combinatorics, Probability and Computing 22 (4), pages 566-591, 2013
Formulas are exponentially stronger than monotone circuits in non-commutative setting. Joint with Pavel Hrubes. CCC, pages 10-14, 2013
Linear cover time for trees is exponentially unlikely. Chicago Journal of Theoretical Computer Science 2012 (3), 2012
Population recovery and partial identification. Joint with Avi Wigderson. Machine Learning, 2015, 10.1007/s10994-015-5489-9
Direct products in communication complexity. Joint with Mark Braverman, Anup Rao and Omri Weinstein. FOCS, pages 746-755, 2013
Proving expansion in three steps. SIGACT News 43 (3), pages 67-84, 2012
Direct product via round-preserving compression. Joint with Mark Braverman, Anup Rao and Omri Weinstein. ICALP, pages 232-243, 2013
Grounded Lipshitz functions on trees are typically flat. Joint with Ron Peled and Wojciech Samotij. ECP 18 (55), pages 1-9, 2013
Direct sum fails for zero error average communication. Joint with Gillat Kol, Shay Moran and Amir Shpilka. Algorithmica 76 (3), pages 782-795, 2016
A note on average-case sorting. Joint with Shay Moran. Order 33(1), pages 23-28, 2016
Concentration for limited independence via inequalities for the elementary symmetric polynomials. Joint with Parikshit Gopalan. Theory of Computing 16(17), pages 1-29, 2020
Fooling pairs in randomized communication complexity. Joint with Shay Moran and Makrand Sinha. SIROCCO, pages 49-59, 2016
Approximate nonnegative rank is equivalent to the smooth rectangle bound. Joint with Gillat Kol, Shay Moran and Amir Shpilka. Computational Complexity 28(1), pages 1-25, 2019
Simplified lower bounds on the multiparty communication complexity of disjointness. Joint with Anup Rao. CCC, pages 88-101, 2015
Internal compression of protocols to entropy. Joint with Balthazar Bauer and Shay Moran. RANDOM 2015
Sign rank versus VC dimension. Joint with Noga Alon and Shay Moran. Sbornik: Mathematics 208, 12, 2017
Teaching and compressing for low VC-dimension. Joint with Shay Moran, Amir Shpilka and Avi Wigderson. FOCS 2015
Sample compression schemes for VC classes. Joint with Shay Moran. JACM 63 (3), pages 1-21, 2016
An elementary exposition of topological overlap in the plane. Discrete & Computational Geometry, DOI 10.1007/s00454-017-9910-y
Geometric stability via information theory. Joint with David Ellis, Ehud Friedgut and Guy Kindler. Discrete Analysis 2016:10, DOI: 10.19086/da.784
On isoperimetric profiles and computational complexity. Joint with Pavel Hrubes. ICALP, pages 1-12, 2016
On the theoretical capacity of evolution strategies to statistically learn the landscape Hessian. Joint with Ofer Shir and Jonathan Roslund. GECCO 2016
Distributed constructions of purely additive spanners. Joint with Keren Censor-Hillel, Telikepalli Kavitha and Ami Paz. Distributed Computing 31(3), pages 223-240, 2018
Pointer chasing via triangular discrimination. Combinatorics, Probability and Computing
On statistical learning via the lens of compression. Joint with Shay Moran and Ofir David. NIPS 2016
On weak ε-nets and the Radon number. Joint with Shay Moran. SoCG, pages 1:14, 2019
Submultiplicative Glivenko-Cantelli and uniform convergence of revenues. Joint with Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour and Shay Moran. NIPS 2017
Learners that leak little information. Joint with Raef Bassily, Shay Moran, Ido Nachum and Jonathan Shafer. ALT, pages 25-55, 2018
On communication complexity of classification problems. Joint with Daniel Kane, Roi Livni and Shay Moran. COLT, pages 1903-1943, 2019
Learnability can be undecidable. Joint with Shai Ben-David, Pavel Hrubes, Shay Moran and Amir Shpilka. Nature Machine Intelligence 1, pages 44-48, 2019 (Invited to STOC 21)
On the communication complexity of key-agreement protocols. Joint with Iftach Haitner, Noam Mazor, Rotem Oshman and Omer Reingold. ITCS, pages 1-16, 2019
A direct sum result for the information complexity of learning. Joint with Ido Nachum and Jonathan Shafer. COLT, pages 1547-1568, 2018
On the perceptron's compression. Joint with Shay Moran, Ido Nachum and Itai Panasoff. CiE 2020
An isoperimetric inequality for Hamming balls and local expansion in hypercubes. Joint with Zilin Jiang. Electronic Journal of Combinatorics 2022
Separating monotone VP and VNP. STOC, pages 425-429, 2019
The communication complexity of exact gap-hamming. Joint with Anup Rao. ECCC 20
Anti-concentration and the exact gap-Hamming problem. Joint with Anup Rao. SIAM Journal on Discrete Mathematics 2022
Lower bounds on balancing sets and depth-2 threshold circuits. Joint with Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao. ICALP, pages 1-14, 2019
Average-case information complexity of learning. Joint with Ido Nachum. ALT, pages 633-646, 2019
On division versus saturation in pseudo-boolean solving. Joint with Stephan Gocht and Jakob Nordström. IJCAI, pages 1711-1718, 2019
On symmetry and initialization of neural network. Joint with Ido Nachum. Latin 2020
Interactive proofs for verifying machine learning. Joint with Shafi Goldwasser, Guy Rothblum and Jonathan Shafer. ITCS 2020
Sharp isoperimetric inequalities for affine quermassintegrals. Joint with Emanuel Milman. JAMS 2022
An elementary exposition of Pisier's inequality. Joint with Siddharth Iyer, Anup Rao, Victor Reis and Thomas Rothvoss. arXiv 2022
A theory of universal learning. Joint with Olivier Bousquet, Steve Hanneke, Shay Moran and Ramon van Handel. STOC 2021
Shadows of Newton polytopes. Joint with Pavel Hrubes. CCC 2021
Slicing the hypercube is not easy. Joint with Gal Yehuda. arXiv 2021
A lower bound for essential covers of the cube. Joint with Gal Yehuda. Combinatorica 2024
Tight bounds on the Fourier growth of bounded functions on the hypercube. Joint with Siddharth Iyer, Anup Rao, Victor Reis and Thomas Rothvoss. ECCC 2021
Explicit exponential lower bounds for exact hyperplane covers. Joint with Benjamin Diamond. Discrete Mathematics 2022
A characterization of multiclass learnability. Joint with Nataly Brukhim, Daniel Carmon, Irit Dinur and Shay Moran. FOCS 2022
On blocky ranks of matrices. Joint with Daniel Avraham. Computational Complexity 2024
Random walks on regular trees can not be slowed down. Joint with Omer Angel, Jacob Richey and Yinon Spinka. Electronic Journal of Probability 2024
Dual systolic graphs. Joint with Daniel Carmon. arXiv 2023
Replicability and stability in learning. Joint with Zachary Chase and Shay Moran. FOCS 2023
A unified characterization of private learnability via graph theory. Joint with Noga Alon, Shay Moran and Hilla Schefler. arXiv 2023
The discrepancy of greater-than. Joint with Srikanth Srinivasan. arXiv 2023
The sample complexity of ERMs in stochastic convex optimization. Joint with Daniel Carmon and Roi Livni. AISTAT 2024
Local Borsuk-Ulam, stability, and replicability. Joint with Zachary Chase, Bogdan Chornomaz and Shay Moran. STOC 2024

AMIR YEHUDAYOFF

PUBLICATIONS

STUDENTS

current

former

TEACHING

TALKS