Guy Moshkovitz
About Me
For details on a summer research position for graduate students, see here.
I am an Assistant Professor at the City University of New York, with appointments in the mathematics departments at Baruch College and at the Graduate Center. In 2018-2020 I was a postdoctoral researcher at the Institute for Advanced Study in Princeton and at DIMACS. In 2017-2018 I was a postdoctoral researcher at Harvard University.
I completed my Ph.D. studies at the School of Mathematics at Tel Aviv University, advised by Asaf Shapira, and my M.Sc. studies at the School of Computer Science advised by Oded Regev.
I have a broad interest in: extremal & additive combinatorics, graph/hypergraph theory, algebraic geometry, number theory, as well as in probabilistic & algebraic methods in combinatorics and their applications to theoretical computer science.
I also mentor in the NYC Discrete Math REU (Research Experience for Undergraduates).
For students interested in topics related to tensor ranks, below are brief introductory materials:
Email: guymoshkov at gmail.com
My work is supported by NSF grant DMS-2302988 ("Structure versus Randomness in Algebraic Geometry and Additive Combinatorics").
Research Highlights
Additive Combinatorics:
The partition-vs-analytic rank conjecture is true up to logarithmic factors
A first step towards the Polynomial Gowers Inverse conjecture over large fields
A proof, using tools from algebraic geometry, that several notions of rank for 3-tensors are equivalent --- and applications to computer science
Quanta Magazine covered some of these works: Mathematicians Find Structure in Biased Polynomials
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 famous 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
(* = paper written with student)
Quasi-linear Relation between Partition and Analytic Rank (with D. Zhu), submitted. *
Partition and Analytic Rank are Equivalent over Large Fields (with A. Cohen), Duke Mathematical Journal 172 (2023), 2433-2470. *
Sharp Effective Finite-Field Nullstellensatz (with J. Yu), The American Mathematical Monthly 130 (2023), 720-727. *
Structure vs. Randomness for Bilinear Maps (with A. Cohen), Discrete Analysis 12 (2022). *
A conference version appeared in the Proc. of the 53rd ACM Symposium on Theory of Computing (STOC 2021), 800-808.Geometric Rank of Tensors and Subrank of Matrix Multiplication (with S. Kopparty and J. Zuiddam), Discrete Analysis 1 (2023).
A conference version 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 IEEE Conference on Computational Complexity (CCC 2012), 159-169.
Teaching
Courses:
Vector Calculus (2022)
Linear Algebra & Matrix Methods (2021, 2023)
Analytic Geometry (2021)
Calculus III (2020, 2022)
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)
Teaching awards: 2014, 2016 (Rector's list for excellence in teaching)