65 citations · 177 across the 68 of their papers we have counts for
4 papers · 1 filter
Dimension Reduction for Polynomials over Gaussian Space and Applications
Badih Ghazi, Pritish Kamath, Prasad Raghavendra
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,…
Resource-Efficient Common Randomness and Secret-Key Schemes
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…
The Power of Shared Randomness in Uncertain Communication
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…
On the Power of Learning from -Wise Queries
Vitaly Feldman, Badih Ghazi
Several well-studied models of access to data samples, including statistical queries, local differential privacy and low-communication algorithms rely on queries that provide infor…