13 citations · 53 across the 21 of their papers we have counts for
8 papers · 1 filter
Integer points in dilates of polytopes
Shubhangi Saraf, Narmada Varadarajan
In this paper we study how the number of integer points in a polytope grows as we dilate the polytope. We prove new and essentially tight bounds on this quantity by specifically st…
On the number of ordinary lines determined by sets in complex space
Abdul Basit, Zeev Dvir, Shubhangi Saraf +1
Kelly's theorem states that a set of points affinely spanning must determine at least one ordinary complex line (a line passing through exactly two of the points…
Finite field Kakeya and Nikodym sets in three dimensions
Ben Lund, Shubhangi Saraf, Charles Wolf
We give improved lower bounds on the size of Kakeya and Nikodym sets over . We also propose a natural conjecture on the minimum number of points in the union of a n…
Incidence Bounds for Block Designs
Ben Lund, Shubhangi Saraf
We prove three theorems giving extremal bounds on the incidence structures determined by subsets of the points and blocks of a balanced incomplete block design (BIBD). These result…
Sylvester-Gallai type theorems for approximate collinearity
Albert Ai, Zeev Dvir, Shubhangi Saraf +1
We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and mor…
Improved rank bounds for design matrices and a new proof of Kelly's theorem
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus…
Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf +1
We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. (A) We show that every Kakeya set (a set of points th…
Improved lower bound on the size of Kakeya sets over finite fields
Shubhangi Saraf, Madhu Sudan
In a recent breakthrough, Dvir showed that every Kakeya set in $\F^n$ must be of cardinality at least $c_n |\F|^n$ where . We improve this lower bound to $β^n |\F…