This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. more >>>

We prove an unexpected upper bound on a communication game proposed by Jeff Edmonds and Russell Impagliazzo as an approach for proving lower bounds for time-space tradeoffs for branching programs. Our result is based on a generalization of a construction of Erdos, Frankl and Rodl of a large 3-hypergraph with ... more >>>

We develop an analytic framework based on linear approximation and point out how a number of complexity related questions -- on circuit and communication complexity lower bounds, as well as pseudorandomness, learnability, and general combinatorics of Boolean functions -- fit neatly into this framework. This isolates the analytic content of ... more >>>

-- Scalar product estimates have so far been used in proving several unweighted threshold lower bounds. We show that if a basis set of Boolean functions satisfies certain weak stability conditions, then scalar product estimates yield lower bounds for the size of weighted thresholds of these basis functions. Stable basis ... more >>>

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k, connected by k links to form a linear array, compute a function f(x,y), for inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and y is only known to P_k; the intermediate processors P_1,...,P_{k-1} ... more >>>

We introduce a notion of a "real game" (a generalization of the Karchmer - Wigderson game), and "real communication complexity", and relate them to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols of small real communication complexity solving the monotone ... more >>>

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity ... more >>>

Using a notion of real communication complexity recently introduced by J. Krajicek, we prove a lower bound on the depth of monotone real circuits and the size of monotone real formulas for st-connectivity. This implies a super-polynomial speed-up of dag-like over tree-like Cutting Planes proofs. more >>>

We extend the tools for proving lower bounds for randomized branching programs by presenting a new technique for the read-once case which is applicable to a large class of functions. This technique fills the gap between simple methods only applicable for OBDDs and the well-known "rectangle technique" of Borodin, Razborov ... more >>>

We obtain improved lower bounds for a class of static and dynamic data structure problems that includes several problems of searching sorted lists as special cases. These lower bounds nearly match the upper bounds given by recent striking improvements in searching algorithms given by Fredman and Willard's fusion trees and ... more >>>

The superposition (or composition) problem is a problem of representation of a function $f$ by a superposition of "simpler" (in a different meanings) set $\Omega$ of functions. In terms of circuits theory this means a possibility of computing $f$ by a finite circuit with 1 fan-out gates $\Omega$ of functions. ... more >>>

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an ordinary branching program with the following restrictions: (i) along every consistent path at most $k$ variables are tested more than once, (ii) for each node $v$ on all paths from the source to $v$ the same set $X(v)\subseteq X$ of variables is tested, ... more >>>

One of the great challenges of complexity theory is the problem of analyzing the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. So far, this problem could be solved only for very few models of computation. For so-called partitioned binary decision diagrams, which are a ... more >>>

This paper deals with the number of monochromatic combinatorial rectangles required to approximate a Boolean function on a constant fraction of all inputs, where each rectangle may be defined with respect to its own partition of the input variables. The main result of the paper is that the number of ... more >>>

While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the ... more >>>

A fundamental question of complexity theory is the direct product question. Namely weather the assumption that a function $f$ is hard on average for some computational class (meaning that every algorithm from the class has small advantage over random guessing when computing $f$) entails that computing $f$ on $k$ independently ... more >>>

Normally, communication Complexity deals with how many bits Alice and Bob need to exchange to compute f(x,y) (Alice has x, Bob has y). We look at what happens if Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n and they want to compute f(x_1,y_1)... f(x_n,y_n). THis seems hard. We look at various ... more >>>

We show that recognizing the $K_3$-freeness and $K_4$-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols with exponentially many partitions and for nondeterministic (syntactic) read-$s$ times branching programs. The key ingradient is a generalization of a coloring lemma, due to Papadimitriou and Sipser, which says that for every ... more >>>

In model checking, program correctness on all inputs is verified by considering the transition system underlying a given program. In practice, the system can be intractably large. In property testing, a property of a single input is verified by looking at a small subset of that input. We join the ... more >>>

In the simultaneous message model, two parties holding $n$-bit integers $x,y$ send messages to a third party, the {\it referee}, enabling him to compute a boolean function $f(x,y)$. Buhrman et al [BCWW01] proved the remarkable result that, when $f$ is the equality function, the referee can solve this problem by ... more >>>

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ... more >>>

We consider the approximate nearest neighbour search problem on the Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that uses polynomial storage and word size $d^{O(1)}$ requires a worst case query time of $\Omega(\log\log d/\log\log\log d)$. The approximation factor may be as loose as $2^{\log^{1-\eta}d}$ for any ... more >>>

