Improved bounds on parity decision tree depth for boolean functions

Parity Decision Trees of Depth $O(4^d \log\|\widehat f\|_1)$ for Boolean Functions $f$ of $F_2$-Degree $d$

Computational Complexity

Summary

This paper looks at a way to represent certain complex yes/no functions called boolean functions using parity decision trees, which ask questions about sums of inputs. The authors find a better upper limit on how deep these trees need to be, depending on measures of the function’s complexity called degree and spectral norm. Their improvement means that for functions with low degree, the tree depth grows more slowly than previously known. They use new mathematical techniques to show this tighter relationship between the function’s characteristics and the size of the parity decision tree needed to compute it.

What this means in practice

  • For complexity theorists: Use tighter upper bounds on parity decision tree depth to analyze boolean function complexity and communication protocols more precisely.
  • For cryptographic engineers: Better understand the computational complexity of boolean functions relevant for cryptographic primitives by relating the degree and spectral norm to parity decision tree depth.

A theory result. No direct application yet.

Authors

Shengyu Zhang

Abstract

Let $f\colon F_2^n\to\{-1,+1\}$ have $F_2$-degree $d\ge2$. We prove that its deterministic parity decision tree depth satisfies \[ D_{\oplus} (f)= O(4^d \log_2\|\widehat f\|_1) = O(4^d \log_2 s(f)), \] where $\|\widehat f\|_1=\sum_ξ|\widehat f(ξ)|$ is the Fourier spectral norm and $s(f)$ is the Fourier sparsity. The bound is linear in the logarithm of the spectral norm for every fixed degree, with singly exponential dependence on $d$. This improves the previously best known bound of $O(2^{d^2/2} \log^{d-2} \|\widehat f\|_1)$ due to Tsang, Wong, Xie and Zhang (FOCS 2013). Our result establishes the log-rank conjecture for $\mathrm{XOR}$ functions of $F_2$-degree $O(\log\log s(f))$, extending the previously accessible range $d=O(1)$. The proof combines field lifting, multiplicative derivatives, a multiplicity-based generic-rank comparison, a Schur-complement vanishing argument, and dimension-preserving descent to $F_2$ to lower the degree on every coset of a common subspace.
View PDFOpen arXiv