<div dir="ltr"><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><font face="arial, helvetica, sans-serif"><b>When:</b>     Friday, May 31st. Refreshments at noon. Talk begins at 12:20pm. <br></font><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><span style="font-family:arial,helvetica,sans-serif"><b>Where:</b>    </span><span style="font-family:arial,helvetica,sans-serif">TTIC</span><span style="font-family:arial,helvetica,sans-serif">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><div><p style="margin-bottom:0.0001pt;line-height:normal"><font face="arial, helvetica, sans-serif"><b>Who: </b>      </font>Madhur Tulsiani, TTIC</p><table cellpadding="0" style="border-collapse:collapse;margin-top:0px;width:auto;font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:0.875rem;letter-spacing:0.2px;display:block"></table></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b>Title: </b>       </font><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">CSPs and Expansion</span></div><div><span style="text-align:justify"><font face="arial, helvetica, sans-serif"><br></font></span></div><div style="text-align:justify"><font face="arial, helvetica, sans-serif"><b>Abstract: </b></font><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">Constraints Satisfaction Problems (CSPs) play an important role in the theory of approximability. They provide an important benchmark combinatorial optimization problem for algorithms, as well as equivalent formulations of questions about Probabilitically Checkable Proofs (PCPs) which are used to prove lower bounds on approximability.</span></div><div style="text-align:justify"><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif"><br></span></div><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">It is relatively well understood that if an instance of a 2-CSP (having two variables in each constraint) is considered as a graph, then the expansion of this graph can be exploited by approximation algorithms - I will discuss some instances of this which led to new algorithms in the past.</span></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><br style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif"><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">I will also discuss new notions of expansion (for hypergraphs) defined recently (known as high-dimensional expansion) which can be exploited by algorithms for k-CSPs for k > 2. I will also discuss applications of these algorithmic results to questions in coding theory.</span></div><div style="font-family:arial,sans-serif;color:rgb(0,0,0)"><br style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif"><span style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">Most of the new results I will discussed are based on joint works with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava.</span><br style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif"><div style="text-align:justify"><br></div><div style="font-size:13px;margin:0px;line-height:normal"><b style="font-size:12.8px"><font face="arial, helvetica, sans-serif">******************************************************************************************************</font></b><br></div><div style="font-family:arial;font-size:13px;margin:0px;line-height:normal"><div style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif">Research at TTIC Seminar Series</font></b></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" style="font-family:arial,sans-serif;text-decoration-line:none" target="_blank">https://groups.google.com/a/ttic.edu/group/talks/subscribe</a></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" style="font-family:arial,sans-serif;text-decoration-line:none" target="_blank">http://www.ttic.edu/tticseminar.php</a>.</font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" style="font-family:arial,sans-serif;text-decoration-line:none" target="_blank">nati@ttic.edu</a>.</font></div></div></div><div><br></div>-- <br><div dir="ltr" class="m_-7659244977616821476gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 518</i></div><div><font color="#0b5394"><i>Chicago, IL 60637</i></font></div></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div>