Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR15-169 | 23rd October 2015
Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

Randomized Communication vs. Partition Number

Revisions: 1

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

TR15-167 | 15th October 2015
Mika Göös, T.S. Jayram

A Composition Theorem for Conical Juntas

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

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

ISSN 1433-8092 | Imprint