Showing source for: https://www.cs.princeton.edu/~kothari/
Redirects (1): http://www.cs.cmu.edu/~praveshk/(302) ⟶ https://www.cs.princeton.edu/~kothari/
Duration: 0.460911s
Server: Apache/2.4.41 (Springdale Linux) OpenSSL/1.0.2k-fips mod_fcgid/2.3.9 PHP/5.6.25 Phusion_Passenger/5.0.30

<!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&egrave;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&amp;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&amp;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&amp;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&amp;t=2s&amp;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&uuml;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&amp;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&amp;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&amp;t=2s&amp;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&amp;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&amp;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&amp;list=PLCA9C279868C62EB1&amp;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>

Latest requests

# Url Url Source Date
1 https://www.cs.princeton.edu/~koth… 2024-03-28 16:21:08
2 https://thebolditalic.com/?gi=6b63… 2024-03-28 16:21:06
3 https://thebolditalic.com/?gi=14f4… 2024-03-28 16:21:02
4 https://thebolditalic.com/?gi=5f82… 2024-03-28 16:20:58
5 https://thebolditalic.com/?gi=a313… 2024-03-28 16:20:55
6 https://thebolditalic.com/?gi=9702… 2024-03-28 16:20:50
7 https://thebolditalic.com/?gi=fa81… 2024-03-28 16:20:46
8 https://thebolditalic.com/?gi=80c1… 2024-03-28 16:20:42
9 https://thebolditalic.com/?gi=3001… 2024-03-28 16:20:38
10 https://thebolditalic.com/?gi=2a6b… 2024-03-28 16:20:34
11 https://thebolditalic.com/?gi=11ea… 2024-03-28 16:20:30
12 https://thebolditalic.com/?gi=d3ad… 2024-03-28 16:20:28
13 https://thebolditalic.com/?gi=d47e… 2024-03-28 16:20:26
14 https://thebolditalic.com/?gi=ee53… 2024-03-28 16:20:22
15 https://thebolditalic.com/?gi=6ba5… 2024-03-28 16:20:18
16 https://thebolditalic.com/?gi=c270… 2024-03-28 16:20:14
17 https://thebolditalic.com/?gi=ee4a… 2024-03-28 16:20:10
18 https://thebolditalic.com/?gi=c6fc… 2024-03-28 16:20:06
19 https://thebolditalic.com/?gi=b044… 2024-03-28 16:20:02
20 https://thebolditalic.com/?gi=92fb… 2024-03-28 16:19:58