Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMMUNICATION COMPLEXITY:
Reports tagged with Communication complexity:
TR94-001 | 12th December 1994
Noam Nisan, Avi Wigderson

#### On Rank vs. Communication Complexity

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

TR95-010 | 16th February 1995
Pavel Pudlak, Jiri Sgall

#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

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

TR96-030 | 31st March 1996
Meera Sitharam

#### Approximation from linear spaces and applications to complexity

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

TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

#### Stable basis families and complexity lower bounds

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

TR96-063 | 6th November 1996
Martin Dietzfelbinger

#### The Linear-Array Problem in Communication Complexity Resolved

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

TR97-015 | 21st April 1997
Jan Krajicek

#### Interpolation by a game

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

TR97-029 | 20th August 1997
Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

#### On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

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

TR97-032 | 11th July 1997
Jan Johannsen

#### Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes

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

TR98-018 | 27th March 1998
Martin Sauerhoff

#### Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

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

TR98-028 | 28th May 1998
Paul Beame, Faith Fich

#### On Searching Sorted Lists: A Near-Optimal Lower Bound

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

TR98-050 | 6th July 1998
Farid Ablayev, Svetlana Ablayeva

#### A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

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

TR99-044 | 30th September 1999
Farid Ablayev

#### On Complexity of Regular $(1,+k)$-Branching Programs

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

TR00-057 | 25th July 2000
Martin Sauerhoff

#### An Improved Hierarchy Result for Partitioned BDDs

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

TR00-058 | 1st August 2000
Martin Sauerhoff

#### Approximation of Boolean Functions by Combinatorial Rectangles

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

TR00-076 | 24th August 2000
Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

#### Measures of Nondeterminism in Finite Automata

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

TR01-009 | 5th January 2001
Ronen Shaltiel

#### Towards proving strong direct product theorems

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

TR01-019 | 2nd March 2001
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

#### The Communication Complexity of Enumeration, Elimination, and Selection

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

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

#### On Multi-Partition Communication Complexity of Triangle-Freeness

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

TR01-051 | 4th May 2001
Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

#### Probabilistic abstraction for model checking: An approach based on property testing

Revisions: 1

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

TR02-074 | 26th December 2002
Andrew Chi-Chih Yao

#### On the Power of Quantum Fingerprinting

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

TR03-047 | 22nd June 2003
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

#### Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

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

TR03-070 | 19th August 2003
Amit Chakrabarti, Oded Regev

#### An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

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

TR03-071 | 18th August 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

#### Privacy in Non-Private Environments

Revisions: 1

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

TR03-075 | 7th September 2003
Agostino Capponi

#### A tutorial on the Deterministic two-party Communication Complexity

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

TR03-082 | 22nd November 2003
Andris Ambainis, Ke Yang

#### Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

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

TR03-083 | 21st November 2003
Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

#### One-Way Communication Complexity of Symmetric Boolean Functions

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

TR03-085 | 28th November 2003
Ke Yang

#### On the (Im)possibility of Non-interactive Correlation Distillation

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

TR04-036 | 27th March 2004
Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

#### Exponential Separation of Quantum and Classical One-Way Communication Complexity

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

TR04-045 | 15th April 2004
Hartmut Klauck, Robert Spalek, Ronald de Wolf

#### Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

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

TR04-061 | 30th June 2004
Scott Aaronson

#### The Complexity of Agreement

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

TR04-062 | 28th July 2004
Stasys Jukna

#### A note on the P versus NP intersected with co-NP question in communication complexity

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

TR04-120 | 22nd November 2004
Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

#### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a

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

TR05-053 | 4th May 2005
Paul Beame, Nathan Segerlind

#### Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

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

TR05-117 | 17th September 2005
Piotr Indyk, David P. Woodruff

#### Polylogarithmic Private Approximations and Efficient Matching

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

TR05-129 | 30th October 2005
Scott Aaronson

#### QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

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

TR06-050 | 18th April 2006
Alexander Razborov, Sergey Yekhanin

#### An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

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

TR06-074 | 24th April 2006
Shahar Dobzinski, Noam Nisan

#### Approximations by Computationally-Efficient VCG-Based Mechanisms

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

TR06-086 | 25th July 2006
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

#### Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

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

TR06-087 | 25th July 2006
Iordanis Kerenidis, Ran Raz

