23 citations · 30 across the 30 of their papers we have counts for
4 papers · 1 filter
When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
Pritish Kamath, Ravi Kumar, Pasin Manurangsi
We study two conjectures posed in the analysis of Boolean functions , in both of which, the Majority function plays a central role: the "Majority is…
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
Mika Göös, Pritish Kamath, Katerina Sotiraki +1
We study the search problem class defined as a modulo- analog of the well-known class introduced by Papadim…
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,…
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…