Communication complexity book
-
- 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. ), 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. arXiv 2021.
- 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. ECCC 2022.
- Random walks on regular trees can not be slowed down. Joint with Omer Angel, Jacob Richey and Yinon Spinka. arXiv 2023.
- Dual systolic graphs. Joint with Daniel Carmon. arXiv 2023.
- Replicability and stability in learning. Joint with Zachary Chase and Shay Moran. arXiv 2023.
- A unified characterization of private learnability via graph theory. Joint with Noga Alon, Shay Moran and Hilla Schefler. arXiv 2023.