On Parity Decision Trees for Fourier-Sparse Boolean Functions

Authors Nikhil S. Mande, Swagato Sanyal



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.29.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Nikhil S. Mande
  • Georgetown University, Washington, DC, USA
Swagato Sanyal
  • Indian Institute of Technology Kharagpur, India

Acknowledgements

We thank Prahladh Harsha, Srikanth Srinivasan, Sourav Chakraborty and Manaswi Paraashar for useful discussions.

Cite AsGet BibTex

Nikhil S. Mande and Swagato Sanyal. On Parity Decision Trees for Fourier-Sparse Boolean Functions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.29

Abstract

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let f : 𝔽₂ⁿ → {-1, 1} be a Boolean function with Fourier support 𝒮 and Fourier sparsity k. - We prove via the probabilistic method that there exists a parity decision tree of depth O(√k) that computes f. This matches the best known upper bound on the parity decision tree complexity of Boolean functions (Tsang, Wong, Xie, and Zhang, FOCS 2013). Moreover, while previous constructions (Tsang et al., FOCS 2013, Shpilka, Tal, and Volk, Comput. Complex. 2017) build the trees by carefully choosing the parities to be queried in each step, our proof shows that a naive sampling of the parities suffices. - We generalize the above result by showing that if the Fourier spectra of Boolean functions satisfy a natural "folding property", then the above proof can be adapted to establish existence of a tree of complexity polynomially smaller than O(√ k). More concretely, the folding property we consider is that for most distinct γ, δ in 𝒮, there are at least a polynomial (in k) number of pairs (α, β) of parities in 𝒮 such that α+β = γ+δ. We make a conjecture in this regard which, if true, implies that the communication complexity of an XOR function is bounded above by the fourth root of the rank of its communication matrix, improving upon the previously known upper bound of square root of rank (Tsang et al., FOCS 2013, Lovett, J. ACM. 2016). - Motivated by the above, we present some structural results about the Fourier spectra of Boolean functions. It can be shown by elementary techniques that for any Boolean function f and all (α, β) in binom(𝒮,2), there exists another pair (γ, δ) in binom(𝒮,2) such that α + β = γ + δ. One can view this as a "trivial" folding property that all Boolean functions satisfy. Prior to our work, it was conceivable that for all (α, β) ∈ binom(𝒮,2), there exists exactly one other pair (γ, δ) ∈ binom(𝒮,2) with α + β = γ + δ. We show, among other results, that there must exist several γ ∈ 𝔽₂ⁿ such that there are at least three pairs of parities (α₁, α₂) ∈ binom(𝒮,2) with α₁+α₂ = γ. This, in particular, rules out the possibility stated earlier.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
Keywords
  • Parity decision trees
  • log-rank conjecture
  • analysis of Boolean functions
  • communication complexity

Metrics

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

References

  1. Anurag Anshu, Naresh Goud Boddu, and Dave Touchette. Quantum log-approximate-rank conjecture is also false. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 982-994, 2019. URL: https://doi.org/10.1109/FOCS.2019.00063.
  2. Anna Bernasconi and Bruno Codenotti. Spectral analysis of boolean functions as a graph eigenvalue problem. IEEE Trans. Computers, 48(3):345-351, 1999. URL: https://doi.org/10.1109/12.755000.
  3. Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 42-53, 2019. URL: https://doi.org/10.1145/3313276.3316353.
  4. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR functions. SIAM J. Comput., 47(1):208-217, 2018. URL: https://doi.org/10.1137/17M1136869.
  5. Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. URL: https://doi.org/10.1561/0400000040.
  6. László Lovász and Michael E. Saks. Lattices, möbius functions and communication complexity. In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, pages 81-90, 1988. URL: https://doi.org/10.1109/SFCS.1988.21924.
  7. Shachar Lovett. Communication is bounded by root of rank. J. ACM, 63(1):1:1-1:9, 2016. URL: https://doi.org/10.1145/2724704.
  8. Nikhil S. Mande and Swagato Sanyal. On parity decision trees for Fourier-sparse Boolean functions. CoRR, abs/2008.00266, 2020. URL: http://arxiv.org/abs/2008.00266.
  9. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  10. Swagato Sanyal. Fourier sparsity and dimension. Theory of Computing, 15(1):1-13, 2019. Google Scholar
  11. Amir Shpilka, Avishay Tal, and Ben lee Volk. On the structure of boolean functions with small spectral norm. Comput. Complex., 26(1):229-273, 2017. URL: https://doi.org/10.1007/s00037-015-0110-y.
  12. Makrand Sinha and Ronald de Wolf. Exponential separation between quantum communication and logarithm of approximate rank. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 966-981, 2019. URL: https://doi.org/10.1109/FOCS.2019.00062.
  13. Robert C Titsworth. Correlation properties of cyclic sequences. PhD thesis, California Institute of Technology, 1962. Google Scholar
  14. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 658-667, 2013. URL: https://doi.org/10.1109/FOCS.2013.76.
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