Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLog-rank and lifting for AND-functions
99
0
0.0
(
0
)
Added by
Sam McGuire
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $f: {0,1}^n to {0, 1}$ be a boolean function, and let $f_land (x, y) = f(x land y)$ denote the AND-function of $f$, where $x land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_land$ and show that, up to a $log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_land$. This comes within a $log n$ factor of establishing the log-rank conjecturefor AND-functions with no assumptions on $f$. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on $f$ such as monotonicity or low $mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_land$ is polynomially-related to the AND-decision tree complexity of $f$. The results rely on a new structural result regarding boolean functions $f:{0, 1}^n to {0, 1}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:{0,1}^n to mathbb{R}$ with a larger range.
rate research
Read More
We prove upper bounds on deterministic communication complexity in terms of log of the rank and simp
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
We define the Augmentation property for binary matrices with respect to different rank functions. A matrix $A$ has the Augmentation property for a given rank function, if for any subset of column vectors $x_1,...,x_t$ for for which the rank of $A$ does not increase when augmented separately with each of the vectors $x_i$, $1leq i leq t$, it also holds that the rank does not increase when augmenting $A$ with all vectors $x_1,...,x_t$ simultaneously. This property holds trivially for the usual linear rank over the reals, but as we show, things change significantly when considering the binary and boolean rank of a matrix. We prove a necessary and sufficient condition for this property to hold under the binary and boolean rank of binary matrices. Namely, a matrix has the Augmentation property for these rank functions if and only if it has a unique base that spans all other bases of the matrix with respect to the given rank function. For the binary rank, we also present a concrete characterization of a family of matrices that has the Augmentation property. This characterization is based on the possible types of linear dependencies between rows of $V$, in optimal binary decompositions of the matrix as $A=Ucdot V$. Furthermore, we use the Augmentation property to construct simple families of matrices, for which there is a gap between their real and binary rank and between their real and boolean rank.
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM 20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
