Tata Institute of Fundamental Research
On the Structure of Boolean Functions With Small Spectral Norm
Student Seminar
Speaker:
Swagato Sanyal
Organiser:
Nikhil S Mande
Date:
Friday, 18 Jul 2014, 14:30 to 16:00
Venue:
D-405
(Scan to add to calendar)
Abstract:
Abstract: Let f: F_2^n -> {+1, -1} be a Boolean function with the first Fourier norm A and Fourier sparsity s. We will prove that there is an affine subspace of the vector space F_2^n, of dimension O(A), on which the f is constant. If time permits, we will prove that f has a parity decision tree of depth O(\sqrt{s}). These results are by Tsang et al which improves on earlier results by Shpilka et al.
References:
Amir Shpilka, Avishay Tal, Ben lee Volk. On the Structure of Boolean Functions with Small Spectral Norm. ITCS 2014
Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang. Fourier sparsity, spectral norm and the log rank conjecture. FOCS 2013
| Speaker: | Swagato Sanyal |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 18 Jul 2014, 14:30 to 16:00 |
| Venue: | D-405 |
(Scan to add to calendar)
Abstract:
Abstract: Let f: F_2^n -> {+1, -1} be a Boolean function with the first Fourier norm A and Fourier sparsity s. We will prove that there is an affine subspace of the vector space F_2^n, of dimension O(A), on which the f is constant. If time permits, we will prove that f has a parity decision tree of depth O(\sqrt{s}). These results are by Tsang et al which improves on earlier results by Shpilka et al.
References:
Amir Shpilka, Avishay Tal, Ben lee Volk. On the Structure of Boolean Functions with Small Spectral Norm. ITCS 2014
Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang. Fourier sparsity, spectral norm and the log rank conjecture. FOCS 2013
References:
Amir Shpilka, Avishay Tal, Ben lee Volk. On the Structure of Boolean Functions with Small Spectral Norm. ITCS 2014
Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang. Fourier sparsity, spectral norm and the log rank conjecture. FOCS 2013