ﻻ يوجد ملخص باللغة العربية
In this note, we study the relation between the parity decision tree complexity of a boolean function $f$, denoted by $mathrm{D}_{oplus}(f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR functions $F(x_1,ldots, x_k)= f(x_1opluscdotsoplus x_k)$, denoted by $mathrm{CC}^{(k)}(F)$. It is known that $mathrm{CC}^{(k)}(F)leq kcdotmathrm{D}_{oplus}(f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that [mathrm{D}_{oplus}(f)leq Obig(mathrm{CC}^{(4)}(F)^5big).] Our main tool is a recent result from additive combinatorics due to Sanders. As $mathrm{CC}^{(k)}(F)$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR functions are polynomially equivalent whenever $kgeq 4$. Remark: After the first version of this paper was finished, we discovered that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.
We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f circ textsf{XOR}$, called an $textsf{XOR}$ function. Using this duality, we develop polynomial based techniques for understanding the bounded
We prove a new lower bound on the parity decision tree complexity $mathsf{D}_{oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of
The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this context Disjointness is usually mentioned as a case where the method fails to gi
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product
We define nondeterministic communication complexity in the model of communication complexity with help of Babai, Hayes and Kimmel. We use it to prove logarithmic lower bounds on the NOF communication complexity of explicit graph functions, which are