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: talks</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}::-webkit-file-upload-button{-webkit-appearance:button;font:inherit}a,article,body,div,footer,h1,html,li,main,nav,p,ul{box-sizing:border-box}.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}.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}.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-100{width:100%}.dark-gray{color:#333}.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}.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}.center{margin-right:auto;margin-left:auto}@media screen and (min-width:30em){.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"><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"><span class="dark-gray">talks</span></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"><h1 class="lh-title f3 dark-blue">2016</h1><p class="mt0 mb2"><a href="/talk/tensor/" class="blue hover-dark-blue link underline">Tensor decompositions, sum-of-squares proofs, and spectral algorithms</a><br/> <strong>Simons Institute in Berkeley.</strong> <a href="/talk/tensor.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="https://www.youtube.com/watch?v=kKRSYmfn7ys&index=3&list=PLYbY2kg6Mm3O0u1uck3NEa_mz_oaRgJXs" class="link b underline hover-dark-blue blue">VIDEO</a></p><h1 class="lh-title f3 dark-blue">2015</h1><p class="mt0 mb2"><a href="/talk/tensorpca/" class="blue hover-dark-blue link underline">Tensor principal component analysis via sum-of-squares</a><br/> <strong>COLT 2015.</strong> <a href="/talk/tensorpca.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><p class="mt0 mb2"><a href="/talk/sdpsize/" class="blue hover-dark-blue link underline">Lower bounds for semidefinite programming relaxations</a><br/> <strong>Midwest theory day.</strong> <a href="/talk/sdpsize.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="https://video.ias.edu/csdm/2015/1130-Steurer" class="link b underline hover-dark-blue blue">VIDEO</a></p><h1 class="lh-title f3 dark-blue">2014</h1><p class="mt0 mb2"><a href="/talk/soslearning/" class="blue hover-dark-blue link underline">Sum-of-Squares method, dictionary learning, and tensor decomposition</a><br/> <strong>Banff approximation workshop.</strong> <a href="/talk/soslearning.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="http://www.birs.ca/events/2014/5-day-workshops/14w5051/videos/watch/201408071105-Steurer.mp4" class="link b underline hover-dark-blue blue">VIDEO</a></p><p class="mt0 mb2"><a href="/talk/sosquest/" class="blue hover-dark-blue link underline">Sum-of-squares proofs and the quest towards optimal algorithms</a><br/> <strong>Dagstuhl Seminar 2014.</strong> <a href="/talk/sosquest.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><p class="mt0 mb2"><a href="/talk/cargese/" class="blue hover-dark-blue link underline">Sum-of-Squares method and approximation algorithms</a><br/> <strong>Cargèse workshop on combinatorial optimization.</strong> <a href="/talk/cargese.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><p class="mt0 mb2"><a href="/talk/sosrounding/" class="blue hover-dark-blue link underline">Rounding Sum-of-Squares Relaxations</a><br/> <strong>STOC 2014.</strong> <a href="/talk/sosrounding.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><h1 class="lh-title f3 dark-blue">2013</h1><p class="mt0 mb2"><a href="/talk/lpsize/" class="blue hover-dark-blue link underline">Approximate Constraint Satisfaction Requires Large LP Relaxations</a><br/> <strong>New York area theory day.</strong> <a href="/talk/lpsize.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="https://www.youtube.com/watch?v=pHpT4c4ekqU" class="link b underline hover-dark-blue blue">VIDEO</a></p><p class="mt0 mb2"><a href="/talk/newton/" class="blue hover-dark-blue link underline">The Unique Games Conjecture and Polynomial Optimization</a><br/> <strong>Isaac Newton Institute.</strong> <a href="/talk/newton.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="https://www.newton.ac.uk/seminar/20130730150016002" class="link b underline hover-dark-blue blue">VIDEO</a></p><p class="mt0 mb2"><a href="/talk/productgames/" class="blue hover-dark-blue link underline">Analytical Approach to Parallel Repetition</a><br/> <strong>Banff workshop on computational complexity.</strong> <a href="/talk/productgames.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="https://www.birs.ca/events/2013/5-day-workshops/13w5010/videos/watch/201307121003-Steurer.mp4" class="link b underline hover-dark-blue blue">VIDEO</a></p><h1 class="lh-title f3 dark-blue">2012</h1><p class="mt0 mb2"><a href="/talk/sdpschool/" class="blue hover-dark-blue link underline">Semidefinite Programming — Approximation & Complexity</a><br/> <strong>RWTH Aachen summer school on semidefinite optimization.</strong> <a href="/talk/sdpschool.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><p class="mt0 mb2"><a href="/talk/ugcsdp/" class="blue hover-dark-blue link underline">Semidefinite Programming Hierarchies and the Unique Games Conjecture</a><br/> <strong>Algorithmic Frontiers Workshop at EPFL.</strong> <a href="/talk/ugcsdp.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><p class="mt0 mb2"><a href="/talk/powersdp/" class="blue hover-dark-blue link underline">On the Power of Semidefinite Programming Hierarchies</a><br/>with Prasad Raghavendra. <strong>STOC 2012 Workshop on Unique Games Conjecture.</strong> <a href="/talk/powersdp.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><p class="mt0 mb2"><a href="/talk/hypercontract/" class="blue hover-dark-blue link underline">Hypercontractivity, Sum-of-Squares Proofs, and their Applications</a><br/> <strong>Georgia Tech theory seminar.</strong> <a href="/talk/hypercontract.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><h1 class="lh-title f3 dark-blue">2011</h1><p class="mt0 mb2"><a href="/talk/sdphierarchies/" class="blue hover-dark-blue link underline">Rounding Semidefinite Programming Hierarchies via Global Correlation</a><br/> <strong>FOCS 2011.</strong> <a href="/talk/sdphierarchies.pdf" class="link b underline hover-dark-blue blue">PDF</a> </p><h1 class="lh-title f3 dark-blue">2010</h1><p class="mt0 mb2"><a href="/talk/subexpug/" class="blue hover-dark-blue link underline">Subexponential Algorithms for Unique Games and Related Problems</a><br/> <strong>FOCS 2010.</strong> <a href="/talk/subexpug.pdf" class="link b underline hover-dark-blue blue">PDF</a> <a href="http://techtalks.tv/talks/subexponential-algorithms-for-unique-games-and-related-problems/1334/" class="link b underline hover-dark-blue blue">VIDEO</a></p></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>