Title: Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
Speaker: Gil Cohen, Weizmann Institute
Date: Wednesday, October 15, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even n, there exists an explicit bijection f from the n-dimensional Boolean cube to the Hamming ball of equal volume embedded in (n+1)-dimensional Boolean cube, such that for all x and y it holds that dist(x,y) / 5 <= dist(f(x),f(y)) <= 4 dist(x,y), where dist(,) denotes the Hamming distance.
This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions requires ideas beyond the sensitivity-based structural results of Boppana [IPL 97].
No prior knowledge is assumed.
Joint work with Itai Benjamini and Igor Shinkar.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/