<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><div class="gmail_default"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, May 24, 2021 at <b>11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA" target="_blank">register in advance here</a></font></b><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Subhash Khot, New York University</font></p><div><br></div><div><br></div><div><div dir="ltr"><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Title:</b>       Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Abstract:</b> Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif">The talk will provide an overview of these connections. It will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Bio: </b>Subhash Khot is a professor of computer science at the Courant Institute of Mathematical Sciences at New York University. His prior affiliations include Princeton University (PhD), Institute for Advanced Study (member), Georgia Tech (assistant professor) and University of Chicago (visiting professor). His research centers on computational complexity and its connections to geometry and analysis. He is a recipient of the National Science Foundation’s Alan T. Waterman Award, the International Mathematical Union’s Nevanlinna Prize, the Simons Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal Society.</font></div></div></div><div><br></div></div><div class="gmail_default"><div dir="auto"><div style="margin:0px;padding:0px 0px 20px;width:1120px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:369" style="direction:ltr;margin:8px 0px 0px;padding:0px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:1ro" style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div dir="auto"><div dir="auto"><b style="font-family:arial,sans-serif">Host:  </b><a href="mailto:madhurt@ttic.edu" target="_blank" style="font-family:arial,sans-serif"><b>Madhur Tulsiani</b></a><br></div></div></div></div></div></div></div><font face="arial, sans-serif">For more information on the colloquium series or to subscribe to the mailing list, please see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/colloquium.php</a>    </font></div><div class="gmail_default"><br></div><div class="gmail_default"><br style="color:rgb(80,0,80)"></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, May 24, 2021 at 10:08 AM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, May 24, 2021 at <b>11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA" target="_blank">register in advance here</a></font></b><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Subhash Khot, New York University</font></p><div><br></div><div><br></div><div><div dir="ltr"><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Title:</b>       Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Abstract:</b> Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif">The talk will provide an overview of these connections. It will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Bio: </b>Subhash Khot is a professor of computer science at the Courant Institute of Mathematical Sciences at New York University. His prior affiliations include Princeton University (PhD), Institute for Advanced Study (member), Georgia Tech (assistant professor) and University of Chicago (visiting professor). His research centers on computational complexity and its connections to geometry and analysis. He is a recipient of the National Science Foundation’s Alan T. Waterman Award, the International Mathematical Union’s Nevanlinna Prize, the Simons Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal Society.</font></div></div></div><div><br></div></div><div><div dir="auto"><div style="margin:0px;padding:0px 0px 20px;width:1120px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:369" style="direction:ltr;margin:8px 0px 0px;padding:0px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:1ro" style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div dir="auto"><div dir="auto"><b style="font-family:arial,sans-serif">Host:  </b><a href="mailto:madhurt@ttic.edu" style="font-family:arial,sans-serif" target="_blank"><b>Madhur Tulsiani</b></a><br></div></div></div></div></div></div></div><font face="arial, sans-serif">For more information on the colloquium series or to subscribe to the mailing list, please see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/colloquium.php</a>    </font></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, May 23, 2021 at 3:16 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, May 24, 2021 at <b>11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA" target="_blank">register in advance here</a></font></b><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Subhash Khot, New York University</font></p><div><br></div><div><br></div><div><div dir="ltr"><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Title:</b>       Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Abstract:</b> Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif">The talk will provide an overview of these connections. It will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Bio: </b>Subhash Khot is a professor of computer science at the Courant Institute of Mathematical Sciences at New York University. His prior affiliations include Princeton University (PhD), Institute for Advanced Study (member), Georgia Tech (assistant professor) and University of Chicago (visiting professor). His research centers on computational complexity and its connections to geometry and analysis. He is a recipient of the National Science Foundation’s Alan T. Waterman Award, the International Mathematical Union’s Nevanlinna Prize, the Simons Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal Society.</font></div></div></div><div><br></div></div><div><div dir="auto"><div style="margin:0px;padding:0px 0px 20px;width:1120px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:369" style="direction:ltr;margin:8px 0px 0px;padding:0px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:1ro" style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div dir="auto"><div dir="auto"><b style="font-family:arial,sans-serif">Host:  </b><a href="mailto:madhurt@ttic.edu" style="font-family:arial,sans-serif" target="_blank"><b>Madhur Tulsiani</b></a><br></div></div></div></div></div></div></div><font face="arial, sans-serif">For more information on the colloquium series or to subscribe to the mailing list, please see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/colloquium.php</a>    </font></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, May 17, 2021 at 6:39 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, May 24, 2021 at <b>11:10 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA" target="_blank">register in advance here</a></font></b><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font>Subhash Khot, New York University</font></p><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div><div dir="ltr"><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Title:</b>       Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Abstract:</b> Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif">The talk will provide an overview of these connections. It will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. It will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.<br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Bio: </b>Subhash Khot is a professor of computer science at the Courant Institute of Mathematical Sciences at New York University. His prior affiliations include Princeton University (PhD), Institute for Advanced Study (member), Georgia Tech (assistant professor) and University of Chicago (visiting professor). His research centers on computational complexity and its connections to geometry and analysis. He is a recipient of the National Science Foundation’s Alan T. Waterman Award, the International Mathematical Union’s Nevanlinna Prize, the Simons Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal Society.</font></div></div></div><div style="font-size:small"><br></div></div><div style="font-size:small"><div dir="auto"><div style="margin:0px;padding:0px 0px 20px;width:1120px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:369" style="direction:ltr;margin:8px 0px 0px;padding:0px"><div id="gmail-m_1117241056376363665gmail-m_3908025856904916274gmail-m_-5961120218729633681gmail-m_-8135693273282615331gmail-m_-2279937835116140568gmail-m_7998836102572585083gmail-m_-1807387322050756054gmail-m_3804487811790926557gmail-m_-1916303418504908038m_171242323807179252gmail-m_-8743081643725194343gmail-:1ro" style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div dir="auto"><div dir="auto"><b style="font-family:arial,sans-serif">Host:  </b><a href="mailto:madhurt@ttic.edu" style="font-family:arial,sans-serif" target="_blank"><b>Madhur Tulsiani</b></a><br></div></div></div></div></div></div></div><font face="arial, sans-serif" style="font-size:small">For more information on the colloquium series or to subscribe to the mailing list, please see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/colloquium.php</a>    </font></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div></div><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b><br></div><div><b><br></b></div><div><b><br></b></div><div><b><br></b></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>