We study private computations in information-theoretical settings on networks that are not 2-connected. Non-2-connected networks are ``non-private'' in the sense that most functions cannot privately be computed on such networks. We relax the notion of privacy by introducing lossy private protocols, which generalize private protocols. We measure the information each ... more >>>

Communication complexity is concerned with the question: how much information do the participants of a communication system need to exchange in order to perform certain tasks? The minimum number of bits that must be communicated is the deterministic communication complexity of $f$. This complexity measure was introduced by Yao \cite{1} ... more >>>

Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the ... more >>>

We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided ... more >>>

We study the problem of non-interactive correlation distillation (NICD). Suppose Alice and Bob each has a string, denoted by $A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$, respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is independently drawn from a distribution $\noise$, known as the ``noise mode''. Alice and Bob wish to ``distill'' the correlation ... more >>>

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems for the classical as well as ... more >>>

A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents with common priors will never "agree to disagree": if their opinions about any topic are common knowledge, then those opinions must be equal. Economists have written numerous papers examining the assumptions behind this theorem. But two key questions ... more >>>

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

Alice and Bob want to know if two strings of length $n$ are almost equal. That is, do they differ on at most $a$ bits? Let $0\le a\le n-1$. We show that any deterministic protocol, as well as any error-free quantum protocol ($C^*$ version), for this problem requires at least ... more >>>

We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>>

A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance ... more >>>

This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later ... more >>>

A two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the ... more >>>

We consider computationally-efficient incentive-compatible mechanisms that use the VCG payment scheme, and study how well they can approximate the social welfare in auction settings. We obtain a $2$-approximation for multi-unit auctions, and show that this is best possible, even though from a purely computational perspective an FPTAS exists. For combinatorial ... more >>>

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate a value with distribution exactly D. Alice and Bob are allowed to share random bits generated ... more >>>

We consider the $k$-layer pointer jumping problem in the one-way multi-party number-on-the-forehead communication model. In this problem, the input is a layered directed graph with each vertex having outdegree $1$, shared amongst $k$ players: Player~$i$ knows all layers {\em except} the $i$th. The players must communicate, in the order $1,2,\ldots,k$, ... more >>>

The Earth Mover Distance (EMD) between two equal-size sets of points in R^d is defined to be the minimum cost of a bipartite matching between the two pointsets. It is a natural metric for comparing sets of features, and as such, it has received significant interest in computer vision. Motivated ... more >>>

A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. We investigate this question in various models of classical communication complexity. We define a new measure, the subdistribution bound, ... more >>>

We solve an open problem of Kushilevitz and Nisan (1997) in communication complexity. Let $R_{eps}(f)$ and $D^{mu}_{eps}(f)$ denote the randomized and $mu$-distributional communication complexities of f, respectively ($eps$ a small constant). Yao's well-known Minimax Principle states that R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }. Kushilevitz and Nisan (1997) ask whether this ... more >>>

We give the first exponential separation between quantum and classical multi-party communication complexity in the (non-interactive) one-way and simultaneous message passing settings. For every k, we demonstrate a relational communication problem between k parties that can be solved exactly by a quantum simultaneous message passing protocol of cost O(log n) ... more >>>

In this paper we study the one-way multi-party communication model, in which every party speaks exactly once in its turn. For every fixed $k$, we prove a tight lower bound of $\Omega{n^{1/(k-1)}}$ on the probabilistic communication complexity of pointer jumping in a $k$-layered tree, where the pointers of the $i$-th ... more >>>

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}: 1. Noise-resistant. A syntactically multilinear ... more >>>

In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the _multidimensional_ discrepancy method. We give an entirely different ... more >>>

The sign-rank of a real matrix M is the least rank of a matrix R in which every entry has the same sign as the corresponding entry of M. We determine the sign-rank of every matrix of the form M=[ D(|x AND y|) ]_{x,y}, where D:{0,1,...,n}->{-1,+1} is given and x ... more >>>

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier ... more >>>

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)). more >>>

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0 for all i,j. We obtain the first exponential lower bound on the sign-rank of a function in AC^0. Namely, let f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}). We show that the matrix [f(x,y)]_{x,y} has ... more >>>

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers ... more >>>

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... more >>>

The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to decide whether the Hamming distance between their $n$-bit input strings is large (i.e., at least $n/2 + \sqrt n$) ... more >>>

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

Does computing n copies of a function require n times the computational effort? In this work, we give the first non-trivial answer to this question for the model of randomized communication complexity. We show that: 1. Computing n copies of a function requires sqrt{n} times the communication. 2. For average ... more >>>

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>