All reports by Author Jaikumar Radhakrishnan:

__
TR22-185
| 29th December 2022
__

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal#### Randomized versus Deterministic Decision Tree Size

__
TR18-211
| 3rd December 2018
__

Kshitij Gajjar, Jaikumar Radhakrishnan#### Parametric Shortest Paths in Planar Graphs

Revisions: 1

__
TR16-103
| 6th July 2016
__

Jaikumar Radhakrishnan, Swagato Sanyal#### The zero-error randomized query complexity of the pointer function.

__
TR16-033
| 10th March 2016
__

Venkatesan Guruswami, Jaikumar Radhakrishnan#### Tight bounds for communication assisted agreement distillation

__
TR15-199
| 7th December 2015
__

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan#### Relaxed partition bound is quadratically tight for product distributions

__
TR14-074
| 14th May 2014
__

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra#### Topology matters in communication

__
TR06-151
| 10th December 2006
__

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan#### The communication complexity of correlation

__
TR03-017
| 27th March 2003
__

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener#### On Converting CNF to DNF

__
TR96-004
| 18th January 1996
__

Shiva Chaudhuri, Jaikumar Radhakrishnan#### Deterministic Restrictions in Circuit Complexity

Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal

A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most the cube of its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been ... more >>>

Kshitij Gajjar, Jaikumar Radhakrishnan

We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>

Jaikumar Radhakrishnan, Swagato Sanyal

The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson

\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently

been used to prove separation results among various measures of

complexity such as deterministic, randomized and quantum query

complexities, exact and approximate polynomial degrees, etc. In

particular, the widest possible (quadratic) separations between

deterministic and zero-error ...
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 >>>

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... 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 >>>

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

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

Shiva Chaudhuri, Jaikumar Radhakrishnan

We study the complexity of computing Boolean functions using AND, OR

and NOT gates. We show that a circuit of depth $d$ with $S$ gates can

be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where

$\epsilon(d) = 4^{-d}$) of its input values. This implies a

superlinear size lower bound ...
more >>>