Source author record

Guy Moshkovitz

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Data Structures and Algorithms math.AC

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Sharp Effective Finite-Field Nullstellensatz

The (weak) Nullstellensatz over finite fields says that if $P_1,\ldots,P_m$ are $n$ -variate degree- $d$ polynomials with no common zero over a finite field $\mathbb{F}$ then there are polynomials $R_1,\ldots,R_m$ such that $R_1P_1+\cdots+R_mP_m \equiv 1$ . Green and Tao [Contrib. Discrete Math. 2009, Proposition 9.1] used a regularity lemma to obtain an effective proof, showing that the degrees of the polynomials $R_i$ can be bounded independently of $n$ , though with an Ackermann-type dependence on the other parameters $m$ , $d$ , and $|\mathbb{F}|$ . In this paper we use the polynomial method to give a proof with a degree bound of $md(|\mathbb{F}|-1)$ . We also show that the dependence on each of the parameters is the best possible up to an absolute constant. We further include a generalization, offered by Pete L. Clark, from finite fields to arbitrary subsets in arbitrary fields, provided the polynomials $P_i$ take finitely many values on said subset.

preprint2016arXiv

A Sparse Regular Approximation Lemma

We introduce a new variant of Szemerédi's regularity lemma which we call the "sparse regular approximation lemma" (SRAL). The input to this lemma is a graph $G$ of edge density $p$ and parameters $ε, δ$ , where we think of $δ$ as a constant. The goal is to construct an $ε$ -regular partition of $G$ while having the freedom to add/remove up to $δ|E(G)|$ edges. As we show here, this weaker variant of the regularity lemma already suffices for proving the graph removal lemma and the hypergraph regularity lemma, which are two of the main applications of the (standard) regularity lemma. This of course raises the following question: can one obtain quantitative bounds for SRAL that are significantly better than those associated with the regularity lemma? Our first result answers the above question affirmatively by proving an upper bound for SRAL given by a tower of height $O(\log 1/p)$ . This allows us to reprove Fox's upper bound for the graph removal lemma. Our second result is a matching lower bound for SRAL showing that a tower of height $Ω(\log 1/p)$ is unavoidable. We in fact prove a more general multicolored lower bound which is essential for proving lower bounds for the hypergraph regularity lemma.

preprint2015arXiv

Constructing Near Spanning Trees with Few Local Inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like to decide whether $e$ belongs to a connected subgraph $G'$ consisting of $(1+ε)n$ edges (for a prespecified constant $ε>0$ ), where the decision for different edges should be consistent with the same subgraph $G'$ . Can this task be performed by inspecting only a {\em constant} number of edges in $G$ ? Our main results are: (1) We show that if every $t$ -vertex subgraph of $G$ has expansion $1/(\log t)^{1+o(1)}$ then one can (deterministically) construct a sparse spanning subgraph $G'$ of $G$ using few inspections. To this end we analyze a "local" version of a famous minimum-weight spanning tree algorithm. (2) We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of $3$ -regular graphs of high girth, in which every $t$ -vertex subgraph has expansion $1/(\log t)^{1-o(1)}$ .

preprint2015arXiv

Decomposing a Graph Into Expanding Subgraphs

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that "any graph is close to being the disjoint union of expanders". Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. These results are obtained as corollaries of a new family of graphs, which we construct by picking random subgraphs of the hypercube, and analyze using (simple) arguments from the theory of metric embedding.

preprint2014arXiv

An Improved Lower Bound for Arithmetic Regularity

The arithmetic regularity lemma due to Green [GAFA 2005] is an analogue of the famous Szemer{é}di regularity lemma in graph theory. It shows that for any abelian group $G$ and any bounded function $f:G \to [0,1]$ , there exists a subgroup $H \le G$ of bounded index such that, when restricted to most cosets of $H$ , the function $f$ is pseudorandom in the sense that all its nontrivial Fourier coefficients are small. Quantitatively, if one wishes to obtain that for $1-ε$ fraction of the cosets, the nontrivial Fourier coefficients are bounded by $ε$ , then Green shows that $|G/H|$ is bounded by a tower of twos of height $1/ε^3$ . He also gives an example showing that a tower of height $Ω(\log 1/ε)$ is necessary. Here, we give an improved example, showing that a tower of height $Ω(1/ε)$ is necessary.

preprint2014arXiv

Exact Bounds for Some Hypergraph Saturation Problems

Let W_n(p,q) denote the minimum number of edges in an n x n bipartite graph G on vertex sets X,Y that satisfies the following condition; one can add the edges between X and Y that do not belong to G one after the other so that whenever a new edge is added, a new copy of K_{p,q} is created. The problem of bounding W_n(p,q), and its natural hypergraph generalization, was introduced by Balogh, Bollobás, Morris and Riordan. Their main result, specialized to graphs, used algebraic methods to determine W_n(1,q). Our main results in this paper give exact bounds for W_n(p,q), its hypergraph analogue, as well as for a new variant of Bollobás's Two Families theorem. In particular, we completely determine W_n(p,q), showing that if 1 <= p <= q <= n then W_n(p,q) = n^2 - (n-p+1)^2 + (q-p)^2. Our proof applies a reduction to a multi-partite version of the Two Families theorem obtained by Alon. While the reduction is combinatorial, the main idea behind it is algebraic.

preprint2013arXiv

A Short Proof of Gowers' Lower Bound for the Regularity Lemma

A celebrated result of Gowers states that for every ε> 0 there is a graph G so that every ε-regular partition of G (in the sense of Szemeredi's regularity lemma) has order given by a tower of exponents of height polynomial in 1/ε. In this note we give a new proof of this result that uses a construction and proof of correctness that are significantly simpler and shorter.

preprint2012arXiv

Ramsey Theory, Integer Partitions and a New Proof of the Erdos-Szekeres Theorem

Let H be a k-uniform hypergraph whose vertices are the integers 1,...,N. We say that H contains a monotone path of length n if there are x_1 < x_2 < ... < x_{n+k-1} so that H contains all n edges of the form {x_i,x_{i+1},...,x_{i+k-1}}. Let N_k(q,n) be the smallest integer N so that every q-coloring of the edges of the complete k-uniform hypergraph on N vertices contains a monochromatic monotone path of length n. While the study of N_k(q,n) for specific values of k and q goes back (implicitly) to the seminal 1935 paper of Erdos and Szekeres, the problem of bounding N_k(q,n) for arbitrary k and q was studied by Fox, Pach, Sudakov and Suk. Our main contribution here is a novel approach for bounding the Ramsey-type numbers N_k(q,n), based on establishing a surprisingly tight connection between them and the enumerative problem of counting high-dimensional integer partitions. Some of the concrete results we obtain using this approach are the following: 1. We show that for every fixed q we have N_3(q,n)=2^{Θ(n^{q-1})}, thus resolving an open problem raised by Fox et al. 2. We show that for every k >= 3, N_k(2,n)=2^{\cdot^{\cdot^{2^{(2-o(1))n}}}} where the height of the tower is k-2, thus resolving an open problem raised by Elias and Matousek. 3. We give a new pigeonhole proof of the Erdős-Szekeres Theorem on cups-vs-caps, similar to Seidenberg's proof of the Erdos-Szekeres Lemma on increasing/decreasing subsequences.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.