School of Technology and Computer Science Seminars
On the Fourier Spectrum of MOD Functions
by Nikhil S Mande (School of Technology and Computer Science, TIFR)
Friday, October 13, 2017
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
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. |