All reports by Author Pravesh Kothari:

__
TR19-106
| 12th August 2019
__

Noah Fleming, Pravesh Kothari, Toniann Pitassi#### Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 2

__
TR18-126
| 24th June 2018
__

Pravesh Kothari, Ruta Mehta#### Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium

__
TR18-077
| 23rd April 2018
__

Boaz Barak, Pravesh Kothari, David Steurer#### Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture

__
TR17-060
| 9th April 2017
__

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari#### Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

Revisions: 1

__
TR17-011
| 22nd January 2017
__

Boaz Barak, Pravesh Kothari, David Steurer#### Quantum entanglement, sum of squares, and the log rank conjecture

__
TR16-058
| 12th April 2016
__

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin#### A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

__
TR15-064
| 19th April 2015
__

Ilan Komargodski, Pravesh Kothari, Madhu Sudan#### Communication with Contextual Uncertainty

Revisions: 1

__
TR14-063
| 23rd April 2014
__

Adam Klivans, Pravesh Kothari#### Embedding Hard Learning Problems into Gaussian Space

__
TR13-129
| 17th September 2013
__

Adam Klivans, Pravesh Kothari, Igor Oliveira#### Constructing Hard Functions from Learning Algorithms

Revisions: 1

__
TR12-127
| 3rd October 2012
__

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari#### An Explicit VC-Theorem for Low-Degree Polynomials

__
TR11-090
| 2nd June 2011
__

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee#### Submodular Functions Are Noise Stable

Revisions: 2

Noah Fleming, Pravesh Kothari, Toniann Pitassi

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

Pravesh 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 the problem of computing equilibria that optimize a certain objective function and not to the (arguably more fundamental) task of finding \emph{any} equilibrium.

We present ... more >>>

Boaz Barak, Pravesh 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 about the soundness of a certain ``Grassmanian agreement tester''.

In this work, we show that the hypothesis of Dinur et al follows from a ...
more >>>

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>

Boaz Barak, Pravesh Kothari, David Steurer

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.

This yields a nearly tight ...
more >>>

Ilan Komargodski, Pravesh Kothari, Madhu Sudan

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 distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

Adam Klivans, Pravesh Kothari

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

Adam Klivans, Pravesh Kothari, Igor Oliveira

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari

Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal C}$ ... more >>>

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>