Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity
| العنوان: | Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity |
|---|---|
| المؤلفون: | Swagato Sanyal |
| المصدر: | Automata, Languages, and Programming ISBN: 9783662476710 ICALP (1) |
| بيانات النشر: | Springer Berlin Heidelberg, 2015. |
| سنة النشر: | 2015 |
| مصطلحات موضوعية: | TheoryofComputation_MISCELLANEOUS, Combinatorics, symbols.namesake, Fourier transform, Fourier analysis, Discrete-time Fourier transform, Discrete Fourier series, Fourier inversion theorem, symbols, Fourier series, Upper and lower bounds, Mathematics, Sine and cosine transforms |
| الوصف: | We prove that the Fourier dimension of any Boolean function with Fourier sparsity \(s\) is at most \(O\left( \sqrt{s} \log s\right) \). This bound is tight up to a factor of \(O(\log s)\) as the Fourier dimension and sparsity of the addressing function are quadratically related. We obtain our result by bounding the non-adaptive parity decision tree complexity, which is known to be equivalent to the Fourier dimension. A consequence of our result is that XOR functions have a one way deterministic communication protocol of communication complexity \(O(\sqrt{r} \log r)\), where \(r\) is the rank of its communication matrix. |
| ردمك: | 978-3-662-47671-0 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::4adaa5d717114743d521183f64fc12b3 https://doi.org/10.1007/978-3-662-47672-7_84 |
| رقم الأكسشن: | edsair.doi...........4adaa5d717114743d521183f64fc12b3 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783662476710 |
|---|