Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KAKEYA:
Reports tagged with kakeya:
TR08-058 | 1st June 2008
Zeev Dvir, Avi Wigderson

#### Kakeya sets, new mergers and old extractors

A merger is a probabilistic procedure which extracts the
randomness out of any (arbitrarily correlated) set of random
variables, as long as one of them is uniform. Our main result is
an efficient, simple, optimal (to constant factors) merger, which,
for $k$ random vairables on $n$ bits each, uses a ... more >>>

TR09-077 | 16th September 2009
Zeev Dvir

#### From Randomness Extraction to Rotating Needles

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

TR22-047 | 4th April 2022
Manik Dhar, Zeev Dvir

#### Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

Revisions: 1

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$ with $q^t$ taken to be sufficiently smaller than $|S|$. Let ... more >>>

ISSN 1433-8092 | Imprint