We initiate the study of the binary and Boolean rank of 0 , 1 matrices that have a small rank over the reals. The relationship between these three rank functions is an important open question, and here we prove that when the real rank d is a small constant, the gap between the real and the binary and Boolean rank is a small constant. We give tight upper and lower bounds on the Boolean and binary rank of matrices with real rank 1 ≤ d ≤ 4 , as well as determine the size of the largest isolation set in each case. Furthermore, we prove that for d = 3 , 4 , the circulant matrix defined by a row with d − 1 consecutive ones followed by d − 1 zeros, is the only matrix, up to a permutation of the rows and columns and the transpose operation, of size ( 2 d − 2 ) × ( 2 d − 2 ) with real rank d and Boolean and binary rank and isolation set of size 2 d − 2 , and this matrix achieves the maximal gap possible between the real and the binary and Boolean rank for these values of d . Our results can also be interpreted in other equivalent forms, such as finding the minimum number of bicliques needed to partition or cover the edges of a bipartite graph whose reduced adjacency matrix has real rank 1 ≤ d ≤ 4 . We use a combination of combinatorial and algebraic techniques combined with the assistance of a computer program.

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. Even though this is such a basic 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 improved protocol has also interesting consequences in additive combinatorics. As we explain below, it yields a higher lower bound on the possible density of corner-free sets in [N]×[N].

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 three 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.

Given a matrix A, we study how many epsilon-cubes are required to cover the convex hull of the columns of A. We show bounds on this cover number in terms of VC dimension and the gamma_2 norm and give algorithms for enumerating elements of a cover. This leads to algorithms for computing approximate Nash equilibria that unify and extend several previous results in the literature. Moreover, our approximation algorithms can be applied quite generally to a family of quadratic optimization problems that also includes finding the k-by-k combinatorial rectangle of a matrix. In particular, for this problem we give the first quasi-polynomial time additive approximation algorithm that works for any matrix A in [0,1]^{m x n}.

In the matrix completion problem the aim is to recover an unknown real matrix from a subset of its entries. This problem comes up in many application areas, and has received a great deal of attention in the context of the netflix prize. A central approach to this problem is to output a matrix of lowest possible complexity (e.g. rank or trace norm) that agrees with the partially specified matrix. The performance of this approach under the assumption that the revealed entries are sampled randomly has received considerable attention. In practice, often the set of revealed entries is not chosen at random and these results do not apply. We are therefore left with no guarantees on the performance of the algorithm we are using. We present a means to obtain performance guarantees with respect to any set of initial observations. The first step remains the same: find a matrix of lowest possible complexity that agrees with the partially specified matrix. We give a new way to interpret the output of this algorithm by next finding a probability distribution over the non-revealed entries with respect to which a bound on the generalization error can be proven. The more complex the set of revealed entries according to a certain measure, the better the bound on the generalization error.

We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including communication complexity, combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the ε-rank and use them for algorithmic applications. Our main algorithmic results are (a) polynomial-time additive approximation schemes for Nash equilibria for 2-player games when the payoff matrices are positive semidefinite or have logarithmic rank and (b) an additive PTAS for the densest subgraph problem for similar classes of weighted graphs. We use combinatorial, geometric and spectral techniques; our main new tool is an algorithm for efficiently covering a convex body with translates of another convex body.

One of the strongest techniques available for showing lower bounds on bounded-error communication complexity is the logarithm of the approximation rank of the communication matrix-the minimum rank of a matrix which is close to the communication matrix in lscrinfinnorm. Krause showed that the logarithm of approximation rank is a lower bound in the randomized case, and later Buhrman and de Wolf showed it could also be used for quantum communication complexity. As a lower bound technique, approximation rank has two main drawbacks: it is difficult to compute, and it is not known to lower bound the model of quantum communication complexity with entanglement. Linial and Shraibman recently introduced a quantity, called gamma2alpha, to quantum communication complexity, showing that it can be used to lower bound communication in the model with shared entanglement. Here alpha is a measure of approximation which is related to the allowable error probability of the protocol. This quantity 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, rkalpha. We show that in fact log gamma2alpha(A) and log rkalpha(A) agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximation rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

We show that disjointness requires randomized communication Omega(n1/(k+1)/22k) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega (log n/k-1). By results of Beame, Pitassi, and Segerlind, this implies 2nOmega(1)lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial lower bounds on the size of a broad class of tree-like proof systems whose terms are degree-d polynomial inequalities for d=log log n-O(log log log n). To prove our bound, we develop a new technique for showing lower bounds in the number-on-the-forehead model which is based on the norm induced by cylinder intersections. This bound naturally extends the linear program bound for rank useful in the two-party case to the case of more than two parties, where the fundamental concept of monochromatic rectangles is replaced by monochromatic cylinder intersections. Previously, the only general method known for showing lower bounds in the unrestricted number-on-the-forehead model was the discrepancy method, which is limited to bounds of size O(log n) for disjointness. To analyze the bound given by our new technique for the disjointness function, we build on an elegant framework developed by Sherstov in the two-party case and Chattopadhyay in the multi-party case which relates polynomial degree to communication complexity. Using this framework we are able to obtain bounds for any tensor of the form F(x1,...,xk)=f(x1Lambda...Lambdaxk) where f is a function which only depends on the number of ones in the input.

Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).

This paper has two main focal points. We first consider an important class of machine learning algorithms - large margin classifiers, such as support vector machines. The notion of margin complexity quantifies the extent to which a given class of functions can be learned by large margin classifiers. We prove that up to a small multiplicative constant, margin complexity is equal to the inverse of discrepancy. This establishes a strong tie between seemingly very different notions from two distinct areas. In the same way that matrix rigidity is related to rank, we introduce the notion of rigidity of margin complexity. We prove that sign matrices with small margin complexity rigidity are very rare. This leads to the question of proving lower bounds on the rigidity of margin complexity. Quite surprisingly, this question turns out to be closely related to basic open problems in communication complexity, e.g., whether PSPACE can be separated from the polynomial hierarchy in communication complexity. There are numerous known relations between the field of learning theory and that of communication complexity, as one might expect since communication is an inherent aspect of learning. The results of this paper constitute another link in this rich web of relations. This link has already proved significant as it was used in the solution of a few open problems in communication complexity.

We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. This approach gives us access toseveral powerful tools from this area such as normed spaces duality and Grothendiek's inequality. This extends the arsenal of methods for deriving lower bounds in communication complexity. As we show,our method subsumes most of the previously known general approaches to lower bounds on communication complexity. Moreover, we extend all (but one) of these lower bounds to the realm of quantum communication complexity with entanglement. Our results also shed some light on the question how much communication can be saved by using entanglement.It is known that entanglement can save one of every two qubits, and examples for which this is tight are also known. It follows from our results that this bound on the saving in communication is tight almost always.