The Fourier Transform of Restrictions of Functions on the Slice

11/05/2021
by   Shravas Rao, et al.
0

This paper considers the Fourier transform over the slice of the Boolean hypercube. We prove a relationship between the Fourier coefficients of a function over the slice, and the Fourier coefficients of its restrictions. As an application, we prove a Goldreich-Levin theorem for functions on the slice based on the Kushilevitz-Mansour algorithm for the Boolean hypercube.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset