Noam Nisan, Avi Wigderson

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.

Pavel Pudlak, Jiri Sgall

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

Meera Sitharam

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

Per Enflo, Meera Sitharam

--

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

Martin Dietzfelbinger

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

Jan Krajicek

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

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

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

Jan Johannsen

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.

Martin Sauerhoff

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

Paul Beame, Faith Fich

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

Farid Ablayev, Svetlana Ablayeva

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

Farid Ablayev

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

Martin Sauerhoff

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

Martin Sauerhoff

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

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

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

Ronen Shaltiel

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

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

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

Stasys Jukna, Georg Schnitger

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

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

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

Andrew Chi-Chih Yao

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

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

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

Amit Chakrabarti, Oded Regev

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

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

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

Agostino Capponi

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

Andris Ambainis, Ke Yang

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

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

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

Ke Yang

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

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

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

Hartmut Klauck, Robert Spalek, Ronald de Wolf

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

Scott Aaronson

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

Stasys Jukna

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

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

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

Paul Beame, Nathan Segerlind

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

Piotr Indyk, David P. Woodruff

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

Scott Aaronson

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

Alexander Razborov, Sergey Yekhanin

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

Shahar Dobzinski, Noam Nisan

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

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

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

Iordanis Kerenidis, Ran Raz

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

Scott Aaronson

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

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

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

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

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

Amit Chakrabarti

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

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

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

Rahul Jain, Hartmut Klauck, Ashwin Nayak

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

Alexander A. Sherstov

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

Dmitry Gavinsky, Pavel Pudlak

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

Emanuele Viola, Avi Wigderson

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

Ran Raz, Amir Yehudayoff

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Scott Aaronson, Avi Wigderson

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

Matei David

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 >>>Alexander Razborov, Alexander A. Sherstov

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

Paul Beame, Trinh Huynh

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

Alexander A. Sherstov

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

Paul Beame, Trinh Huynh

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

Paul Beame, Trinh Huynh

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

Marc Kaplan, Sophie Laplante

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

Nikos Leonardos, Michael Saks

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

Joshua Brody, Amit Chakrabarti

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

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

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

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

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

Paul Beame, Trinh Huynh

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

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that ... more >>>

Henning Wunderlich

In an unpublished Russian manuscript Razborov proved that a matrix family with high

rigidity over a finite field would yield a language outside the polynomial hierarchy

in communication complexity.

We present an alternative proof that strengthens the original result in several ways.

In particular, we replace rigidity by the strictly ...
more >>>

Amit Chakrabarti, Oded Regev

We prove an optimal $\Omega(n)$ lower bound on the randomized

communication complexity of the much-studied

Gap-Hamming-Distance problem. As a consequence, we

obtain essentially optimal multi-pass space lower bounds in the

data stream model for a number of fundamental problems, including

the estimation of frequency moments.

The Gap-Hamming-Distance problem is a ... more >>>

Bo'az Klartag, Oded Regev

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol

communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the ...
more >>>

Ming Lam Leung, Yang Li, Shengyu Zhang

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>

Ankur Moitra

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>>

Alexander A. Sherstov

In the gap Hamming distance problem, two parties must

determine whether their respective strings $x,y\in\{0,1\}^n$

are at Hamming distance less than $n/2-\sqrt n$ or greater

than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and

Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound

on the randomized communication ...
more >>>

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

Gillat Kol, Ran Raz

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

Mark Braverman

The primary goal of this paper is to define and study the interactive information complexity of functions. Let $f(x,y)$ be a function, and suppose Alice is given $x$ and Bob is given $y$. Informally, the interactive information complexity $IC(f)$ of $f$ is the least amount of information Alice and Bob ... more >>>

Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

Nathanaël François, Frederic Magniez

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>>

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

The \textsc{equality} problem is usually one's first encounter with

communication complexity and is one of the most fundamental problems in the

field. Although its deterministic and randomized communication complexity

were settled decades ago, we find several new things to say about the

problem by focusing on two subtle aspects. The ...
more >>>

Elad Haramaty, Madhu Sudan

We consider the task of compression of information when the source of the information and the destination do not agree on the prior, i.e., the distribution from which the information is being generated. This setting was considered previously by Kalai et al. (ICS 2011) who suggested that this was a ... more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We develop a new local characterization of the zero-error information complexity function for two party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: $IC(AND,0) = C_{\wedge}\approx 1.4923$ bits, and $IC^{ext}(AND,0) = \log_2 3 \approx 1.5839$ bits. This leads to ... more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform ... more >>>

Gillat Kol, Ran Raz

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate $\epsilon$, where ... more >>>

Venkatesan Guruswami, Krzysztof Onak

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

Yang Liu, Shengyu Zhang

Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the ... more >>>