#### The one-way communication complexity of the Boolean Hidden Matching Problem

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

TR06-106 | 18th August 2006
Scott Aaronson

#### The Learnability of Quantum States

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

TR06-117 | 31st August 2006
Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

#### Languages with Bounded Multiparty Communication Complexity

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

TR06-151 | 10th December 2006

#### The communication complexity of correlation

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

TR07-014 | 23rd January 2007
Amit Chakrabarti

#### Lower Bounds for Multi-Player Pointer Jumping

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

TR07-048 | 3rd April 2007
Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

#### Earth Mover Distance over High-Dimensional Spaces

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

TR07-064 | 19th June 2007
Rahul Jain, Hartmut Klauck, Ashwin Nayak

#### Direct Product Theorems for Communication Complexity via Subdistribution Bounds

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

TR07-072 | 2nd July 2007
Alexander A. Sherstov

#### Communication Complexity under Product and Nonproduct Distributions

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

TR07-074 | 7th August 2007
Dmitry Gavinsky, Pavel Pudlak

#### Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

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

TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

#### One-way multi-party communication lower bound for pointer jumping with applications

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

TR07-085 | 2nd September 2007
Ran Raz, Amir Yehudayoff

#### Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

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

TR07-100 | 25th September 2007
Alexander A. Sherstov

#### The Pattern Matrix Method for Lower Bounds on Quantum Communication

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

TR07-112 | 25th September 2007
Alexander A. Sherstov

#### Unbounded-Error Communication Complexity of Symmetric Functions

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

TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

#### Algebrization: A New Barrier in Complexity Theory

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

TR08-014 | 26th February 2008
Matei David

#### Separating NOF communication complexity classes RP and NP

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

TR08-016 | 26th February 2008
Alexander Razborov, Alexander A. Sherstov

#### The Sign-Rank of AC^0

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

TR08-024 | 26th February 2008
Paul Beame, Trinh Huynh

#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

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

TR08-057 | 14th May 2008
Alexander A. Sherstov

#### Communication Lower Bounds Using Dual Polynomials

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
surveys a new and growing body of work in communication
complexity that centers ... more >>>

TR08-061 | 11th June 2008
Paul Beame, Trinh Huynh

#### Multiparty Communication Complexity of AC^0

Revisions: 1

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

TR08-082 | 11th September 2008
Paul Beame, Trinh Huynh

#### Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 2

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

TR08-109 | 10th November 2008
Marc Kaplan, Sophie Laplante

#### Kolmogorov complexity and combinatorial methods in communication complexity

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

TR09-010 | 29th January 2009
Nikos Leonardos, Michael Saks

#### Lower bounds on the randomized communication complexity of read-once functions

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

TR09-015 | 19th February 2009
Joshua Brody, Amit Chakrabarti

#### A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

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

TR09-039 | 6th April 2009
Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

#### Polynomial Time with Restricted Use of Randomness

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

TR09-044 | 6th May 2009
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

#### Direct Sums in Randomized Communication Complexity

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

TR09-072 | 3rd September 2009
Paul Beame, Trinh Huynh

#### Hardness Amplification in Proof Complexity

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

TR10-076 | 18th April 2010
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

#### Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

Revisions: 1

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

TR10-086 | 17th May 2010
Henning Wunderlich

#### On a Theorem of Razborov

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

TR10-140 | 17th September 2010
Amit Chakrabarti, Oded Regev

#### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

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

TR10-143 | 19th September 2010
Bo'az Klartag, Oded Regev

#### Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

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

TR11-011 | 1st February 2011
Ming Lam Leung, Yang Li, Shengyu Zhang

#### Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

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

TR11-042 | 25th March 2011
Ankur Moitra

#### Efficiently Coding for Interactive Communication

Revisions: 1

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

TR11-062 | 18th April 2011
Amit Chakrabarti, Graham Cormode, Andrew McGregor

#### Robust Lower Bounds for Communication and Stream Computation

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

TR11-063 | 19th April 2011
Alexander A. Sherstov

#### The Communication Complexity of Gap Hamming Distance

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

TR11-106 | 6th August 2011
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

#### The Limits of Two-Party Differential Privacy

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

TR11-122 | 14th September 2011
Gillat Kol, Ran Raz

