Zobrazeno 1 - 10
of 144
pro vyhledávání: '"DVIR, ZEEV"'
Autor:
Dhar, Manik, Dvir, Zeev
Publikováno v:
TheoretiCS, Volume 3 (April 3, 2024) theoretics:11529
We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_\infty$ sense. More concretely, consider a set $S \subset \mathbb{F}_q^n$ and a randomly chosen linear map $L : \mathbb{F}_q^n \to \mathbb{F}_q^t$ w
Externí odkaz:
http://arxiv.org/abs/2204.01665
Autor:
Dhar, Manik, Dvir, Zeev
Publikováno v:
Combinatorial Theory, 2021:1
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
Externí odkaz:
http://arxiv.org/abs/2011.11225
Publikováno v:
Discrete Analysis 2021:22
A $(k,m)$-Furstenberg set $S \subset \mathbb{F}_q^n$ over a finite field is a set that has at least $m$ points in common with a $k$-flat in every direction. The question of determining the smallest size of such sets is a natural generalization of the
Externí odkaz:
http://arxiv.org/abs/1909.03180
A $(k,m)$-Furstenberg set is a subset $S \subset \mathbb{F}_q^n$ with the property that each $k$-dimensional subspace of $\mathbb{F}_q^n$ can be translated so that it intersects $S$ in at least $m$ points. Ellenberg and Erman proved that $(k,m)$-Furs
Externí odkaz:
http://arxiv.org/abs/1909.02431
Autor:
Dvir, Zeev, Liu, Allen
The concept of matrix rigidity was first introduced by Valiant in 1977. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Vali
Externí odkaz:
http://arxiv.org/abs/1902.07334
We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear
Externí odkaz:
http://arxiv.org/abs/1811.02725
We introduce a simple logical inference structure we call a $\textsf{spanoid}$ (generalizing the notion of a matroid), which captures well-studied problems in several areas. These include combinatorial geometry, algebra (arrangements of hypersurfaces
Externí odkaz:
http://arxiv.org/abs/1809.10372
We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice $L$ if and only if $L$ is relatively complemented, and prove partial results towards this
Externí odkaz:
http://arxiv.org/abs/1807.04957
Autor:
Dvir, Zeev, Moran, Shay
We show that any family of subsets $A\subseteq 2^{[n]}$ satisfies $\lvert A\rvert \leq O\bigl(n^{\lceil{d}/{2}\rceil}\bigr)$, where $d$ is the VC dimension of $\{S\triangle T \,\vert\, S,T\in A\}$, and $\triangle$ is the symmetric difference operator
Externí odkaz:
http://arxiv.org/abs/1806.05737