We define the marginal information of a communication protocol, and use it to prove XOR lemmas for communication complexity. We show that if every $C$-bit protocol has bounded advantage for computing a Boolean function $f$, then every $\tilde \Omega(C \sqrt{n})$-bit protocol has advantage $\exp(-\Omega(n))$ for computing the $n$-fold xor $f^{\oplus ... more >>>

We study the error resilience of transitive linear codes over $F_2$. We give tight bounds on the weight distribution of every such code $C$, and we show how these bounds can be used to infer bounds on the error rates that $C$ can tolerate on the binary symmetric channel. Using ... more >>>

A \emph{sunflower} is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erd\H{o}s and Rado, made by Alweiss, Lovett, Wu and Zhang.

We give tight bounds on the degree $\ell$ homogenous parts $f_\ell$ of a bounded function $f$ on the cube. We show that if $f: \{\pm 1\}^n \rightarrow [-1,1]$ has degree $d$, then $\| f_\ell \|_\infty$ is bounded by $d^\ell/\ell!$, and $\| \hat{f}_\ell \|_1$ is bounded by $d^\ell e^{{\ell+1 \choose 2}} ... more >>>

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

If $k<n$, can one express the majority of $n$ bits as the majority of at most $k$ majorities, each of at most $k$ bits? We prove that such an expression is possible only if $k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>>

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

We give an example of a boolean function whose information complexity is exponentially
smaller than its communication complexity. Our result simplifies recent work of Ganor, Kol and
Raz (FOCS'14, STOC'15).

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

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof
showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being depth ... more >>>

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

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(?,f,C) denote the maximum success probability of a 2-party communication protocol for computing f(x,y) with C bits of communication, when the inputs (x,y) are ... more >>>

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

We show that it is possible to encode any communication protocol
between two parties so that the protocol succeeds even if a $(1/4 -
\epsilon)$ fraction of all symbols transmitted by the parties are
corrupted adversarially, at a cost of increasing the communication in
the protocol by a constant factor ... more >>>

We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver.

We ... more >>>

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.
A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.
For every width $d$ and length $n$,
our pseudorandom generator uses a seed of length $O((\log d + \log\log n ... more >>>

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... more >>>

In a two player game, a referee asks two cooperating players (who are
not allowed to communicate) questions sampled from some distribution
and decides whether they win or not based on some predicate of the
questions and their answers. The parallel repetition of the game is
the game in which ... more >>>

A construction of Bourgain gave the first 2-source
extractor to break the min-entropy rate 1/2 barrier. In this note,
we write an exposition of his result, giving a high level way to view
his extractor construction.

We also include a proof of a generalization of Vazirani's XOR lemma
that seems ... more >>>

We consider the problem of bit extraction from independent sources. We
construct an extractor that can extract from a constant number of
independent sources of length $n$, each of which have min-entropy
$n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our
constructions are different from recent extractor constructions
more >>>