Daniel Apon, Jonathan Katz, Alex Malozemoff

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

Iordanis Kerenidis, Mathieu Laurière, David Xiao

Communication complexity is a central model of computation introduced by Yao in 1979, where

two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed

function f with the least amount of communication. Recently people have revisited the question of the ...
more >>>

Tom Gur, Ran Raz

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

... more >>>Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

We obtain a strong direct product theorem for two-party bounded round communication complexity.

Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses

at most C bits of communication in computing f(x,y) when (x,y)~\mu.

Jain et al. [JPY12] have recently showed that if

more >>>

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.

Our lower bounds also apply to the more restricted setting ...
more >>>

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

Anat Ganor, Ran Raz

In 1989, Babai, Nisan and Szegedy [BNS92] gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was $2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>>

Oded Goldreich

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity

of property testing via communication complexity. They provided a restricted formulation of their methodology

(via ``simple combining operators'')

and also hinted towards a more general formulation, which we spell ...
more >>>

Shachar Lovett

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

Emanuele Viola

We draw two incomplete, biased maps of challenges in

computational complexity lower bounds. Our aim is to put

these challenges in perspective, and to present some

connections which do not seem widely known.

Mark Braverman, Ankit Garg

We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing $I$ bits of information, the transmission can be ... more >>>

Mark Bun, Justin Thaler

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>

Periklis Papakonstantinou, Dominik Scheder, Hao Song

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969

monograph, Minsky and Papert constructed a polynomial-size constant-depth

$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies ...
more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

Roei Tell

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

Mark Braverman, Jieming Mao

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

Noga Alon, Shay Moran, Amir Yehudayoff

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Mark Braverman, Jon Schneider

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $\alpha>0$, thus resolving an ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If $I^A$ denotes the number of bits of information revealed by the first party, $I^B$ denotes the information revealed by the second party, and $C$ is the number of bits of communication in ... more >>>

Omri Weinstein

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

Yael Tauman Kalai, Ilan Komargodski

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

Amit Chakrabarti, Tony Wirth

Set cover, over a universe of size $n$, may be modelled as a

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n \text{ poly}\{\log n, \log m\})$ space to process this ...
more >>>

Jacob Steinhardt, Gregory Valiant, Stefan Wager

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>

Eli Ben-Sasson, Gal Maor

We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was first stated in Yao's seminal paper [STOC 1979], but no full proof appears in the literature.

Our proof ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced

in the seminal work of Minsky and Papert (1969), this notion is central to

some of the strongest algorithmic and complexity-theoretic results for

more >>>

Tim Roughgarden

This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at

Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

Gillat Kol

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol ... more >>>

Eli Ben-Sasson, Gal Maor

In this paper three complexity measures are studied: (i) internal information, (ii) external information, and (iii) a measure called here "output information". Internal information (i) measures the counter-party privacy-loss inherent in a communication protocol. Similarly, the output information (iii) measures the reduction in input-privacy that is inherent when the output ... more >>>

Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

Kaave Hosseini, Shachar Lovett

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.

We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.

This relies on a novel technique ...
more >>>

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized

communication complexity for a ...
more >>>

Mark Bun, Justin Thaler

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

Alexander A. Sherstov

We study the problem of compressing interactive communication to its

information content $I$, defined as the amount of information that the

participants learn about each other's inputs. We focus on the case when

the participants' inputs are distributed independently and show how to

compress the communication to $O(I\log^{2}I)$ bits, with ...
more >>>

Noga Alon, Klim Efremenko, Benny Sudakov

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose

that on each vertex of the graph there is a player having an $n$-bit

string. Each player is allowed to communicate with its neighbors according

to an agreed communication protocol, and the players must decide,

deterministically, if their inputs ...
more >>>

Shalev Ben-David, Robin Kothari

We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] ... more >>>

Mark Bun, Justin Thaler

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the ... more >>>

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>>

Amir Yehudayoff

We prove an essentially sharp $\tilde\Omega(n/k)$ lower bound on the $k$-round distributional complexity of the $k$-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson's $\tilde \Omega(n/k^2)$ lower bound. A key part of the proof is using triangular discrimination instead ... more >>>

Frantisek Duris

We compare two methods for proving lower bounds on standard two-party model of communication complexity, the Rank method and Fooling set method. We present bounds on the number of functions $f(x,y)$, $x,y\in\{0,1\}^n$, with rank of size $k$ and fooling set of size at least k, $k\in [1,2^n]$. Using these bounds ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

Alexander A. Sherstov, Pei Wu

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

Badih Ghazi, T.S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with ... more >>>

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

We study the parameterized complexity of approximating the $k$-Dominating Set (domset) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal is to find a dominating set of size at most $F(k) \cdot k$ whenever the graph $G$ has a dominating ... more >>>

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>