#### Competing Provers Protocols for Circuit Evaluation

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

TR11-123 | 15th September 2011
Mark Braverman

#### Interactive information complexity

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

TR11-152 | 12th November 2011
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 >>> TR11-155 | 22nd November 2011 Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen #### The NOF Multiparty Communication Complexity of Composed Functions 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 >>> TR12-128 | 21st September 2012 Nathanaël François, Frederic Magniez #### Streaming Complexity of Checking Priority Queues Revisions: 1 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 >>> TR12-153 | 9th November 2012 Joshua Brody, Amit Chakrabarti, Ranganath Kondapally #### Certifying Equality With Limited Interaction Revisions: 1 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 >>> TR12-166 | 25th November 2012 Elad Haramaty, Madhu Sudan #### Deterministic Compression with Uncertain Priors 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 >>> TR12-171 | 3rd December 2012 Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein #### From Information to Exact Communication 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 >>> TR12-177 | 19th December 2012 Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein #### Information lower bounds via self-reducibility 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 >>> TR13-001 | 2nd January 2013 Gillat Kol, Ran Raz #### Interactive Channel Capacity Revisions: 1 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 >>> TR13-002 | 31st December 2012 Venkatesan Guruswami, Krzysztof Onak #### Superlinear lower bounds for multipass graph processing Revisions: 3 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 >>> TR13-010 | 4th January 2013 Yang Liu, Shengyu Zhang #### Quantum and randomized communication complexity of XOR functions in the SMP model 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 >>> TR13-013 | 18th January 2013 Daniel Apon, Jonathan Katz, Alex Malozemoff #### One-Round Multi-Party Communication Complexity of Distinguishing Sums Revisions: 1 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 >>> TR13-015 | 18th January 2013 Iordanis Kerenidis, Mathieu Laurière, David Xiao #### New lower bounds for privacy in communication protocols 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 >>> TR13-020 | 2nd February 2013 Tom Gur, Ran Raz #### Arthur-Merlin Streaming Complexity 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 >>> TR13-021 | 5th February 2013 Kristoffer Arnsfelt Hansen, Vladimir Podolskii #### Polynomial threshold functions and Boolean threshold circuits 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 >>> TR13-035 | 6th March 2013 Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff #### Direct product via round-preserving compression Revisions: 1 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 >>> TR13-036 | 13th March 2013 Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev #### Lower Bounds for Testing Properties of Functions on Hypergrid Domains Revisions: 1 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 >>> TR13-044 | 25th March 2013 Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang #### Shared Randomness and Quantum Communication in the Multi-Party Model 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 >>> TR13-064 | 22nd April 2013 Anat Ganor, Ran Raz #### Space Pseudorandom Generators by Communication Complexity Lower Bounds Revisions: 1 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 >>> TR13-073 | 14th May 2013 Oded Goldreich #### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing Revisions: 2 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 >>> TR13-084 | 8th June 2013 Shachar Lovett #### Communication is bounded by root of rank Revisions: 1 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 >>> TR13-119 | 2nd September 2013 Emanuele Viola #### Challenges in computational lower bounds 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. more >>> TR13-130 | 17th September 2013 Mark Braverman, Ankit Garg #### Public vs private coin in bounded-round information Revisions: 1 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 >>> TR13-151 | 7th November 2013 Mark Bun, Justin Thaler #### Hardness Amplification and the Approximate Degree of Constant-Depth Circuits Revisions: 3 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 >>> TR13-189 | 21st December 2013 Periklis Papakonstantinou, Dominik Scheder, Hao Song #### Overlays and Limited Memory Communication Mode(l)s 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 >>> TR14-009 | 21st January 2014 Alexander A. Sherstov #### Breaking the Minsky-Papert Barrier for Constant-Depth Circuits 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 >>> TR14-049 | 11th April 2014 Anat Ganor, Gillat Kol, Ran Raz #### Exponential Separation of Information and Communication Revisions: 1 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 >>> TR14-074 | 14th May 2014 Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra #### Topology matters in communication 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 >>> TR14-113 | 27th August 2014 Anat Ganor, Gillat Kol, Ran Raz #### Exponential Separation of Information and Communication for Boolean Functions 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 >>> TR14-115 | 27th August 2014 Roei Tell #### Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees Revisions: 1 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 >>> TR14-119 | 15th September 2014 Mark Braverman, Jieming Mao #### Simulating Noisy Channel Interaction 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 >>> TR14-135 | 23rd October 2014 Noga Alon, Shay Moran, Amir Yehudayoff #### Sign rank, VC dimension and spectral gaps Revisions: 2 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 >>> TR14-153 | 14th November 2014 Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan #### Communication with Imperfectly Shared Randomness Revisions: 2 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 >>> TR15-023 | 10th February 2015 Mark Braverman, Jon Schneider #### Information complexity is computable 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 >>> TR15-055 | 13th April 2015 Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao #### How to Compress Asymmetric Communication 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 >>> TR15-060 | 14th April 2015 Omri Weinstein #### Information Complexity and the Quest for Interactive Compression Revisions: 1 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 >>> TR15-087 | 30th May 2015 Badih Ghazi, Pritish Kamath, Madhu Sudan #### Communication Complexity of Permutation-Invariant Functions 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 >>>

