论文标题
关于傅里叶式布尔功能的均等决策树
On parity decision trees for Fourier-sparse Boolean functions
论文作者
论文摘要
我们研究布尔功能的平价决策树。我们研究的动机是XOR函数的对数秩猜想及其与傅立叶分析和均等决策树复杂性的联系。让F成为带有傅立叶支持S和傅立叶稀疏k的布尔功能。 1）我们通过概率方法证明，存在一个计算f的深度O（SQRT K）的平价决策树。这与布尔函数的平等决策树复杂性相匹配（Tsang，Wong，Xie和Zhang，Focs 2013）。此外，虽然先前的结构（Tsang等人，Focs，2013，Shpilka，Tal和Volk，Comput。Complex。2017）通过仔细选择在每个步骤中要查询的奇偶群来建造树木，我们的证明表明，对奇偶群的幼稚采样就足够了。 2）我们通过表明布尔函数的傅立叶光谱满足自然的“折叠特性”来概括上述结果，则可以对上述证明进行调整以确定复杂性的多个复杂性多种态度的存在，而多个百分点小于o（sqrt k）。在这方面，我们做出了一个猜想，如果是的，则意味着XOR函数的通信复杂性在上面是其通信矩阵等级的第四根词根，从而改善了先前已知的秩上线的上限（Tsang等，focs，focs，2013年，Lovett，Lovett，J。Acm。2016）。 3）可以通过基本技术来显示，对于任何布尔函数f和s中的所有布尔函数（alpha，beta），在s中存在另一对（伽玛，三角洲），使alpha + beta = gamba = gamma + delta。除其他结果外，我们还必须在f_2^n中存在几个伽玛，以便与alpha_1 + alpha_2 = gamma至少有三对（alpha_1，alpha_2）。
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. Let f be a Boolean function with Fourier support S and Fourier sparsity k. 1) We prove via the probabilistic method that there exists a parity decision tree of depth O(sqrt 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. 2) 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(sqrt k). 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). 3) It can be shown by elementary techniques that for any Boolean function f and all pairs (alpha, beta) of parities in S, there exists another pair (gamma, delta) of parities in S such that alpha + beta = gamma + delta. We show, among other results, that there must exist several gamma in F_2^n such that there are at least three pairs (alpha_1, alpha_2) of parities in S with alpha_1 + alpha_2 = gamma.
