Document Open Access Logo

Searching for Regularity in Bounded Functions

Authors Siddharth Iyer, Michael Whitmeyer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.83.pdf
  • Filesize: 0.84 MB
  • 20 pages

Document Identifiers

Author Details

Siddharth Iyer
  • University of Washington CSE, Seattle, WA, USA
Michael Whitmeyer
  • University of Washington CSE, Seattle, WA, USA

Funding

  • Iyer, Siddharth: Research supported by NSF grant CCF-2131899.
  • Whitmeyer, Michael: Research supported by NSF grant CCF-2006359.

Acknowledgements

We thank Anup Rao for posing the question that launched this project and for his invaluable advice and feedback. We are also grateful Paul Beame for his extremely helpful advice, discussions, and feedback. Finally, we thank Sandy Kaplan for detailed feedback on this writeup.

Cite As Get BibTex

Siddharth Iyer and Michael Whitmeyer. Searching for Regularity in Bounded Functions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.83

Abstract

Given a function f on F₂ⁿ, we study the following problem. What is the largest affine subspace 𝒰 such that when restricted to 𝒰, all the non-trivial Fourier coefficients of f are very small? 
For the natural class of bounded Fourier degree d functions f: F₂ⁿ → [-1,1], we show that there exists an affine subspace of dimension at least Ω(n^{1/d!} k^{-2}), wherein all of f’s nontrivial Fourier coefficients become smaller than 2^{-k}. To complement this result, we show the existence of degree d functions with coefficients larger than 2^{-d log n} when restricted to any affine subspace of dimension larger than Ω(d n^{1/(d-1)}). In addition, we give explicit examples of functions with analogous but weaker properties.
Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of F₂ⁿ that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
Keywords
  • regularity
  • bounded function
  • Boolean function
  • Fourier analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20, May 2001. URL: https://doi.org/10.1007/s004930070001.
  2. Shalev Ben David. Quantum speedups in query complexity. PhD thesis, Massachusetts Institute of Technology, 2017. Google Scholar
  3. Eli Ben-Sasson and Swastik Kopparty. Affine dispersers from subspace polynomials. SIAM J. Comput., 41(4):880-914, 2012. Google Scholar
  4. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  5. Eshan Chattopadhyay, Jesse Goodman, and Jyun-Jie Liao. Affine extractors for almost logarithmic entropy. In FOCS, pages 622-633. IEEE, 2021. Google Scholar
  6. Gil Cohen and Avishay Tal. Two structural results for low degree polynomials and applications. In APPROX-RANDOM, volume 40 of LIPIcs, pages 680-709. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  7. Alan M. Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In FOCS, pages 12-20. IEEE Computer Society, 1996. Google Scholar
  8. Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan. Parallel repetition for the GHZ game: A simpler proof. In APPROX-RANDOM, volume 207 of LIPIcs, pages 62:1-62:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  9. Ben Green. A szemerédi-type regularity lemma in abelian groups. Geometric and Functional Analysis, 15:340-376, January 2005. URL: https://doi.org/10.1007/s00039-005-0509-8.
  10. A. W. Hales and R. I. Jewett. Regularity and positional games. Transactions of the American Mathematical Society, 106(2):222-229, 1963. Google Scholar
  11. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. URL: http://www.jstor.org/stable/2282952.
  12. Kaave Hosseini, Shachar Lovett, Guy Moshkovitz, and Asaf Shapira. An improved lower bound for arithmetic regularity. Mathematical Proceedings of the Cambridge Philosophical Society, 161(2):193-197, 2016. URL: https://doi.org/10.1017/S030500411600013X.
  13. Zander Kelley and Raghu Meka. Strong bounds for 3-progressions, 2023. URL: https://arxiv.org/abs/2302.05537.
  14. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In FOCS, pages 168-177. IEEE Computer Society, 2016. Google Scholar
  15. Roy Meshulam. On subsets of finite abelian groups with no 3-term arithmetic progressions. J. Comb. Theory Ser. A, 71(1):168-172, July 1995. URL: https://doi.org/10.1016/0097-3165(95)90024-1.
  16. Gatis Midrijanis. Exact quantum query complexity for total boolean functions, 2004. URL: https://doi.org/10.48550/arXiv.quant-ph/0403168.
  17. Ryan O'Donnell. Analysis of boolean functions. CoRR, abs/2105.10386, 2021. URL: https://arxiv.org/abs/2105.10386.
  18. Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, and Li-Yang Tan. A composition theorem for parity kill number. In Computational Complexity Conference, pages 144-154. IEEE Computer Society, 2014. Google Scholar
  19. K. F. Roth. On certain sets of integers. Journal of the London Mathematical Society, s1-28(1):104-109, 1953. URL: https://doi.org/10.1112/jlms/s1-28.1.104.
  20. I. Ruzsa and E. Szemerédi. Triple systems with no six points carrying three triangles. Combinatorica, 18, January 1976. Google Scholar
  21. Ronen Shaltiel. Dispersers for affine sources with sub-polynomial entropy. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 247-256, 2011. URL: https://doi.org/10.1109/FOCS.2011.37.
  22. Asaf Shapira. Graph Property Testing and Related Problems. University of Tel-Aviv, 2006. Google Scholar
  23. Endre Szemerédi. Regular partitions of graphs. Technical report, Stanford Univ Calif Dept of Computer Science, 1975. Google Scholar
  24. Avishay Tal. Properties and applications of boolean function composition. In ITCS, pages 441-454. ACM, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact