<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!-- saved from url=(0041)https://www.math.lsu.edu/~svanzwam/ -->
<html lang="en" xml:lang="en" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<!-- Start of StatCounter Code for WebStarts -->
<script async="" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/MathJax.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/javascript">
var sc_project = 7475502;
var sc_invisible = 1;
var sc_security = "5aa535fa";
var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www.");
document.write("<sc" + "ript type='text/javascript' src='" + scJsHost + "statcounter.com/counter/counter.js'></" + "script>");
</script>
<script async="" src="https://www.googletagmanager.com/gtag/js?id=UA-26545501-1">
</script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'UA-26545501-1');
</script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.4.4/jquery.min.js" type="text/javascript">
</script>
<script type="text/javascript">
function toggleDiv(divId) {
$("#" + divId).toggle();
}
</script>
<!--end toggle text script code -->
<title>
Pravesh K. Kothari
</title>
<link href="./MyWeb/docs/style.css" media="screen" rel="stylesheet" type="text/css">
</head>
<body>
\(
\newcommand{\pmset}{ \{\pm 1\}}
\newcommand{\on}{\{\pm 1\}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\R}{\mathbb{R}}
\)
<div class="container">
<div class="header">
<h1>
Pravesh K. Kothari
</h1>
</div>
<div class="left">
<div class="nav">
<div class="textbox">
home
</div>
</div>
<div class="nav">
<a class="nav" href="./MyWeb/docs/CV.pdf">
CV
</a>
</div>
<div class="nav">
<a class="nav" href="./papers.html">
research
</a>
</div>
<div class="nav">
<a class="nav" href="./teaching.html">
teaching
</a>
</div>
<div style="float: left; margin-left: 20px; margin-top: 50px; margin-bottom: 60px; border: 2px">
<a href="https://www.nowpublishers.com/article/Details/TCS-086">
<img alt="picture" src="bookpicture.png">
</a>
</div>
</div>
<div class="content">
<div style="float: right; margin-left: 20px; margin-top: 0px; margin-bottom: 60px; border: 2px">
<img alt="picture" src="picturen.jpg" style="width:300px;height:px;">
</div>
<b>
Assistant Professor (Jan 2024-)
</b>
<br>
<a href="http://www.cs.princeton.edu">
Computer Science Department, Princeton
</a>
<br>
kothari AT cs.princeton.edu
<br>
<br>
<i>
In Spring'24, I am also affiliated with the
<a href="https://www.ias.edu/math">
School of Math
</a>
at the
<a href="https://www.ias.edu">
IAS
</a>
.
<br>
<br>
<b>
Brief Bio:
</b>
I got my PhD in CS from UT Austin in Summer 2016 with a dissertation on
<a href="https://repositories.lib.utexas.edu/items/6daacbaa-f71d-4365-9ad6-254d013649e0">
<i>
Strong Lower Bounds on Generic Convex Relaxations
</i>
</a>
. I was a postdoctoral research instructor at the IAS and Princeton CS from 2016-19 and an Assistant Professor at CSD at CMU from 2019-2023.
<!-- <font color="red">Aayush Jain and I are currently looking for a <a href="theory-postdoc.html">postdoc</a> (soft deadline Jan 31).</font> -->
<h2>
Upcoming Talks/Events
</h2>
<p>
<a href="">
Cargèse Workshop on Combinatorial Optimization
</a>
[Sep'24]
<br>
<a href="">
Workshop on Algorithms for Learning and Economics
</a>
[June'24]
<br>
<a href="">
Oberwolfach Complexity Meeting
</a>
[June'24]
<br>
<a href="">
Milan Theory Workshop
</a>
[May'24]
<br>
<a href="">
Oberwolfach Meeting on Proof Complexity and Beyond
</a>
[March'24]
<br>
<a href="">
School of Math Colloquium at the Institute for Advanced Study
</a>
[March 24]
<br>
<a href="">
EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization
</a>
[Feb'24]
<br>
<a href="">
Banff Workshop on Computational Complexity of Statistical Inference
</a>
[Feb 24]
<br>
<a href="">
Rutgers Theory Seminar
</a>
[Feb 24]
<br>
<a href="">
MIT Statistics and Stochastics Seminar
</a>
[Feb 24]
<br>
<a href="">
MIT-Harvard Reading Group
</a>
[Feb 24]
<br>
<a href="">
Harvard Theory Seminar
</a>
[Feb 24]
<br>
<a href="">
CSDM Seminar at the Institute for Advanced Study
</a>
[Feb 24]
<br>
<a href="">
Simons Symposium on Math of Computing According to Lattices
</a>
[Aug'23]
<br>
<a href="">
Santa Fe Workshop on Connecting Physics, Geometry, and Algebraic Hardness
</a>
[July'23]
<br>
<a href="">
SIAM Conference on Optimization
</a>
[May'23]
<br>
<a href="">
Tel Aviv University Theory Fest, Plenary Session
</a>
[Dec 22]
<br>
<!--
<a href="">Workshop on Algorithms Under Uncertainty, Chennai</a> [Dec 22]<br>
<a href="">Simons Institute Reunion Workshop on CCSI</a> [Dec 22]<br>
<a href="https://pcts.princeton.edu/events/2022/positivity"> Princeton Center for Theoretical Science Workshop on Positivity </a>[Nov 22]<br>
<a href="http://www.crm.umontreal.ca/2022/Tensors22/index_e.php "> CRM Workshop on Tensors in Algebraic Geometry </a> [Nov'22]<br>
<a href="https://sigact.org/tcswomen/professional-mentoring-panel-at-focs-2022/">Professional Mentoring Panel at FOCS 2022</a> [Nov'22] <br>
<a href="https://www.cs.utexas.edu/theory-seminar">UT Theory Seminar </a> [Oct' 22]<br>
<a href="https://acoi.ics.uci.edu/seminar-series/">ACO Seminar UC Irvine </a> [Oct'22]<br>
<a href="">Berkeley Theory Lunch </a> [Oct'22]<br>
<a href="">Stanford Theory Lunch</a> [Oct'22]<br>
<a href="">Santa Fe Working Group on Foundations of Machine Learning</a> [Jul'22]<br>
<a href=""> Fields Workshop on Differential Privacy</i> </a> [Jul'22]<br>
<a href="https://suri.epfl.ch/#program"> EPFL Workshop on <i>Learning: Optimization and Stochastics</i> </a> [Jun'22]<br>
<a href=""> Dagstuhl Worshop on <i>The Constraint Satisfaction Problem: Complexity and Approximability</i> </a> [May'22]<br>
<a href="">MIT Theory of Computation Colloquium</a> [April 26, '22]<br>
<a href="">Harvard Theory Seminar</a> [April 20, '22]<br>
<!-- <a href="">IAS CS/DM Seminar</a> [Feb 28, '22]<br>
<a href="">"Three Lectures on High-Dimensional Statistical Estimation via Sum-of-Squares", ARC-ACO Lecture Series, Georgia Tech</a> [15-19 Feb'22]<br> -->
<!--
<a href="">FOCS Workshop on Proof Complexity</a> [7-8 Feb'22]<br>
<a href="https://simons.berkeley.edu/talks/smoothed-csp-refutation-easy-random-both-efficient-algorithms-and-certificates"> Simons Workshop on Rigorous Evidence for Information-Computation Trade-offs</a> [Sep 21]<br>
<a href="https://sites.google.com/view/tcsplus/welcome/past-talks?authuser=0#h.o1qhq3db56i4"> TCS Plus Seminar <a href="https://sites.google.com/view/tcsplus/welcome/past-talks?authuser=0#h.o1qhq3db56i4" style="color:red;"> Robust Learning of Mixture of $k$ Arbitrary Gaussians</a> [June 21] </a> -->
<!-- <br>
<a href="http://poema-network.eu/"> POEMA Workshop on Polynomial Optimization [Feb 21] </a><br>
<a href="https://simons.berkeley.edu/talks/recent-progress-algorithmic-robust-statistics-sum-squares-method"> Simons Workshop on High Dimensional Learning and Testing [Dec 20] </a><br>
<a href="https://csp-seminar.org/talks/pravesh-kothari/"> Online CSP Seminar [Nov 20] </a><br>
<a href="https://simons.berkeley.edu/talks/sum-squares-approach-clustering-non-spherical-gaussian-mixtures"> Simons Workshop on Computational Phase Transitions [Sep 20] </a><br> -->
<!-- <a href="https://www.math.tamu.edu/seminars/randomtensors/index.php?print&id=68&semester=2020B"> TAMU High Dimensional Probability Seminar [Aug 20] </a><br>
<a href="https://icerm.brown.edu/topical_workshops/tw-20-srag/#workshopschedule"> ICERM Workshop on Symmetry, Randomness, and Computations in Real Algebraic Geometry[Aug 20] </a><br>
<a href="https://polyalg.csa.iisc.ac.in/?talk=20200608_PraveshKothari"> Polynomials as an Algorithmic Paradigm, PolyAlg Seminar [June 20]</a><br>
<a href="">Workshop on Extension Complexity and Lifting Theorems, FSTTCS [Dec 2019]</a><br>
<a href=""> International Conference on Continuous Optimization, Berlin [Aug 2019] </a><br>
<a href=""> SIAM Conference in Applied Algebraic Geometry, Bern [Jul 2019] <br>
<a href=""> BIRS Workshop on Algebraic Techniques in Computational Complexity, Banff [July 2019] </a><br> -->
<!-- <a href=""> ITCS 2019, San Diego [Jan 2019] </a><br>
<a href=""> UCLA Theory Seminar [Jan 2019] </a><br>
<a href="">University of Chicago Theory Seminar [Dec 2018] </a> <br>
<a href="https://www.mfo.de/occasion/1846/www_view">Oberwolfach Workshop on Complexity Theory, Oberwolfach, Germany [Nov 2018] </a><br>
<a href="https://icerm.brown.edu/programs/sp-f18/w2/">ICERM Workshop on Real Algebraic Geometry and Optimization, Providence, RI [Oct'18] </a> <br>
<a href="https://www.birs.ca/events/2018/5-day-workshops/18w5197"> Workshop on Analytic Techniques in Theoretical Computer Science, Oaxaca, Mexico [Aug 12-17] </a><br>
<a href="http://www.iliasdiakonikolas.org/tti-robust.html"> TTI-Chicago Summer Workshop on High-Dimensional Robust Statistics [Aug 2018]</a> <br>
<a href=""> NYU Theory Seminar [May 2018] </a><br>
<a href=""> IAS Computer Science and Discrete Mathematics Seminar, Princeton [Feb 2018] </a> <br>
<a href="https://projects.csail.mit.edu/itcs/"> ITCS 2018, Cambridge, MA [Jan 2018] </a> <br>
<a href="https://www.icts.res.in/discussion-meeting/wao2018">ICTS Workshop on Algorithms and Optimization, Bangalore, India [Jan'18]</a> -->
<!-- <br>
<a href="https://toc.csail.mit.edu/node/1150">MIT Theory of Computation Colloquium [Dec 2017] </a><br>
<a href="https://simons.berkeley.edu/workshops/optimization2017-3">Simons Workshop on Hierarchies, Extended Formulations and Matrix-Analytic Techniques, Berkeley, CA [Nov 2017] </a> <br>
<a href=""> Columbia Theory Seminar [Oct 27] </a><br>
<a href="https://www.cs.princeton.edu/courses/archive/fall17/cos597A/"> Guest Lecture: Seminar on New Directions in Theoretical Machine Learning, Princeton CS [Oct 2017] </a> <br>
<a href="https://www.mfo.de/occasion/1733">Oberwolfach Workshop on Proof Complexity and Beyond, Oberwolfach, Germany [Aug 2017] </a> <br> -->
</p>
<h2>
Research Interests
</h2>
<p>
Algorithms and computational thresholds for
<i>
average-case
</i>
computational problems, random matrices, extremal combinatorics
<br>
My work is generously supported by an
<b>
<a href="https://www.nsf.gov/awardsearch/showAward?AWD_ID=2047933">
NSF CAREER Award
</a>
</b>
(2021), an Alfred P.
<b>
<a href="https://sloan.org/fellowships/2022-Fellows">
Sloan Fellowship
</a>
</b>
(2022), a
<b>
<a href="https://research.google/outreach/research-scholar-program/recipients/?category=2021">
Google Research Scholar Award
</a>
</b>
(2021), and an
<b>
<a href="https://www.nsf.gov/awardsearch/showAward?AWD_ID=2211971&HistoricalAwards=false">
NSF Medium
</a>
Grant
</b>
for collaborative research with
<a href="https://people.eecs.berkeley.edu/~venkatg/">
Venkat Guruswami
</a>
(2022).
</p>
<h2>
Research Highlights
</h2>
<p>
Complete list of my
<u>
<a href="papers.html">
papers
</a>
</u>
. Some highlights/resources:
</p>
<ul>
<li>
<b>
The Sum-of-Squares Method
</b>
and Algorithm Design via Connections to Proof Complexity
<ul>
<li>
Monograph on
<u>
<b>
<a href="https://eccc.weizmann.ac.il/report/2019/106/">
Semialgebraic Proofs and Efficient Algorithm Design
</a>
</b>
</u>
.
</li>
<li>
<u>
<b>
<a href="https://www.diderot.one/courses/58">
Fall'21 CMU Lecture notes
</a>
</b>
</u>
and
<b>
<a href="https://www.youtube.com/watch?v=tMWZw9f3J48&ab_channel=PraveshKothari">
videos
</a>
</b>
.
</li>
</ul>
</li>
<li>
Sum-of-Squares Framework for
<b>
Efficient Robust Statistics
</b>
<ul>
<li>
Resolving the robust learnability of mixtures of high-dimensional Gaussians (in the sequence
<a href="https://arxiv.org/abs/1711.07465">
[1]
</a>
,
<a href="https://arxiv.org/abs/2005.02970">
[2]
</a>
, and
<a href="https://arxiv.org/abs/2012.02119">
[3]
</a>
) (see
<a href="https://cacm.acm.org/magazines/2012/2/145410-technical-perspective-modeling-high-dimensional-data/fulltext">
2012 CACM Tech Perspective
</a>
and
<a href="https://simons.berkeley.edu/news/research-vignette-foundations-data-science">
Simons Research Vignette
</a>
for history and context).
</li>
<li>
Toolkit for basic estimation:
<a href="https://arxiv.org/abs/1803.03241">
regression
</a>
,
<a href="https://arxiv.org/abs/1711.11581">
moment estimation
</a>
, and
<a href="https://arxiv.org/abs/2011.06585">
sparse recovery
</a>
.
</li>
<li>
Efficient estimation in the presence of majority outliers (in the sequence
<a href="https://arxiv.org/abs/1905.05679">
[1]
</a>
,
<a href="https://arxiv.org/abs/2002.05139">
[2]
</a>
, and
<a href="https://arxiv.org/abs/2206.10942">
[3]
</a>
).
</li>
<li>
Overview
<u>
<a href="https://simons.berkeley.edu/talks/recent-progress-algorithmic-robust-statistics-sum-squares-method">
<b>
talk
</b>
</a>
</u>
with open questions.
</li>
</ul>
</li>
<li>
<b>
The
<i>
Kikuchi
</i>
Matrix Method
</b>
and Applications
<ul>
<li>
A new class of spectral methods for extremal combinatorics. Applications so far: refuting and solving
<a href="">
smoothed SAT (CSPs)
</a>
, settling
<a href="https://arxiv.org/abs/2109.04415">
Feige's conjecture
</a>
on extremal girth of hypergraphs, and improved lower bounds on
<a href="https://eccc.weizmann.ac.il/report/2022/101">
locally decodable codes
</a>
, and an
<a href="https://arxiv.org/abs/2311.00558">
exponential lower bound
</a>
on three-query linear locally correctable codes.
</li>
<li>
Some
<a href="https://www.youtube.com/watch?v=NFbQESM3zKg&ab_channel=TAUVOD">
recent
</a>
<a href="https://www.youtube.com/watch?v=eQF74Ixb7oo">
talks
</a>
.
</li>
</ul>
</li>
<li>
Efficient Algorithms approaching the conjectured threshold for
<b>
Semirandom and Smoothed Optimization
</b>
<ul>
<li>
Refuting/solving Smoothed SAT and other CSPs(in the sequence
<a href="https://arxiv.org/abs/2009.08032">
[1]
</a>
,
<a href="https://arxiv.org/abs/2109.04415">
[2]
</a>
,
<a href="https://arxiv.org/abs/2302.12289">
[3]
</a>
).
</li>
<li>
Finding
<a href="https://arxiv.org/abs/2212.05619">
planted cliques
</a>
in Feige-Kilian Semirandom Model (see
<a href="https://www.wisdom.weizmann.ac.il/~feige/mypapers/bwca.pdf">
this
</a>
book chapter and
<a href="https://arxiv.org/abs/1704.05120">
this
</a>
paper for history and context on the question).
</li>
<li>
Breaking security of
<a href="https://eccc.weizmann.ac.il/report/2017/060/download">
certain
</a>
<a href="https://eprint.iacr.org/2018/1237">
proposed
</a>
cryptographic Pseudorandom Generators.
</li>
<li>
Some
<a href="https://www.youtube.com/watch?v=IaTlRY7wJ5E&t=2s&ab_channel=SimonsInstitute">
recent
</a>
<a href="https://arxiv.org/abs/2212.05619">
talks
</a>
.
</li>
</ul>
</li>
<li>
<i>
Pseudo-calibration
</i>
, the Low-degree Polynomial Method and
<b>
Sharp Computational Thresholds in Average-Case
</b>
<ul>
<li>
Lower bounds for SoS SDPs via planted vs null distinguishing problems with applications to
<a href="http://arxiv.org/abs/1501.00734">
random CSPs
</a>
,
<a href="https://arxiv.org/abs/1604.03084">
planted clique
</a>
,
<a href="">
Tensor/Sparse PCA
</a>
, with new connections to
<a href="https://arxiv.org/abs/1710.05017">
spectral methods and the low degree polynomial heuristic for computational phase transitions in statistical estimation
</a>
</li>
<li>
<a href="">
Exponential lower bounds
</a>
for linear relaxations for constraint satisfaction
</li>
<li>
<a href="https://video.ias.edu/csdm/2017/0307-Kothari">
Some
</a>
<a href="https://www.youtube.com/watch?v=BG66uWKa8Qw">
talks
</a>
.
</li>
</ul>
</li>
</ul>
<p>
</p>
<h2>
Current Teaching
</h2>
<p>
<a href="https://www.cs251.com/">
<b>
15-251: Great Ideas in Theoretical Computer Science
</b>
</a>
<br>
with
<a href="">
Anil Ada
</a>
<br>
</p>
<!-- <h2> Current Teaching </h2>
<p> <a href="http://www.computational-lens.com"><b>15-155: The Computational Lens</b></a> <br>
<i>A class focused on the use of theory of computation as a lens on other fields of inquiry.</i><br>
Tue-Thu, 3:30-4:50pm, GHC 4102 <br>
Office Hours: after class <br>
</p>
-->
<h2>
Service
</h2>
<p>
<b>
Workshop Co-Chair
</b>
, FOCS 2023 and 2024
</p>
<p>
PC Member
<b>
<a href="http://cui.unige.ch/tcs/random-approx/2018/index.php">
APPROX/RANDOM 2018
</a>
</b>
,
<b>
<a href="http://www.siam.org/meetings/da19/">
SODA 2019
</a>
</b>
,
<b>
<a href="">
STOC 2020
</a>
</b>
,
<b>
<a href="">
ITCS 2020
</a>
</b>
,
<b>
<a href="">
NeurIPS Area Chair 2020,2021
</a>
</b>
,
<b>
<a href="">
CCC 2022
</a>
</b>
,
<b>
<a href="">
RANDOM 2022
</a>
</b>
,
<b>
<a href="">
FSTTCS 2022
</a>
</b>
,
<b>
<a href="">
FOCS 2023
</a>
</b>
</p>
<h2>
Advising
</h2>
<p>
<b>
Postdocs:
</b>
<br>
<a href="http://alpergur.xyz/">
Alperen Ergür
</a>
(Fall 2019-20, Now Assistant Professor of Math and CS at UT San Antonio),
<br>
<a href="https://mitalibafna.github.io/">
Mitali Bafna
</a>
(Fall 2022-23, now postdoc at MIT Math)
<br>
<b>
PhD Students:
</b>
<br>
<a href="http://aineshbakshi.com/">
Ainesh Bakshi
</a>
(co-advised with David Woodruff, graduated 2022, now postdoc at MIT Math)
<br>
<a href="https://jthsieh.github.io/">
Tim Hsieh
</a>
,
<br>
<a href="https://www.cs.cmu.edu/~pmanohar/">
Peter Manohar
</a>
(winner of the
<b>
2023 Cylab Presidential Fellowship
</b>
, co-advised with Venkat Guruswami),
<br>
<a href="https://www.andrew.cmu.edu/user/xinyuw1/">
Xinyu Wu
</a>
(winner of the
<b>
MSR Ada Lovelace Fellowship
</b>
, co-advised with Ryan O'Donnell),
<br>
<a href="https://jeffxsc.github.io/">
Jeff Xu
</a>
(winner of the
<b>
2022 Cylab Presidential Fellowship
</b>
)
<br>
<b>
Undergraduates:
</b>
<br>
<a href="https://www.linkedin.com/in/prashanti-anderson">
Prashanti Anderson
</a>
(Phd student at MIT EECS,
<b>
Alan J Perlis Award
</b>
for student teaching,
<i>
runner up
</i>
to the
<b>
Alan Newell award
</b>
for best undergraduate SCS thesis for 2023),
<br>
<a href="https://profiles.stanford.edu/misha-ivkov">
Misha Ivkov
</a>
(PhD student at Stanford, winner of the
<b>
Mark Stehlik SCS Alumni Undergraduate Impact Scholarship
</b>
),
<br>
<a href="">
Zachary Sussman
</a>
(winner of the
<b>
Alan Newell Award
</b>
for best undergraduate SCS Thesis)
</p>
<!-- winner of the <b>2023 Cylab Presidential Fellowship</b>, -->
<h2>
Some Representative Papers (for all papers, see
<a href="./papers.html">
<u>
here
</u>
</a>
)
</h2>
<font color="brown">
<h3>
Algorithms for Learning Mixtures of Gaussians
</h3>
</font>
<ul>
<li>
<b>
<a href="https://arxiv.org/abs/2012.02119">
Robustly Learning a Mixture of $k$ Arbitrary Gaussians
</a>
</b>
<br>
With
<a href="http://aineshbakshi.com">
Ainesh Bakshi
</a>
,
<a href="http://www.iliasdiakonikolas.org/">
Ilias Diakonikolas
</a>
,
<a href="https://aco.gatech.edu/users/hjia36">
He Jia
</a>
,
<a href="https://cseweb.ucsd.edu/~dakane/">
Daniel Kane
</a>
,
<a href="https://www.cc.gatech.edu/~vempala/">
Santosh Vempala
</a>
<br>
<b>
STOC
</b>
, 2022.
<b>
<a href="https://sites.google.com/view/tcsplus/welcome/past-talks?authuser=0#h.o1qhq3db56i4" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<li>
<a href="https://arxiv.org/abs/2005.02970">
<b>
Outlier-Robust Clustering of Non-Spherical Mixtures
</b>
</a>
<br>
With
<a href="http://aineshbakshi.com">
Ainesh Bakshi
</a>
<br>
<b>
FOCS
</b>
, 2020.
<b>
<a href="https://bluejeans.com/s/PB8AX/" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
<br>
Conference version to be merged with
<i>
<u>
<a href="https://arxiv.org/abs/2005.06417">
this
</a>
</u>
</i>
paper.
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1711.07465">
Better Agnostic Clustering Via Relaxed Tensor Norms
</a>
</b>
<br>
With
<a href="http://cs.stanford.edu/~jsteinhardt/">
Jacob Steinhardt
</a>
Conference version merged with
<a href="https://arxiv.org/abs/1711.11581">
this
</a>
paper.
</li>
</ul>
<font color="brown">
<h3>
Spectral Refutations via Kikuchi Matrices and Applications
</h3>
</font>
<ul>
<li>
<b>
<a href="https://arxiv.org/abs/2401.11590">
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
</a>
</b>
<br>
With
<a href="">
Tim Hsieh
</a>
,
<a href="">
Sidhanth Mohanty
</a>
,
<a href="">
David Munha Correia
</a>
, and
<a href="">
Benny Sudakov
</a>
<br>
<b>
Manuscript
</b>
, 2024
<br>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2311.00558">
An Exponential Lower Bound on Linear Three-Query Locally Correctable Codes
</a>
</b>
<br>
With
<a href="https://www.cs.cmu.edu/~pmanohar/">
Peter Manohar
</a>
<br>
<b>
STOC
</b>
, 2024 (to appear)
<br>
</li>
<li>
<b>
<a href="https://eccc.weizmann.ac.il/report/2022/101">
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
</a>
</b>
<br>
With
<a href="">
Omar Alrabiah
</a>
,
<a href="http://www.cs.cmu.edu/~venkatg/">
Venkat Guruswami
</a>
and
<a href="https://www.cs.cmu.edu/~pmanohar/">
Peter Manohar
</a>
<br>
<b>
STOC
</b>
, 2023.
<br>
<b>
<font color="red">
Invited to SICOMP Special Issue for STOC'23
</font>
</b>
<br>
<b>
<a href="https://www.youtube.com/watch?v=NFbQESM3zKg&ab_channel=TAUVOD" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2207.10850">
A simple and sharper proof of the hypergraph Moore bound
</a>
</b>
<br>
With
<a href="https://jthsieh.github.io/">
Tim Hsieh
</a>
and
<a href="">
Sidhanth Mohanty
</a>
<br>
<b>
SODA
</b>
, 2023.
<br>
<b>
<a href="https://www.youtube.com/watch?v=NFbQESM3zKg&ab_channel=TAUVOD" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2109.04415">
Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no Harder than Random
</a>
</b>
<br>
With
<a href="http://www.cs.cmu.edu/~venkatg/">
Venkat Guruswami
</a>
and
<a href="https://www.cs.cmu.edu/~pmanohar/">
Peter Manohar
</a>
<br>
<b>
STOC
</b>
, 2022.
<b>
<a href="https://www.youtube.com/watch?v=IaTlRY7wJ5E&t=2s&ab_channel=SimonsInstitute" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
<br>
<b>
<font color="red">
Invited to the
<i>
SICOMP Special Issue
</i>
for STOC 2022,
<font color="purple">
<i>
CACM Research Highlights
</i>
2023
</font>
</font>
</b>
</li>
</ul>
<font color="brown">
<h3>
Algorithms and Thresholds for Semirandom and Smoothed Models
</h3>
</font>
<ul>
<li>
<b>
<a href="https://arxiv.org/abs/2302.12289">
Efficient Algorithms for Semirandom Planted CSPs at the
Refutation Threshold
</a>
</b>
<br>
With
<a href="http://www.cs.cmu.edu/~venkatg/">
Venkat Guruswami
</a>
,
<a href="https://jthsieh.github.io/">
Tim Hsieh
</a>
, and
<a href="https://www.cs.cmu.edu/~pmanohar/">
Peter Manohar
</a>
<br>
<b>
FOCS
</b>
, 2023 (to appear).
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2212.05619">
Algorithms approaching the threshold for semi-random planted clique
</a>
</b>
<br>
With
<a href="https://raresbuhai.github.io/">
Rares Buhai
</a>
and
<a href="https://www.dsteurer.org/">
David Steurer
</a>
<br>
<b>
STOC
</b>
, 2023 (to appear).
<br>
<b>
<a href="https://www.youtube.com/watch?v=eQF74Ixb7oo" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2207.10850">
A simple and sharper proof of the hypergraph Moore bound
</a>
</b>
<br>
With
<a href="https://jthsieh.github.io/">
Tim Hsieh
</a>
and
<a href="">
Sidhanth Mohanty
</a>
<br>
<b>
SODA
</b>
, 2023.
<br>
<b>
<a href="https://www.youtube.com/watch?v=NFbQESM3zKg&ab_channel=TAUVOD" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<!--
<li><b><a href="https://arxiv.org/abs/2109.04415">Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no Harder than Random</a></b><br>
With <a href="http://www.cs.cmu.edu/~venkatg/"> Venkat Guruswami </a> and <a href="https://www.cs.cmu.edu/~pmanohar/">Peter Manohar </a><br>
<b>STOC</b>, 2022. <b><a href="https://www.youtube.com/watch?v=IaTlRY7wJ5E&t=2s&ab_channel=SimonsInstitute" style="color:red;"><u>LONG TALK</u></a>.</b><br>
<b><font color="red">Invited to the <i>SICOMP Special Issue</i> for STOC 2022, <font color="purple"><i>CACM Research Highlights</i> 2023</font></font></b>
</li> -->
<li>
<b>
<a href="https://arxiv.org/abs/2009.08032">
Strongly refuting all semi-random Boolean CSPs
</a>
</b>
<br>
With
<a href="https://www.csd.cs.cmu.edu/people/graduate-student/jackson-abascal">
Jackson Abascal
</a>
and
<a href="http://www.cs.cmu.edu/~venkatg">
Venkat Guruswami
</a>
.
<br>
<b>
SODA
</b>
, 2021.
<b>
<a href="https://www.youtube.com/watch?v=KZRMiQfcT_o" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1701.04521">
Sum-of-Squares Lower Bounds for Refuting any CSP
</a>
</b>
<br>
With
<a href="http://www.is.titech.ac.jp/~mori/">
Ryuhei Mori
</a>
,
<a href="https://www.cs.cmu.edu/~odonnell/">
Ryan O'Donnell
</a>
and
<a href="https://www.cs.cmu.edu/~dwitmer/">
David Witmer
</a>
<br>
<b>
STOC
</b>
, 2017.
</li>
</ul>
<font color="brown">
<h3>
Algorithmic Robust Statistics and Related Topics
</h3>
</font>
<ul>
<li>
<b>
<a href="https://arxiv.org/abs/2302.12289">
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
</a>
</b>
<br>
With
<a href="">
He Jia
</a>
and
<a href="https://faculty.cc.gatech.edu/~vempala/">
Santosh Vempala
</a>
<br>
<b>
FOCS
</b>
, 2023 (to appear).
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2212.08018">
Privately Estimating a Gaussian: Efficient, Robust and Optimal
</a>
</b>
<br>
With
<a href="https://alabidan.me/">
Daniel Alabi
</a>
,
<a href="https://www.seas.harvard.edu/person/pranay-tankala">
Pranay Tankala
</a>
,
<a href="https://vprayaag.github.io/">
Prayaag Venkat
</a>
and
<a href="https://fredzhang.me/">
Fred Zhang
</a>
<br>
<b>
STOC
</b>
, 2023 (to appear).
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2211.13312">
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
</a>
</b>
<br>
With
<a href="">
Aravind Gallakota
</a>
and
<a href="https://www.cs.utexas.edu/~klivans/">
Adam Klivans
</a>
<br>
<b>
STOC
</b>
, 2023 (to appear).
<br>
<b>
<font color="red">
Invited to SICOMP Special Issue for STOC'23
</font>
</b>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2206.10942">
List-Decodable Covariance Estimation
</a>
</b>
<br>
With
<a href="https://www.andrew.cmu.edu/user/mivkov/">
Misha Ivkov
</a>
<br>
<b>
STOC
</b>
, 2022.
<br>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2002.05139">
List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time
</a>
</b>
<br>
With
<a href="http://aineshbakshi.com">
Ainesh Bakshi
</a>
<br>
<b>
SODA
</b>
, 2021.
<br>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1905.05679">
List-Decodable Linear Regression
</a>
</b>
<br>
With
<a href="">
Sushrut Karmalkar
</a>
and
<a href="http://www.cs.utexas.edu/~klivans">
Adam Klivans
</a>
<br>
<b>
NeuIPS Spotlight
</b>
, 2019.
<b>
<a href="https://www.youtube.com/watch?v=ZoODlvo-5wA" style="color:red;">
<u>
LONG TALK
</u>
</a>
.
</b>
</li>
<li>
<b>
<a href="">
Sparse PCA: algorithms, adversarial perturbations and certificates
</a>
</b>
<br>
With
<a href="">
Tommaso D'Orsi
</a>
,
<a href="">
Gleb Novikov
</a>
, and
<a href="http://dsteurer.org">
David Steurer
</a>
.
<br>
<b>
FOCS
</b>
2020.
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1803.03241">
Efficient Algorithms for Outlier-Robust Regression
</a>
</b>
<br>
With
<a href="http://www.cs.utexas.edu/~klivans">
Adam Klivans
</a>
and
<a href="http://www.raghumeka.org">
Raghu Meka
</a>
<br>
<b>
COLT 2018
</b>
<br>
<font color="red">
Prasad Raghavendra's
<a href="https://www.youtube.com/watch?v=BCOafN4In98&ab_channel=SimonsInstitute">
<font color="red">
<b>
<u>
Exposition
</u>
</b>
</font>
</a>
of our algorithm in a Simons Institute Bootcamp
</font>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1711.11581">
Outlier-Robust Moment Estimation Via Sum-of-Squares
</a>
</b>
<br>
With
<a href="https://www.dsteurer.org/">
David Steurer
</a>
<br>
<b>
STOC 2018
</b>
<b>
<a href="https://www.youtube.com/watch?v=9s5kkIn5TsQ&list=PLCA9C279868C62EB1&index=206" style="color:red;">
<u>
2 hour BOARD TALK
</u>
</a>
</b>
.
<br>
Conference version merged with
<a href="https://arxiv.org/abs/1711.07465">
this
</a>
paper.
</li>
</ul>
<font color="brown">
<h3>
Algorithms and Complexity of Unique Games and Related Problems
</h3>
</font>
<ul>
<li>
<b>
<a href="https://arxiv.org/abs/2006.09969">
Playing Unique Games on Certified Small-Set Expanders
</a>
</b>
<br>
With
<a href="https://mitalibafna.github.io/">
Mitali Bafna
</a>
,
<a href="http://boazbarak.org">
Boaz Barak
</a>
,
<a href="https://tselilschramm.org/">
Tselil Schramm
</a>
and
<a href="https://www.dsteurer.org/">
David Steurer
</a>
.
<br>
<b>
STOC
</b>
, 2021.
<br>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1701.06321">
Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture
</a>
</b>
<br>
With
<a href="http://boazbarak.org">
Boaz Barak
</a>
and
<a href="http://dsteurer.org">
David Steurer
</a>
<br>
<b>
STOC, 2017
</b>
<br>
Recent
<b>
<a href="https://www.youtube.com/watch?v=K2VFS1gADdw" style="color:red;">
50 min talk
</a>
</b>
and a shorter
<b>
<a href="https://www.youtube.com/watch?v=TwLz5cqHF6M" style="color:red;">
talk
</a>
</b>
with a different perspective.
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1804.08662">
Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture
</a>
</b>
<br>
With
<a href="http://boazbarak.org">
Boaz Barak
</a>
and
<a href="http://dsteurer.org">
David Steurer
</a>
<br>
<b>
A generally accessible
<a href="https://www.quantamagazine.org/computer-scientists-close-in-on-unique-games-conjecture-proof-20180424/">
article
</a>
on the recent proof of the 2-to-2 games conjecture that partly relies on this work.
</b>
<br>
</li>
</ul>
<font color="brown">
<h3>
Average-Case Algorithmic Thresholds
</h3>
</font>
</i>
<ul>
<i>
<li>
<b>
<a href="">
Sum of Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
</a>
</b>
<br>
With
<a href="">
Aaron Potechin
</a>
and
<a href="">
Jeff Xu
</a>
.
<br>
<b>
STOC
</b>
, 2024 (to appear)
</li>
<li>
<b>
<a href="https://arxiv.org/abs/2110.08677">
Algorithmic Thresholds for Refuting Random Polynomial Systems
</a>
</b>
<br>
With
<a href="https://jthsieh.github.io/">
Tim Hsieh
</a>
.
<br>
<b>
SODA
</b>
, 2022.
</li>
<li>
<b>
<a href="https://arxiv.org/pdf/2105.07517.pdf">
A Stress-Free Sum-of-Squares Lower Bound for Coloring
</a>
</b>
<br>
With
<a href="http://www.cs.cmu.edu/~pmanohar">
Peter Manohar
</a>
.
<br>
<b>
CCC
</b>
, 2021.
<br>
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1710.05017">
The power of sum-of-squares for detecting hidden structures
</a>
</b>
<br>
With
<a href="https://www.cs.cornell.edu/~samhop/">
Samuel B. Hopkins
</a>
,
<a href="http://www.cs.princeton.edu/~kothari/">
Aaron Potechin
</a>
,
<a href="http://www.cs.berkeley.edu/~prasad">
Prasad Raghavendra
</a>
,
<a href="http://www.cs.berkeley.edu/~tschramm/">
Tselil Schramm
</a>
and
<a href="http://dsteurer.org/">
David Steurer
</a>
<br>
<b>
FOCS 2017
</b>
<br>
<b>
<font color="red">
Invited to the Highlights of Algorithms (HALG) 2018
</font>
</b>
</li>
</i>
<li>
<i>
<b>
<a href="https://arxiv.org/abs/1604.03084">
A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique
</a>
</b>
</i>
<br>
With
<a href="http://www.boazbarak.org/ ">
Boaz Barak
</a>
,
<a href="https://www.cs.cornell.edu/~samhop/ ">
Sam Hopkins
</a>
,
<a href="http://math.mit.edu/~kelner/ ">
Jon Kelner
</a>
,
<a href="http://people.csail.mit.edu/moitra/ ">
Ankur Moitra
</a>
and
<a href="">
Aaron Potechin
</a>
<br>
<b>
FOCS 2016.
</b>
<b>
<a href="https://video.ias.edu/csdm/2017/0307-Kothari">
[Video- IAS CS/DM Seminar]
</a>
<a href="https://windowsontheory.org/2016/04/13/bayesianism-frequentism-and-the-planted-clique-or-do-algorithms-believe-in-unicorns/ " style="color:red">
[Boaz's WOT post]
</a>
</b>
<br>
<i>
<font color="red">
<b>
Invited to SICOMP Special Issue for FOCS 2016
</b>
</font>
</i>
</li>
<li>
<b>
<a href="http://arxiv.org/abs/1507.05230">
SoS and Planted Clique: Tight Analysis of MPW Moments
<br>
at all Degrees and an Optimal Lower Bound at Degree Four
</a>
</b>
<br>
With
<a href="https://www.cs.cornell.edu/~samhop/">
Samuel B. Hopkins
</a>
and
<a href="http://math.mit.edu/directory/profile.php?pid=1272">
Aaron Potechin
</a>
<br>
<b>
SODA 2016
</b>
<br>
<i>
<font color="red">
<b>
Invited to the ACM Transactions on Algorithms, Special Issue for SODA 2016
</b>
</font>
</i>
<br>
Conference version merged with
<a href="http://arxiv.org/abs/1507.05136">
this
</a>
paper.
</li>
<li>
<b>
<a href="https://arxiv.org/abs/1610.02704">
Approximating Rectangles by Juntas and a Weakly Exponential Lower Bound for LP Relaxations of CSPs
</a>
</b>
<br>
With
<a href="http://www.raghumeka.org">
Raghu Meka
</a>
and
<a href="http://www.cs.berkeley.edu/~prasad">
Prasad Raghavendra
</a>
<br>
<b>
STOC, 2017
</b>
<br>
<i>
<font color="red">
<b>
Invited to SICOMP Special Issue for STOC 2017
</b>
</font>
</i>
<br>
Recent
<b>
<a href="https://www.youtube.com/watch?v=BG66uWKa8Qw" style="color:red;">
50 min talk
</a>
.
</b>
</li>
</ul>
<font color="brown">
<h3>
Applications
</h3>
</font>
<ul>
<li>
<b>
<a href="https://arxiv.org/abs/1806.09426">
Sum-of-Squares Meets Nash: Lower Bounds for finding
<i>
any
</i>
equilibrium
</a>
</b>
<br>
With
<a href="http://cs.stanford.edu/~jsteinhardt/">
Ruta Mehta
</a>
<br>
<b>
STOC 2018
</b>
</li>
<li>
<b>
<a href="https://eccc.weizmann.ac.il/report/2017/060/download">
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
</a>
</b>
<br>
With
<a href="http://boazbarak.org">
Boaz Barak
</a>
,
<a href="http://www.wisdom.weizmann.ac.il/~zvikab/">
Zvika Brakerski
</a>
and
<a href="https://sites.google.com/site/ilankomhomepage/">
Ilan Komargodski
</a>
<br>
<b>
EUROCRYPT 2018
</b>
</li>
</ul>
<h2>
Mentoring Talks
</h2>
<p>
I recently gave two mentoring talks as part of the new workshops organized by
<b>
<a href="https://let-all.com/">
Learning Theory Alliance
</a>
</b>
<br>
Slides from talk on
<b>
<a href="How-to-kothari1.pdf">
Interacting with your Research Community
</a>
.
</b>
<br>
Slides from talk on
<b>
<a href="how-to-kothari2.pdf">
Thoughts on PhD Admissions
</a>
</b>
.
</p>
<!-- <h2>Seminars</h2>
In Fall 2016, co-taught (with David Steurer) a seminar (notes online) on <a href="http://dsteurer.org/sos">"<it>Proofs, Beliefs and Algorithms through the lens of Sum-of-Squares</it>" </a> at Princeton CS.
</p>
-->
</div>
</div>
</body>
</html>