TR15-088 | 31st May 2015
Anat Ganor, Gillat Kol, Ran Raz

#### Exponential Separation of Communication and External Information

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

TR15-092 | 31st May 2015
Yael Tauman Kalai, Ilan Komargodski

#### Compressing Communication in Distributed Protocols

Revisions: 1

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

TR15-113 | 9th July 2015
Amit Chakrabarti, Tony Wirth

#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

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

TR15-126 | 27th July 2015
Jacob Steinhardt, Gregory Valiant, Stefan Wager

#### Memory, Communication, and Statistical Queries

Revisions: 1

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

TR15-139 | 25th August 2015
Eli Ben-Sasson, Gal Maor

#### Lower bound for communication complexity with no public randomness

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

TR15-147 | 8th September 2015
Alexander A. Sherstov

#### The Power of Asymmetry in Constant-Depth Circuits

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

TR15-156 | 21st September 2015
Tim Roughgarden

#### Communication Complexity (for Algorithm Designers)

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

TR15-168 | 18th October 2015
Gillat Kol

#### Interactive Compression for Product Distributions

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

TR15-209 | 29th December 2015
Eli Ben-Sasson, Gal Maor

#### On the information leakage of public-output protocols

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

TR16-033 | 10th March 2016

#### Tight bounds for communication assisted agreement distillation

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

TR16-044 | 21st March 2016
Kaave Hosseini, Shachar Lovett

#### Structure of protocols for XOR functions

Revisions: 1

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

TR16-072 | 4th May 2016
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

#### Separations in communication complexity using cheat sheets and information complexity

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

TR16-075 | 9th May 2016
Mark Bun, Justin Thaler

#### Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

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

TR16-081 | 20th May 2016
Alexander A. Sherstov

#### Compressing interactive communication under product distributions

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

TR16-086 | 29th May 2016
Noga Alon, Klim Efremenko, Benny Sudakov

#### Testing Equality in Communication Graphs

Revisions: 1

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

TR16-087 | 30th May 2016
Shalev Ben-David, Robin Kothari

#### Randomized query complexity of sabotaged and composed functions

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

TR16-095 | 7th June 2016

#### Small Error Versus Unbounded Error Protocols in the NOF Model

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

TR16-121 | 4th August 2016
Mark Bun, Justin Thaler

#### Approximate Degree and the Complexity of Depth Three Circuits

Revisions: 1

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

TR16-130 | 11th August 2016

#### Tight Network Topology Dependent Bounds on Rounds of Communication

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

TR16-140 | 9th September 2016
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

#### On SZK and PP

Revisions: 3

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

TR16-150 | 23rd September 2016
Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

#### Streaming Communication Protocols

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

TR16-151 | 26th September 2016
Amir Yehudayoff

#### Pointer chasing via triangular discrimination

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

TR17-002 | 6th January 2017
Frantisek Duris

#### Some notes on two lower bound methods for communication complexity

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

TR17-014 | 23rd January 2017

#### Composition and Simulation Theorems via Pseudo-random Properties

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

TR17-051 | 16th March 2017
Mark Bun, Justin Thaler

#### A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

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

TR17-079 | 1st May 2017
Alexander A. Sherstov, Pei Wu

#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

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

TR17-119 | 25th July 2017