# Guy Moshkovitz

# About Me

I am an Assistant Professor in the Department of Mathematics at the City University of New York (Baruch College). Previously, I was a postdoctoral researcher at the Institute for Advanced Study in Princeton and DIMACS. In 2018 I was a postdoctoral researcher at Harvard University in the Special Year on Combinatorics and Complexity.

I completed my Ph.D. studies at the School of Mathematics at Tel Aviv University, advised by Prof. Asaf Shapira, and my M.Sc. studies at the School of Computer Science under the supervision of Prof. Oded Regev.

I have a broad interest in: Extremal Combinatorics, Graph/Hypergraph Theory, Algebraic Geometry, probabilistic and algebraic methods in Combinatorics, and their applications to Theoretical Computer Science.

Email: guymoshkov at gmail.com

# Research Highlights

**Algebraic Geometry:**

A proof of the simplest case of the polynomial Gowers inverse conjecture.

A new notion of tensor rank, providing a bridge to the field of algebraic geometry, with applications to matrix multiplication

**Extremal Combinatorics:**

A proof that the hypergraph regularity lemma cannot have a primitive recursive bound, settling a long-standing open question & confirming prediction of Tao [JCTA '06]

A variant of the celebrated Sauer-Shelah Lemma for a wide range of parameters (and a new variant of the famous Kruskal-Katona Theorem)

A near-resolution of the Erdos-Szekeres Ramsey problems

A short and simple proof of the celebrated lower bound for the graph regularity lemma due to Gowers [GAFA '97]

**Theoretical Computer Science:**

Lower bounds for multiple results on graph decompositions, nearly matching bounds by Arora-Barak-Steurer [J. ACM '15] and many others

A new, combinatorial approach to arithmetic circuit lower bounds, via the polynomial method

# Papers

An Optimal Inverse Theorem (with A. Cohen).

Structure vs. Randomness for Bilinear Maps (with A. Cohen), Proc. of the 53rd ACM Symposium on Theory of Computing (

**STOC 2021**), to appear.Geometric Rank of Tensors and Subrank of Matrix Multiplication (with S. Kopparty and J. Zuiddam), Accepted to

**Discrete Analysis**;

previously appeared in the Proc. of the 35th Computational Complexity Conference (**CCC 2020**), 1-21.Limitations on Regularity Lemmas for Clustering Graphs (with N. Alon),

**Advances in Applied Mathematics**124 (2021).Traces of Hypergraphs (with N. Alon and N. Solomon),

**Journal of the London Mathematical Society**100 (2019), 498--517.A Tight Bound for Hypergraph Regularity (with A. Shapira),

**Geometric and Functional Analysis**29 (2019), 1531--1578.

For a simplified version of this result for 3-uniform hypergraphs, see: A Tight Bound for Hypergraph Regularity I

A Sparse Regular Approximation Lemma (with A. Shapira),

**Transactions of the American Mathematical Society**371 (2019), 6779--6814.Decomposing a Graph Into Expanding Subgraphs (with A. Shapira),

**Random Structures and Algorithms**52 (2018), 158-178.Constructing Near Spanning Trees with Few Local Inspections (with R. Levi, D. Ron, R. Rubinfeld and A. Shapira),

**Random Structures and Algorithms**50 (2017), 183-200.An Improved Lower Bound for Arithmetic Regularity (with K. Hosseini, S. Lovett and A. Shapira),

**Mathematical Proceedings of the Cambridge Philosophical Society**161 (2016), 193-197.A Short Proof of Gowers' Lower Bound for the Regularity Lemma (with A. Shapira),

**Combinatorica**, 36 (2016), 187-194.Exact Bounds for Some Hypergraph Saturation Problems (with A. Shapira),

**Journal of Combinatorial Theory Series B**111 (2015), 242-248.

A full version of this paper: (arXiv)

Ramsey Theory, Integer Partitions and a New Proof of the Erdos-Szekeres Theorem (with A. Shapira),

**Advances in Mathematics**262 (2014), 1107-1129.Complexity Lower Bounds through Balanced Graph Properties, Proc. of the 27th Annual IEEE Conference on Computational Complexity (

**CCC 2012**), 159-169.

# Teaching

Analytic Geometry (2021)

Calculus III (2020)

Introduction to Discrete Structures I (2019)

Introduction to Discrete Mathematics (2016)

Calculus B2 (2014, 2015, 2016)

Linear Algebra A1 (2013, 2014, 2015)

Differential and Integral Calculus (2012, 2013)

Linear Algebra (2012)