CINXE.COM

<!doctype html><html lang="en" class="overflow-y-scroll-ns"><head><meta charSet="utf-8"/><meta name="description" content="David Steurer is an associate professor at ETH Zurich. He investigates the power and limitations of mathematical relaxations for basic optimization and estimation problems. His current focus is on the sum-of-squares method and the Unique Games Conjecture with applications to estimation problems that arise in machine learning. "/><meta name="viewport" content="width=device-width, initial-scale=1"/><link rel="icon" href="/images/eth.jpg"/><title>David Steurer — ETH Zurich, Computer Science, Theory</title><style>@font-face{font-family:KaTeX_AMS;src:url(katex/dist/fonts/KaTeX_AMS-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_AMS-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_AMS-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Caligraphic;src:url(katex/dist/fonts/KaTeX_Caligraphic-Bold.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Caligraphic-Bold.woff) format("woff"),url(katex/dist/fonts/KaTeX_Caligraphic-Bold.ttf) format("truetype");font-weight:700;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Caligraphic;src:url(katex/dist/fonts/KaTeX_Caligraphic-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Caligraphic-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Caligraphic-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Fraktur;src:url(katex/dist/fonts/KaTeX_Fraktur-Bold.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Fraktur-Bold.woff) format("woff"),url(katex/dist/fonts/KaTeX_Fraktur-Bold.ttf) format("truetype");font-weight:700;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Fraktur;src:url(katex/dist/fonts/KaTeX_Fraktur-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Fraktur-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Fraktur-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Main;src:url(katex/dist/fonts/KaTeX_Main-Bold.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Main-Bold.woff) format("woff"),url(katex/dist/fonts/KaTeX_Main-Bold.ttf) format("truetype");font-weight:700;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Main;src:url(katex/dist/fonts/KaTeX_Main-BoldItalic.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Main-BoldItalic.woff) format("woff"),url(katex/dist/fonts/KaTeX_Main-BoldItalic.ttf) format("truetype");font-weight:700;font-style:italic;font-display:swap}@font-face{font-family:KaTeX_Main;src:url(katex/dist/fonts/KaTeX_Main-Italic.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Main-Italic.woff) format("woff"),url(katex/dist/fonts/KaTeX_Main-Italic.ttf) format("truetype");font-weight:400;font-style:italic;font-display:swap}@font-face{font-family:KaTeX_Main;src:url(katex/dist/fonts/KaTeX_Main-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Main-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Main-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Math;src:url(katex/dist/fonts/KaTeX_Math-BoldItalic.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Math-BoldItalic.woff) format("woff"),url(katex/dist/fonts/KaTeX_Math-BoldItalic.ttf) format("truetype");font-weight:700;font-style:italic;font-display:swap}@font-face{font-family:KaTeX_Math;src:url(katex/dist/fonts/KaTeX_Math-Italic.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Math-Italic.woff) format("woff"),url(katex/dist/fonts/KaTeX_Math-Italic.ttf) format("truetype");font-weight:400;font-style:italic;font-display:swap}@font-face{font-family:"KaTeX_SansSerif";src:url(katex/dist/fonts/KaTeX_SansSerif-Bold.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_SansSerif-Bold.woff) format("woff"),url(katex/dist/fonts/KaTeX_SansSerif-Bold.ttf) format("truetype");font-weight:700;font-style:normal;font-display:swap}@font-face{font-family:"KaTeX_SansSerif";src:url(katex/dist/fonts/KaTeX_SansSerif-Italic.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_SansSerif-Italic.woff) format("woff"),url(katex/dist/fonts/KaTeX_SansSerif-Italic.ttf) format("truetype");font-weight:400;font-style:italic;font-display:swap}@font-face{font-family:"KaTeX_SansSerif";src:url(katex/dist/fonts/KaTeX_SansSerif-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_SansSerif-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_SansSerif-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Script;src:url(katex/dist/fonts/KaTeX_Script-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Script-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Script-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Size1;src:url(katex/dist/fonts/KaTeX_Size1-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Size1-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Size1-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Size2;src:url(katex/dist/fonts/KaTeX_Size2-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Size2-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Size2-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Size3;src:url(katex/dist/fonts/KaTeX_Size3-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Size3-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Size3-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Size4;src:url(katex/dist/fonts/KaTeX_Size4-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Size4-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Size4-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap}@font-face{font-family:KaTeX_Typewriter;src:url(katex/dist/fonts/KaTeX_Typewriter-Regular.woff2) format("woff2"),url(katex/dist/fonts/KaTeX_Typewriter-Regular.woff) format("woff"),url(katex/dist/fonts/KaTeX_Typewriter-Regular.ttf) format("truetype");font-weight:400;font-style:normal;font-display:swap} /*! TACHYONS v4.12.0 | http://tachyons.io */ /*! normalize.css v8.0.0 | MIT License | github.com/necolas/normalize.css */html{line-height:1.15;-webkit-text-size-adjust:100%}body{margin:0}h1{font-size:2em;margin:.67em 0}hr{box-sizing:content-box;height:0;overflow:visible}a{background-color:transparent}strong{font-weight:bolder}img{border-style:none}::-webkit-file-upload-button{-webkit-appearance:button;font:inherit}a,article,body,dd,div,dl,dt,footer,h1,html,li,main,nav,p,ul{box-sizing:border-box}img{max-width:100%}.bb{border-bottom-style:solid;border-bottom-width:1px}.b--black-10{border-color:rgba(0,0,0,.1)}.cf:after,.cf:before{content:" ";display:table}.cf:after{clear:both}.cf{*zoom:1}.db{display:block}.dib{display:inline-block}.flex{display:flex}.flex-column{flex-direction:column}.flex-wrap{flex-wrap:wrap}.items-baseline{align-items:baseline}.justify-center{justify-content:center}.fl{float:left;_display:inline}.sans-serif{font-family:-apple-system,BlinkMacSystemFont,avenir next,avenir,helvetica neue,helvetica,ubuntu,roboto,noto,segoe ui,arial,sans-serif}.b{font-weight:700}.h4{height:8rem}.min-vh-100{min-height:100vh}.lh-title{line-height:1.25}.lh-copy{line-height:1.5}.link{text-decoration:none}.link,.link:active,.link:focus,.link:hover,.link:link,.link:visited{transition:color .15s ease-in}.link:focus{outline:1px dotted currentColor}.list{list-style-type:none}.mw7{max-width:48rem}.w-20{width:20%}.w-80{width:80%}.w-100{width:100%}.dark-gray{color:#333}.mid-gray{color:#555}.dark-blue{color:#00449e}.blue{color:#357edd}.bg-white{background-color:#fff}.hover-dark-blue:focus,.hover-dark-blue:hover{color:#00449e}.pl0{padding-left:0}.pt3{padding-top:1rem}.ph2{padding-left:.5rem;padding-right:.5rem}.ma0{margin:0}.mr2{margin-right:.5rem}.mb1{margin-bottom:.25rem}.mb2{margin-bottom:.5rem}.mb3{margin-bottom:1rem}.mt0{margin-top:0}.mv4{margin-top:2rem;margin-bottom:2rem}.underline{text-decoration:underline}.f3{font-size:1.5rem}.f5{font-size:1rem}.f6{font-size:.875rem}.center{margin-right:auto;margin-left:auto}@media screen and (min-width:30em){.h5-ns{height:16rem}.w-third-ns{width:33.33333%}.w-two-thirds-ns{width:66.66667%}.overflow-y-scroll-ns{overflow-y:scroll}.ph3-ns{padding-left:1rem;padding-right:1rem}}.underline{text-decoration-color:rgba(0,105,180,.5);text-decoration-thickness:.1em}.blue{color:#0069b4}.dark-blue,.hover-dark-blue:hover{color:#1f407a}</style></head><body><div id="main" class="mw7 center ph2 ph3-ns pt3 dark-gray bg-white sans-serif flex flex-column min-vh-100"><nav class="cf mb3 sans-serif lh-copy"><div class="fl w-third-ns w-100"><span class="dark-blue b">David Steurer</span></div><div class="fl w-two-thirds-ns w-100"><ul class="list dib pl0 ma0"><li class="dib mr2"><span class="dark-gray">home</span></li><li class="dib mr2"><a href="/papers/" class="link underline hover-dark-blue blue">papers</a></li><li class="dib mr2"><a href="/talks/" class="link underline hover-dark-blue blue">talks</a></li><li class="dib mr2"><a href="/cv/" class="link underline hover-dark-blue blue">c.v.</a></li><li class="dib mr2"><a href="/courses/" class="link underline hover-dark-blue blue">courses</a></li><li class="dib mr2"><a href="/contact/" class="link underline hover-dark-blue blue">contact</a></li></ul></div></nav><main style="flex:1"><article class="lh-copy"> <div class="flex"> <div class="w-third-ns w-100 pt3"> <div class="line-block">Associate Professor<br/> Computer Science<br/> ETH Zurich</div> </div> <div class="w-two-thirds-ns w-100"> <p class="mt0 mb2"><a class="blue hover-dark-blue link underline" href="/images/photo-orig.jpg"><img src="/images/photo.jpg" class="h5-ns h4" alt="photo"/></a></p> </div> </div> <h1 class="lh-title f3 dark-blue" id="positions">positions</h1> <p class="mt0 mb2">I am looking for highly motivated postdocs and PhD students with a strong background in theoretical computer science, mathematics, or statistics. If you are interested, please contact me.</p> <h1 class="lh-title f3 dark-blue" id="selected-events-all-events">selected events (<a class="blue hover-dark-blue link underline" href="/events/">all events</a>)</h1> <dl class="flex flex-wrap items-baseline"> <dt class="db w-20 f6 mb1 mid-gray">Feb. 2020</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="https://theory.epfl.ch/WinterSchool2020/"><em>Swiss Winter School on Lower Bounds and Communication Complexity</em></a> for PhD students. Application deadline: November 15th 2019 </dd> <dt class="db w-20 f6 mb1 mid-gray">Nov. 2019</dt> <dd class="ma0 db w-80 mb1"> mini-course in workshop on <a class="blue hover-dark-blue link underline" href="https://perso.math.univ-toulouse.fr/statistics-geometry-and-topology/accueil/computational-aspects-of-geometry/"><em>Computational Aspects of Geometry</em></a> as part of <a class="blue hover-dark-blue link underline" href="https://perso.math.univ-toulouse.fr/statistics-geometry-and-topology/"><em>Statistics with Geometry and Topology</em></a> trimister at <a class="blue hover-dark-blue link underline" href="https://www.math.univ-toulouse.fr">IMT Toulouse</a> </dd> <dt class="db w-20 f6 mb1 mid-gray">Sep. 2019</dt> <dd class="ma0 db w-80 mb1"> Clay Mathematics Institute (CMI) workshop <a class="blue hover-dark-blue link underline" href="http://claymath.org/events/beyond-spectral-gaps"><em>Beyond Spectral Gaps</em></a>, University of Oxford </dd> <dt class="db w-20 f6 mb1 mid-gray">Jan. 2019</dt> <dd class="ma0 db w-80 mb1"> focus lecture at <a class="blue hover-dark-blue link underline" href="http://www.iasi.cnr.it/aussois/web/home/program/year/2019">23rd Combinatorial Optimization Workshop</a>, Aussois </dd> <dt class="db w-20 f6 mb1 mid-gray">Aug. 2018</dt> <dd class="ma0 db w-80 mb1"> invited lecture at <a class="blue hover-dark-blue link underline" href="http://www.icm2018.org/">International Congress for Mathematicians 2018</a> </dd> <dt class="db w-20 f6 mb1 mid-gray">Jan. 2018</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://www.nasonline.org/programs/awards/2018/Raghavendra-Steurer.html">Michael and Sheila Held prize</a> </dd> <dt class="db w-20 f6 mb1 mid-gray">Jan. 2017</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://cseweb.ucsd.edu/~slovett/workshops/sum-of-squares-2017/">winter school on sum-of-squares</a>, UC San Diego, see <a class="blue hover-dark-blue link underline" href="http://cseweb.ucsd.edu/~slovett/workshops/sum-of-squares-2017/schedule.html"><strong>slides</strong></a> </dd> <dt class="db w-20 f6 mb1 mid-gray">Sep. 2016</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://sos16.dsteurer.org">seminar on sum-of-squares</a> at Princeton University with <a class="blue hover-dark-blue link underline" href="http://sumofsquares.org"><strong>lecture notes</strong></a> </dd> <dt class="db w-20 f6 mb1 mid-gray">May 2016</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="https://theory.eecs.northwestern.edu/events/sum-of-squares/">Quarterly Theory Workshop: Semidefinite Programming Hierarchies and Sum of Squares</a>, Northwestern University. </dd> </dl> <h1 class="lh-title f3 dark-blue" id="curriculum-vitæ-webcv-html-pdfcv-pdf">curriculum vitæ (<a class="blue hover-dark-blue link underline" href="/cv/" title="CV (web version)">web</a> / <a class="blue hover-dark-blue link underline" href="/cv.pdf" title="CV (pdf version)">pdf</a>)</h1> <dl class="flex flex-wrap items-baseline"> <dt class="db w-20 f6 mb1 mid-gray">2020–</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="https://www.inf.ethz.ch/">ETH Zurich</a> — associate professor </dd> <dt class="db w-20 f6 mb1 mid-gray">2017–2020</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="https://www.inf.ethz.ch/">ETH Zurich</a> — assistant professor </dd> <dt class="db w-20 f6 mb1 mid-gray">2016–2017</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://www.math.ias.edu">Institute for Advanced Study</a> — visiting assistant professor </dd> <dt class="db w-20 f6 mb1 mid-gray">2012–2017</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://www.cornell.edu">Cornell University</a> <a class="blue hover-dark-blue link underline" href="http://www.cs.cornell.edu">Department of Computer Science</a> — assistant professor </dd> <dt class="db w-20 f6 mb1 mid-gray">2010–2012</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://research.microsoft.com/en-us/labs/newengland/default.aspx">Microsoft Research New England</a> — postdoc </dd> <dt class="db w-20 f6 mb1 mid-gray">2006–2010</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://www.cs.princeton.edu/">Princeton University</a> — Ph.D., advised by <a class="blue hover-dark-blue link underline" href="http://www.cs.princeton.edu/~arora/">Sanjeev Arora</a> </dd> <dt class="db w-20 f6 mb1 mid-gray">2003–2006</dt> <dd class="ma0 db w-80 mb1"> <a class="blue hover-dark-blue link underline" href="http://www.cs.uni-saarland.de/">Saarland University</a> — undergraduate </dd> </dl> <h1 class="lh-title f3 dark-blue" id="funding">funding</h1> <ul> <li class="mb1">ERC Consolidator Grant, 2019</li> <li class="mb1">Microsoft Research Faculty Fellowship, 2014</li> <li class="mb1"><a class="blue hover-dark-blue link underline" href="https://www.simonsfoundation.org/mathematics-and-physical-science/algorithms-and-geometry-collaboration/">Simons Collaboration: Algorithms and Geometry,</a> 2014–2017</li> <li class="mb1">Alfred P. Sloan Research Fellowship, 2014</li> <li class="mb1">NSF CAREER Award, 2014</li> <li class="mb1">NSF AF Medium 1408673, 2014</li> </ul> <h1 class="lh-title f3 dark-blue" id="group-and-alumni">group and alumni</h1> <ul> <li class="mb1">Stefan Tiegel (PhD student, 2020–now)</li> <li class="mb1">Rares Buhai (PhD student, 2020–now)</li> <li class="mb1">Jingqiu Ding (PhD student, 2020–now)</li> <li class="mb1">Rajai Nasser (postdoc, 2020–now)</li> <li class="mb1">Chih-Hung Liu (postdoc, 2020–now)</li> <li class="mb1">Tommaso d'Orsi (PhD student, 2018–now)</li> <li class="mb1">Gleb Novikov (PhD student, 2017–now)</li> <li class="mb1"><a class="blue hover-dark-blue link underline" href="http://www.samuelbhopkins.com/">Sam Hopkins</a> (PhD student 2013–2018; now: Miller fellow at UC Berkeley; starting 2021–2022: tenure-track assistant professor at MIT)</li> <li class="mb1"><a class="blue hover-dark-blue link underline" href="https://www.jshi.science/">Jonathan Shi</a> (PhD student 2013–2019; now: postdoc with Luca Trevisan at Università Bocconi)</li> <li class="mb1"><a class="blue hover-dark-blue link underline" href="http://www.potechin.org/aaronpotechin/">Aaron Potechin</a> (postdoc 2017; now: assistant professor at U Chicago)</li> </ul> <h1 class="lh-title f3 dark-blue" id="selected-papers-all-papers">selected papers (<a class="blue hover-dark-blue link underline" href="/papers/">all papers</a>)</h1> <a href="/paper/ugcertsse/" class="blue hover-dark-blue link underline">Playing Unique Games on Certified Small-Set Expanders</a> with Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm. <strong>STOC 2021. </strong><a href="/paper/ugcertsse.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/degreereduction/" class="blue hover-dark-blue link underline">SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation</a> with Stefan Tiegel. <strong>SODA 2021. </strong><a href="/paper/degreereduction.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/sparsepca/" class="blue hover-dark-blue link underline">Sparse PCA: Algorithms, Adversarial Perturbations and Certificates</a> with Tommaso d'Orsi, Gleb Novikov, Pravesh Kothari. <strong>FOCS 2020. </strong><a href="/paper/sparsepca.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/surveysos/" class="blue hover-dark-blue link underline">High-dimensional estimation from sum-of-squares proofs</a> with Prasad Raghavendra, Tselil Schramm. <strong>ICM 2018. </strong><a href="/paper/surveysos.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/clustering/" class="blue hover-dark-blue link underline">Improved clustering and robust moment estimation via sum-of-squares</a> with Pravesh Kothari, Jacob Steinhardt. <strong>STOC 2018. </strong><a href="/paper/clustering.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/inference/" class="blue hover-dark-blue link underline">Bayesian estimation from few samples: community detection and related problems</a> with Sam Hopkins. <strong>FOCS 2017. </strong><a href="/paper/inference.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/planted/" class="blue hover-dark-blue link underline">The power of sum-of-squares for detecting hidden structure</a> with Sam Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm. <strong>FOCS 2017. </strong><a href="/paper/planted.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/subexpalg/" class="blue hover-dark-blue link underline">Quantum entanglement, sum of squares, and the log rank conjecture</a> with Boaz Barak, Pravesh Kothari. <strong>STOC 2017. </strong><a href="/paper/subexpalg.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/polytensor/" class="blue hover-dark-blue link underline">Polynomial-time tensor decompositions with sum-of-squares</a> with Tengyu Ma, Jonathan Shi. <strong>FOCS 2016. </strong><a href="/paper/polytensor.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/fastsos/" class="blue hover-dark-blue link underline">Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors</a> with Sam Hopkins, Tselil Schramm, Jonathan Shi. <strong>STOC 2016. </strong><a href="/paper/fastsos.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/sdpsize/" class="blue hover-dark-blue link underline">Lower bounds on the size of semidefinite programming relaxations</a> with James R. Lee, Prasad Raghavendra. <strong>STOC 2015. </strong><a href="/paper/sdpsize.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/soslearning/" class="blue hover-dark-blue link underline">Dictionary learning and tensor decomposition via the sum-of-squares method</a> with Boaz Barak, Jonathan Kelner. <strong>STOC 2015. </strong><a href="/paper/soslearning.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/sosicm/" class="blue hover-dark-blue link underline">Sum-of-squares proofs and the quest toward optimal algorithms</a> with Boaz Barak. <strong>ICM 2014. </strong><a href="/paper/sosicm.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/productgames/" class="blue hover-dark-blue link underline">Analytical approach to parallel repetition</a> with Irit Dinur. <strong>STOC 2014. </strong><a href="/paper/productgames.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/cayleysse/" class="blue hover-dark-blue link underline">Making the long code shorter</a> with Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra. <strong>FOCS 2012. </strong><a href="/paper/cayleysse.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/hypercontract/" class="blue hover-dark-blue link underline">Hypercontractivity, sum-of-squares proofs, and applications</a> with Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, Yuan Zhou. <strong>STOC 2012. </strong><a href="/paper/hypercontract.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/thesis/" class="blue hover-dark-blue link underline">On the complexity of Unique Games and graph expansion</a> <strong>Dissertation. </strong><a href="/paper/thesis.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/subexpug/" class="blue hover-dark-blue link underline">Subexponential algorithms for unique games and related problems</a> with Sanjeev Arora, Boaz Barak. <strong>FOCS 2010. </strong><a href="/paper/subexpug.pdf" class="link b underline hover-dark-blue blue">PDF</a><br/><a href="/paper/expansion/" class="blue hover-dark-blue link underline">Graph expansion and the Unique Games Conjecture</a> with Prasad Raghavendra. <strong>STOC 2010. </strong><a href="/paper/expansion.pdf" class="link b underline hover-dark-blue blue">PDF</a> <h1 class="lh-title f3 dark-blue" id="program-committees">program committees</h1> <ul> <li class="mb1">COLT 2020 (senior pc)</li> <li class="mb1">STOC 2019</li> <li class="mb1">APPROX 2018 (chair)</li> <li class="mb1">COLT 2018</li> <li class="mb1">CCC 2016</li> <li class="mb1">APPROX 2015</li> <li class="mb1">FOCS 2014</li> <li class="mb1">STOC 2013</li> <li class="mb1">ICALP 2013</li> <li class="mb1">CATS 2013</li> <li class="mb1">APPROX 2012</li> <li class="mb1">SODA 2012</li> </ul> </article></main><footer><hr class="mv4 bb b--black-10"/><ul class="list db flex justify-center pl0 ma0 lh-copy sans-serif mv4 f5"><li class="dib mr2"><a href="/" class="link underline hover-dark-blue blue">home</a></li><li class="dib mr2"><a href="/papers/" class="link underline hover-dark-blue blue">papers</a></li><li class="dib mr2"><a href="/talks/" class="link underline hover-dark-blue blue">talks</a></li><li class="dib mr2"><a href="/cv/" class="link underline hover-dark-blue blue">c.v.</a></li><li class="dib mr2"><a href="/courses/" class="link underline hover-dark-blue blue">courses</a></li><li class="dib mr2"><a href="/contact/" class="link underline hover-dark-blue blue">contact</a></li><li class="dib mr2"><a href="/events/" class="link underline hover-dark-blue blue">events</a></li></ul></footer></div></body></html>