Department of Computer Science, University of Copenhagen

Department of Mathematics, Technion-IIT

email: first name dot last name at gmail dot com

- 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

- Daniel Carmon, Ph.D.
- Shachar Shabelman, M.Sc.

- Shay Moran, Ph.D., co-advised with Amir Shpilka
- Balthazar Bauer, intern
- Jonathan Shafer, M.Sc., co-advised with Amir Shpilka
- Ido Nachum, Ph.D.
- Krishna Manoorkar, M.Sc.
- Daniel Avraham, M.Sc.

- Advanced topics in machine learning (notes)
- Analytic method (notes)
- Basic notions in mathematics (notes)
- Calculus
- Calculus 2 (notes)
- Combinatorial algorithms
- Combinatorics (notes)
- Communication complexity
- Computability and computational complexity (notes: 1, 2 and 3)
- Information theory (notes)
- Intro to probability (notes)
- Math for life sciences
- Seminar on learning theory (notes)
- Set theory

- Talks on YouTube
- Building monotone expanders, Neo-classical methods in discrete analysis, Simons Institute, Berkeley
- Lower bounds for multilinear circuits and Non-commutative lower bounds, Recent progress in arithmetic complexity,TIFR, Bombai
- A needle in a haystack, in Hebrew, Technion, Haifa
- Rounding group actions: examples, Computational complexity meeting, BIRS, Banff
- Lower bounds on the multiparty communication complexity of disjointness, Communication complexity and application meeting, BIRS, Banff
- Symmetric computations, Workshop on Algebraic Complexity Theory, Tel Aviv
- Geometric stability using information theory, Nexus of Information and Computation Theories, IHP, Paris
- Spectral gaps and geometric representations, Expanders and Extractors Workshop, Simons Institute, Berkeley
- Blocky ranks, BIRS, Banff