The Fourier Transform of Restrictions of Functions on the Slice

Autor:	Rao, Shravas
Rok vydání:	2021
Předmět:	Mathematics - Combinatorics Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2111.03213 Zobrazit plný text záznamu View this record from Arxiv