65 citations · 177 across the 68 of their papers we have counts for
6 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…
Optimality of Correlated Sampling Strategies
Mohammad Bavarian, Badih Ghazi, Elad Haramaty +3
In the "correlated sampling" problem, two players are given probability distributions and , respectively, over the same finite set, with access to shared randomness. Without…
Communication Complexity of Permutation-Invariant Functions
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…
Communication with Contextual Uncertainty
Badih Ghazi, Ilan Komargodski, Pravesh Kothari +1
We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributiona…
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes
Badih Ghazi, Euiwoong Lee
Random (dv,dc)-regular LDPC codes are well-known to achieve the Shannon capacity of the binary symmetric channel (for sufficiently large dv and dc) under exponential time decoding.…