
# Pravesh K. Kothari's homepage

Research Instructor
Department of Computer Science, Princeton University

## Brief Bio

I received my PhD from UT Austin advised by Adam Klivans, where I was partially supported by the Simons Award for Graduate Students in Theoretical Computer Science, and Bachelor's degree from IIT Kanpur advised by Surender Baswana.

In Fall 2019, I will join the Computer Science Department (and the diverse theory group) at CMU.

Venkatesan Guruswami and I are offering a joint postdoctoral fellowship starting Fall 2019 at the Computer Science Department, CMU. Check here for details.

## Service

PC Member APPROX/RANDOM 2018 , SODA 2019

## Contact

Email: "lastname" at cs dot princeton dot edu
Offices: Simonyi 007 (IAS, Default) and 413 (35, Olden Street, Princeton)

## Current Teaching

COS 597: Analytical Methods in Theoretical Computer Science
Course Webpage
Time/Venue : Mon-Wed 1:30:-2:50pm, Location: Friend 009 First Meeting: Feb 04.
Office Hours: Mon-Wed 3:00-4:00 pm (or by appointment)

## Research

I am broadly interested in theoretical computer science. My recent research has focused on investigating meta-algorithms such as the Sum of Squares method and Extended Formulations. Specifically, I have worked on
1) obtaining fast algorithms for problems arising in unsupervised machine learning, combinatorial optimization, quantum information and cryptography and, on the flip side,
2) obtaining general lower-bound techniques to gather evidence for tight computational vs statistical complexity trade-offs for some basic problems arising in average-case complexity.

## Selected Recent Papers (for all papers, see here)

Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture
With Boaz Barak and David Steurer
A generally accessible article on the recent proof of the 2-to-2 games conjecture that partly relies on this work.
Show Abstract

STOC 2018 (conference version to be merged with the paper below)

STOC 2018 (conference version to be merged with the paper above)

STOC 2018

Approximating Rectangles by Juntas and a Weakly Exponential Lower Bound for LP Relaxations of CSPs
With Raghu Meka and Prasad Raghavendra
STOC, 2017
Invited to SICOMP Special Issue for STOC 2017 Show Abstract

A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique
With Boaz Barak , Sam Hopkins , Jon Kelner , Ankur Moitra and Aaron Potechin
FOCS 2016. [Video- IAS CS/DM Seminar] [Boaz's WOT post]
Invited to SICOMP Special Issue for FOCS 2016 Show Abstract

SoS and Planted Clique: Tight Analysis of MPW Moments
at all Degrees and an Optimal Lower Bound at Degree Four

With Samuel B. Hopkins and Aaron Potechin
SODA 2016
Invited to the ACM Transactions on Algorithms, Special Issue for SODA 2016
(Conference version to be merged with Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program by Tselil Schramm and Prasad Raghavendra .) Show Abstract

Provable Submodular Minimization Using Wolfe's Algorithm
With Deeparnab Chakrabarty and Prateek Jain
NIPS 2014 (Oral Presentation) Show Abstract