Zeev Dvir
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Zeev Dvir has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Manik Dhar
Department of Computer Science Princeton University
2 shared publications Albert Ai
Department of Mathematics, University of California, Berkeley, USA
1 shared publicationAvi Wigderson
School of Mathematics, Institute for Advanced Study, USA
1 shared publication- David Zuckerman
Department of Computer Science School of Engineering & Applied Sciences School of Engineering & Applied Sciences Department of Computer Science Stanford University Harvard University Harvard University University of Texas at Austin
1 shared publication - Ethan Leeman
The University of Texas at Austin
1 shared publication - Jean Bourgain
Institute for Advanced Study
1 shared publication
Latest Publications
- Open Access
Rank-metric separation in irreducible representations of finite groups
We give a general lower bound on the rank of matrices of the form $ρ(h) - I$ with $ρ: G \rightarrow GL({\mathbb F}^n)$ an irreducible representation of a finite group $G$. The main tool in the proof is a (strengthening) of a reduction due to Efremenko from low rank matrices spanned by a few images of $ρ$ to Locally Decodable Codes (LDCs), which are a special kind of error correcting codes. We then apply the known results on 2-query LDCs to derive our rank bound.Open AccessRank-metric separation in irreducible representations of finite groups
We give a general lower bound on the rank of matrices of the form $ρ(h) - I$ with $ρ: G \rightarrow GL({\mathbb F}^n)$ an irreducible representation of a finite group $G$. The main tool in the proof is a (strengthening) of a reduction due to Efremenko from low rank matrices spanned by a few images of $ρ$ to Locally Decodable Codes (LDCs), which are a special kind of error correcting codes. We then apply the known results on 2-query LDCs to derive our rank bound. - Open Access
- 9 December 2021
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 1
Proof of the Kakeya set conjecture over rings of integers modulo square-free N
A Kakeya set $S \subset (\mathbb{Z}/N\mathbb{Z})^n$ is a set containing a line in each direction. We show that, when $N$ is any square-free integer, the size of the smallest Kakeya set in $(\mathbb{Z}/N\mathbb{Z})^n$ is at least $C_{n,\epsilon} N^{n - \epsilon}$ for any $\epsilon$ -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime $N$. We also show that the case of general $N$ can be reduced to lower bounding the $\mathbb{F}_p$ rank of the incidence matrix of points and hyperplanes over $(\mathbb{Z}/p^k\mathbb{Z})^n$.Mathematics Subject Classifications: 05B20, 05B25- 9 December 2021
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 1
Open AccessProof of the Kakeya set conjecture over rings of integers modulo square-free N
A Kakeya set $S \subset (\mathbb{Z}/N\mathbb{Z})^n$ is a set containing a line in each direction. We show that, when $N$ is any square-free integer, the size of the smallest Kakeya set in $(\mathbb{Z}/N\mathbb{Z})^n$ is at least $C_{n,\epsilon} N^{n - \epsilon}$ for any $\epsilon$ -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime $N$. We also show that the case of general $N$ can be reduced to lower bounding the $\mathbb{F}_p$ rank of the incidence matrix of points and hyperplanes over $(\mathbb{Z}/p^k\mathbb{Z})^n$.Mathematics Subject Classifications: 05B20, 05B25 - Open AccessProof of the Kakeya set conjecture over rings of integers modulo square-free $N$A Kakeya set $S \subset (\mathbb{Z}/N\mathbb{Z})^n$ is a set containing a line in each direction. We show that, when $N$ is any square-free integer, the size of the smallest Kakeya set in $(\mathbb{Z}/N\mathbb{Z})^n$ is at least $C_{n,\epsilon} N^{n - \epsilon}$ for any $\epsilon$ -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime $N$. We also show that the case of general $N$ can be reduced to lower bounding the $\mathbb{F}_p$ rank of the incidence matrix of points and hyperplanes over $(\mathbb{Z}/p^k\mathbb{Z})^n$.Open AccessProof of the Kakeya set conjecture over rings of integers modulo square-free $N$A Kakeya set $S \subset (\mathbb{Z}/N\mathbb{Z})^n$ is a set containing a line in each direction. We show that, when $N$ is any square-free integer, the size of the smallest Kakeya set in $(\mathbb{Z}/N\mathbb{Z})^n$ is at least $C_{n,\epsilon} N^{n - \epsilon}$ for any $\epsilon$ -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime $N$. We also show that the case of general $N$ can be reduced to lower bounding the $\mathbb{F}_p$ rank of the incidence matrix of points and hyperplanes over $(\mathbb{Z}/p^k\mathbb{Z})^n$.
- 20 April 2016
- Published by Springer Nature in computational complexity
- Vol. 25 (2) , 305-307
Special issue “Computational Complexity Conference 2015” Guest Editors’ Foreword
- 20 April 2016
- Published by Springer Nature in computational complexity
- Vol. 25 (2) , 305-307
Special issue “Computational Complexity Conference 2015” Guest Editors’ Foreword
- 2 September 2015
- Published by Springer Nature in computational complexity
- Vol. 25 (4) , 921-931
Affine extractors over large fields with exponential error
- 2 September 2015
- Published by Springer Nature in computational complexity
- Vol. 25 (4) , 921-931
Affine extractors over large fields with exponential error
- Open Access
- 1 March 2014
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 2
SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY
We study questions in incidence geometry where the precise position of points is ‘blurry’ (for example due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of approximately collinear triples in a set of points in ${\mathbb{C}}^d$ implies that the points are close to a low dimensional affine subspace. This can be viewed as a stable variant of the Sylvester–Gallai theorem and its extensions. Building on the recently found connection between Sylvester–Gallai type theorems and complex locally correctable codes (LCCs), we define the new notion of stable LCCs, in which the (local) correction procedure can also handle small perturbations in the Euclidean metric. We prove that such stable codes with constant query complexity do not exist. No impossibility results were known in any such local setting for more than two queries.- 1 March 2014
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 2
Open AccessSYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY
We study questions in incidence geometry where the precise position of points is ‘blurry’ (for example due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of approximately collinear triples in a set of points in ${\mathbb{C}}^d$ implies that the points are close to a low dimensional affine subspace. This can be viewed as a stable variant of the Sylvester–Gallai theorem and its extensions. Building on the recently found connection between Sylvester–Gallai type theorems and complex locally correctable codes (LCCs), we define the new notion of stable LCCs, in which the (local) correction procedure can also handle small perturbations in the Euclidean metric. We prove that such stable codes with constant query complexity do not exist. No impossibility results were known in any such local setting for more than two queries. - Open Access
Incidence Theorems and Their Applications
We survey recent (and not so recent) results concerning arrangements of lines, points and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are: (1) Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc..), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi-Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multi-source extractors). (2) Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness-extractors. (3) Sylvester-Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many `local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes. Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics.
Open AccessIncidence Theorems and Their Applications
We survey recent (and not so recent) results concerning arrangements of lines, points and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are: (1) Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc..), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi-Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multi-source extractors). (2) Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness-extractors. (3) Sylvester-Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many `local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes. Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics.
- 25 June 2013
- Published by Springer Nature in computational complexity
- Vol. 23 (4) , 509-529
Variety Evasive Sets
- 25 June 2013
- Published by Springer Nature in computational complexity
- Vol. 23 (4) , 509-529
Variety Evasive Sets
- Open Access
- 12 December 2012
- Published by Emerald Publishing in Foundations and Trends® in Theoretical Computer Science
- Vol. 6 (4) , 257-393
Incidence Theorems and Their Applications
We survey recent (and not so recent) results concerning arrangements of lines, points, and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are: Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc.), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi–Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multisource extractors). Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness extractors. Sylvester–Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many 'local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes. Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics. The author is supported under NSF grant CCF-1217416.
- 12 December 2012
- Published by Emerald Publishing in Foundations and Trends® in Theoretical Computer Science
- Vol. 6 (4) , 257-393
Open AccessIncidence Theorems and Their Applications
We survey recent (and not so recent) results concerning arrangements of lines, points, and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are: Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc.), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi–Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multisource extractors). Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness extractors. Sylvester–Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many 'local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes. Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics. The author is supported under NSF grant CCF-1217416.