Uncertainty principle in the hypercube and short vectors in linear codes

Seminar
Speaker
Alex Samorodnitsky (Hebrew University, Jerusalem)
Date
10/04/2016 - 15:30 - 14:00Add to Calendar 2016-04-10 14:00:00 2016-04-10 15:30:00 Uncertainty principle in the hypercube and short vectors in linear codes The uncertainty principle in the n-dimensional hypercube states that if a non-zero function is supported in A and its Fourier transform is supported in B, then |A||B| is at least 2^n.  We consider a relaxed version, requiring only a non-negligible fraction of the l_2 norm of the function to be attained in A and of its transform in B. Provided either A or B is a Hamming ball, we give a description of the possible joint behavior of |A| and |B|. This description is tight on the exponential scale (that is, assuming both A and B are exponentially small). The main technical tool we use is a stronger version of the hypercontractive inequality for functions with exponentially small support.  As a corollary we show that any binary linear code contains "many" (in the appropriate sense) codewords whose length is close to that guaranteed by the linear programming bound. Joint work with Yury Polyanskiy. Math building, 3rd floor seminar room (216/201) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Math building, 3rd floor seminar room (216/201)
Abstract

The uncertainty principle in the n-dimensional hypercube states that if a non-zero function is supported in A and its Fourier transform is supported in B, then |A||B| is at least 2^n. 

We consider a relaxed version, requiring only a non-negligible fraction of the l_2 norm of the function to be attained in A and of its transform in B. Provided either A or B is a Hamming ball, we give a description of the possible joint behavior of |A| and |B|. This description is tight on the exponential scale (that is, assuming both A and B are exponentially small). The main technical tool we use is a stronger version of the hypercontractive inequality for functions with exponentially small support. 

As a corollary we show that any binary linear code contains "many" (in the appropriate sense) codewords whose length is close to that guaranteed by the linear programming bound.

Joint work with Yury Polyanskiy.

Last Updated Date : 31/03/2016