Manik Dhar: ℓ∞ linear hashing and two-sided Kakeya bounds

Passcode for Zoom: 728726

Abstract: The celebrated Leftover Hash Lemma (LHL) states that for a given subset S of {0,1}^n and a function H:{0,1}^n → {0,1}^t sampled uniformly from a universal hash family, H(U_S) is close to uniform under statistical/ℓ1 distance with high probability (where U_S is uniform on S). In this talk, we present recent work (joint with Zeev Dvir) which proves an ℓ∞ variant of the LHL for the special case where H is a random linear map over a finite field.. In particular, we show that if H:(F_2)^n to (F_2)^t is a randomly sampled surjective linear map then H(U_S) is close in ℓ∞ distance to uniform. By known bounds from the load balancing literature [Raab and Steger 98], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss (log|S|-t).