Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Badih Ghazi:

TR18-150 | 27th August 2018
Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

TR17-125 | 7th August 2017
Badih Ghazi, Pritish Kamath, Prasad Raghavendra

Dimension Reduction for Polynomials over Gaussian Space and Applications

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>

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

TR17-081 | 2nd May 2017
Badih Ghazi, Madhu Sudan

The Power of Shared Randomness in Uncertain Communication

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

TR16-194 | 4th December 2016
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

The Optimality of Correlated Sampling

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

TR16-176 | 9th November 2016
Venkata Gandikota, Badih Ghazi, Elena Grigorescu

NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when ... more >>>

TR16-104 | 14th July 2016
Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-Interactive Simulation of Joint Distributions

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

TR15-087 | 30th May 2015
Badih Ghazi, Pritish Kamath, Madhu Sudan

Communication Complexity of Permutation-Invariant Functions

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>>

ISSN 1433-8092 | Imprint