87 citations · 305 across the 39 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.CC2015
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size added to an \Erdos-\Renyi graph $G \si…
cs.CC2015
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…
cs.CC2015
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh Kothari
We prove that for every and predicate that supports a pairwise independent distribution, there exists an instance of the $\math…