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

__
TR17-125
| 7th August 2017
__

Badih Ghazi, Pritish Kamath, Prasad Raghavendra#### Dimension Reduction for Polynomials over Gaussian Space and Applications

__
TR17-119
| 25th July 2017
__

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

__
TR17-081
| 2nd May 2017
__

Badih Ghazi, Madhu Sudan#### The Power of Shared Randomness in Uncertain Communication

__
TR16-194
| 4th December 2016
__

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan#### The Optimality of Correlated Sampling

Revisions: 1

__
TR16-176
| 9th November 2016
__

Venkata Gandikota, Badih Ghazi, Elena Grigorescu#### NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

__
TR16-104
| 14th July 2016
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Decidability of Non-Interactive Simulation of Joint Distributions

__
TR15-087
| 30th May 2015
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Communication Complexity of Permutation-Invariant Functions

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

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

Badih Ghazi, Pritish Kamath, Prasad Raghavendra

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

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

Badih Ghazi, Madhu Sudan

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

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

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

Venkata Gandikota, Badih Ghazi, Elena Grigorescu

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

Badih Ghazi, Pritish Kamath, Madhu Sudan

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

Badih Ghazi, Pritish Kamath, Madhu Sudan

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