All reports by Author Anup Rao:

__
TR24-111
| 1st July 2024
__

Siddharth Iyer, Anup Rao#### An XOR Lemma for Deterministic Communication Complexity

__
TR23-194
| 5th December 2023
__

Siddharth Iyer, Anup Rao#### XOR Lemmas for Communication via Marginal Information

Revisions: 2

__
TR22-012
| 2nd February 2022
__

Anup Rao, Oscar Sprumont#### On List Decoding Transitive Codes From Random Errors

__
TR22-005
| 11th January 2022
__

Anup Rao#### Sunflowers: from soil to oil

Revisions: 3

__
TR21-102
| 13th July 2021
__

Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff#### Tight bounds on the Fourier growth of bounded functions on the hypercube

Revisions: 1

__
TR20-006
| 22nd January 2020
__

Anup Rao, Amir Yehudayoff#### The Communication Complexity of the Exact Gap-Hamming Problem

__
TR17-174
| 13th November 2017
__

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao#### On Expressing Majority as a Majority of Majorities

__
TR17-040
| 4th March 2017
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

__
TR16-167
| 1st November 2016
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

__
TR15-057
| 13th April 2015
__

Anup Rao, Makrand Sinha#### Simplified Separation of Information and Communication

Revisions: 3

__
TR15-055
| 13th April 2015
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### How to Compress Asymmetric Communication

__
TR15-039
| 16th March 2015
__

Anup Rao, Makrand Sinha#### On Parallelizing Streaming Algorithms

__
TR14-060
| 21st April 2014
__

Anup Rao, Amir Yehudayoff#### Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

__
TR14-020
| 18th February 2014
__

Pavel Hrubes, Anup Rao#### Circuits with Medium Fan-In

Revisions: 1

__
TR13-035
| 6th March 2013
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct product via round-preserving compression

Revisions: 1

__
TR12-143
| 5th November 2012
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct Products in Communication Complexity

Revisions: 2

__
TR11-160
| 1st December 2011
__

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff#### Restriction Access

__
TR10-166
| 5th November 2010
__

Mark Braverman, Anup Rao#### Towards Coding for Maximum Errors in Interactive Communication

__
TR10-083
| 13th May 2010
__

Mark Braverman, Anup Rao#### Efficient Communication Using Partial Information

Revisions: 1

__
TR10-035
| 7th March 2010
__

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff#### Pseudorandom Generators for Regular Branching Programs

__
TR09-044
| 6th May 2009
__

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao#### Direct Sums in Randomized Communication Complexity

__
TR08-015
| 23rd January 2008
__

Anup Rao#### Extractors for Low-Weight Affine Sources

__
TR08-013
| 16th January 2008
__

Anup Rao#### Parallel Repetition in Projection Games and a Concentration Bound

__
TR07-034
| 29th March 2007
__

Anup Rao#### An Exposition of Bourgain's 2-Source Extractor

__
TR05-106
| 26th September 2005
__

Anup Rao#### Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources

Revisions: 1

Siddharth Iyer, Anup Rao

We prove a lower bound on the communication complexity of computing the $n$-fold xor of an arbitrary function $f$, in terms of the communication complexity and rank of $f$. We prove that $D(f^{\oplus n}) \geq n \cdot \Big(\frac{\Omega(D(f))}{\log rk(f)} -\log rk(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the ... more >>>

Siddharth Iyer, Anup Rao

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

Anup Rao, Oscar Sprumont

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

Anup Rao

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.

more >>>Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff

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

Anup Rao, Amir Yehudayoff

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

more >>>Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

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

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

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

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

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

Anup Rao, Makrand Sinha

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

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

Anup Rao, Makrand Sinha

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

Anup Rao, Amir Yehudayoff

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.

Pavel Hrubes, Anup Rao

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

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

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

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

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

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

Mark Braverman, Anup Rao

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

Mark Braverman, Anup Rao

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

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

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

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

Anup Rao

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

Anup Rao

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

Anup Rao

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

Anup Rao

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