All reports by Author T.S. Jayram:

__
TR17-119
| 25th July 2017
__

Badih Ghazi, T.S. Jayram#### Resource-Efficient Common Randomness and Secret-Key Schemes

__
TR15-169
| 23rd October 2015
__

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson#### Randomized Communication vs. Partition Number

Revisions: 1

__
TR15-167
| 15th October 2015
__

Mika Göös, T.S. Jayram#### A Composition Theorem for Conical Juntas

__
TR04-036
| 27th March 2004
__

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis#### Exponential Separation of Quantum and Classical One-Way Communication Complexity

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

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>Mika Göös, T.S. Jayram

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

$\bullet~$ $\textbf{AND-OR trees}$: We show a near-optimal $\tilde{\Omega}(n^{0.753...})$ randomised communication lower bound ... 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 >>>