87 citations · 305 across the 39 of their papers we have counts for
6 papers · 1 filter
SOS lower bounds with hard constraints: think global, act local
Pravesh Kothari, Ryan O'Donnell, Tselil Schramm
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in,…
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Pravesh K. Kothari, Ruta Mehta
Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to th…
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Boaz Barak, Pravesh K. Kothari, David Steurer
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis ab…
Efficient Algorithms for Outlier-Robust Regression
Adam Klivans, Pravesh K. Kothari, Raghu Meka
We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently la…
An Analysis of the t-SNE Algorithm for Data Visualization
Sanjeev Arora, Wei Hu, Pravesh K. Kothari
A first line of attack in exploratory data analysis is data visualization, i.e., generating a 2-dimensional representation of data that makes clusters of similar points visually id…
Surprise in Elections
Palash Dey, Pravesh K. Kothari, Swaprava Nath
Elections involving a very large voter population often lead to outcomes that surprise many. This is particularly important for the elections in which results affect the economy of…