One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication
matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
A subset of the integer planar grid $[N] times [N]$ is called corner-free if it contains no triple of the form $(x,y), (x+delta,y), (x,y+delta)$. It is known that such a set has a vanishingly small density, but how large this density can be remains u
nknown. The best previous construction was based on Behrends large subset of $[N]$ with no $3$-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity. In the $3$-players exactly-$N$ problem the players need to decide whether $x+y+z=N$ for inputs $x,y,z$ and fixed $N$. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Despite the basic nature of this problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-$N$ problem. This is also the first significant example where algorithmic ideas in communication complexity bear fruit in additive combinatorics.
We describe algorithmic Number On the Forehead protocols that provide dense Ruzsa-Szemer{e}di graphs. One protocol leads to a simple and natural extension of the original construction of Ruzsa and Szemer{e}di. The graphs induced by this protocol have
$n$ vertices, $Omega(n^2/log n)$ edges, and are decomposable into $n^{1+O(1/log log n)}$ induced matchings. Another protocol is an explicit (and slightly simpler) version of the construction of Alon, Moitra and Sudakov, producing graphs with similar properties. We also generalize the above protocols to more than three players, in order to construct dense uniform hypergraphs in which every edge lies in a positive small number of simplices.
We present algorithms for testing if a $(0,1)$-matrix $M$ has Boolean/binary rank at most $d$, or is $epsilon$-far from Boolean/binary rank $d$ (i.e., at least an $epsilon$-fraction of the entries in $M$ must be modified so that it has rank at most $
d$). The query complexity of our testing algorithm for the Boolean rank is $tilde{O}left(d^4/ epsilon^6right)$. For the binary rank we present a testing algorithm whose query complexity is $O(2^{2d}/epsilon)$. Both algorithms are $1$-sided error algorithms that always accept $M$ if it has Boolean/binary rank at most $d$, and reject with probability at least $2/3$ if $M$ is $epsilon$-far from Boolean/binary rank $d$.
Let $A_{k,t}$ be the matrix that represents the adjacency matrix of the intersection bipartite graph of all subsets of size $t$ of ${1,2,...,k}$. We give constructions of large isolation sets in $A_{k,t}$, where, for a large enough $k$, our construct
ions are the best possible. We first prove that the largest identity submatrix in $A_{k,t}$ is of size $k-2t+2$. Then we provide constructions of isolations sets in $A_{k,t}$ for any $tgeq 2$, as follows: begin{itemize} item If $k = 2t+r$ and $0 leq r leq 2t-3$, there exists an isolation set of size $2r+3 = 2k-4t+3$. item If $k geq 4t-3$, there exists an isolation set of size $k$. end{itemize} The construction is maximal for $kgeq 4t-3$, since the Boolean rank of $A_{k,t}$ is $k$ in this case. As we prove, the construction is maximal also for $k = 2t, 2t+1$. Finally, we consider the problem of the maximal triangular isolation submatrix of $A_{k,t}$ that has ones in every entry on the main diagonal and below it, and zeros elsewhere. We give an optimal construction of such a submatrix of size $({2t choose t}-1) times ({2t choose t}-1)$, for any $t geq 1$ and a large enough $k$. This construction is tight, as there is a matching upper bound, which can be derived from a theorem of Frankl about skew matrices.
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
complementary to the bounds proved by Beame, David, Pitassi and Woelfel.
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$ do
es 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.
For integers $n$ and $k$, the density Hales-Jewett number $c_{n,k}$ is defined as the maximal size of a subset of $[k]^n$ that contains no combinatorial line. We show that for $k ge 3$ the density Hales-Jewett number $c_{n,k}$ is equal to the maximal
size of a cylinder intersection in the problem $Part_{n,k}$ of testing whether $k$ subsets of $[n]$ form a partition. It follows that the communication complexity, in the Number On the Forehead (NOF) model, of $Part_{n,k}$, is equal to the minimal size of a partition of $[k]^n$ into subsets that do not contain a combinatorial line. Thus, the bound in cite{chattopadhyay2007languages} on $Part_{n,k}$ using the Hales-Jewett theorem is in fact tight, and the density Hales-Jewett number can be thought of as a quantity in communication complexity. This gives a new angle to this well studied quantity. As a simple application we prove a lower bound on $c_{n,k}$, similar to the lower bound in cite{polymath2010moser} which is roughly $c_{n,k}/k^n ge exp(-O(log n)^{1/lceil log_2 krceil})$. This lower bound follows from a protocol for $Part_{n,k}$. It is interesting to better understand the communication complexity of $Part_{n,k}$ as this will also lead to the better understanding of the Hales-Jewett number. The main purpose of this note is to motivate this study.
We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where thr
ee players receive integer inputs and need to decide if their inputs sum to a given integer $n$. There is a considerable body of literature dealing with the same problem, where $(mathbb{N},+)$ is replaced by some other abelian group. Our work can be viewed as a far-reaching extension of this line of work. We show that the known lower bounds for that group-theoretic problem apply to all high dimensional permutations. We introduce new proof techniques that appeal to recent advances in Additive Combinatorics and Ramsey theory. We reveal new and unexpected connections between the NOF communication complexity of high dimensional permutations and a variety of well known and thoroughly studied problems in combinatorics. Previous protocols for Exactly-n all rely on the construction of large sets of integers without a 3-term arithmetic progression. No direct algorithmic protocol was previously known for the problem, and we provide the first such algorithm. This suggests new ways to significantly improve the CFL protocol. Many new open questions are presented throughout.
We prove upper bounds on deterministic communication complexity in terms of log of the rank and simp
