Tata Institute of Fundamental Research
On the Fourier Spectrum of MOD Functions
STCS Student Seminar
Speaker:
Nikhil S Mande
Organiser:
Somnath Chakraborty
Date:
Friday, 13 Oct 2017, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
We use exponential sums to analyze the Fourier spectrum of functions of the type MOD_m^A (with output in {-1, 1}), for any constant m, and a general accepting set A. We will then see how this yields lower bounds on the number of monomials required by any real polynomial which sign represents MOD_m^A on all inputs.
No Fourier analysis background will be assumed, and I will start with a quick recap of the necessary Fourier analytic prerequisites.
| Speaker: | Nikhil S Mande |
| Organiser: | Somnath Chakraborty |
| Date: | Friday, 13 Oct 2017, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
We use exponential sums to analyze the Fourier spectrum of functions of the type MOD_m^A (with output in {-1, 1}), for any constant m, and a general accepting set A. We will then see how this yields lower bounds on the number of monomials required by any real polynomial which sign represents MOD_m^A on all inputs.
No Fourier analysis background will be assumed, and I will start with a quick recap of the necessary Fourier analytic prerequisites.
No Fourier analysis background will be assumed, and I will start with a quick recap of the necessary Fourier analytic prerequisites.