M.Sc Thesis | |

M.Sc Student | Tal Avishay |
---|---|

Subject | On The Minimal Fourier Degree of Symmetric Boolean Functions |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Amir Shpilka |

Full Thesis text |

In this thesis we give a new upper bound on the minimal degree of a
nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically,
we prove that for every non-linear and symmetric *f:*{0,1}* ^{k }→*{0,1}
there exists a non-empty subset

Our bound on the degree greatly improves the previous result of
Kolountzakis et al. [KLMMV09] who proved that |*S*| = O(*k* / log(*k*)).