<div dir="ltr"><div><div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><span style="color:rgb(34,34,34);font-size:large;word-spacing:0px">******************************</span><span style="color:rgb(34,34,34);font-size:large;word-spacing:0px">******************************</span><span style="color:rgb(34,34,34);font-size:large;word-spacing:0px">**************************</span><b><br></b></font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b><br></b></font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Date:</b> February 25, Wednesday</font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Time: </b>12:30pm CT</font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Location: </b>JCL 390</font></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><b><font style="font-size:1.125rem"><br></font></b></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><b><font style="font-size:1.125rem">Speaker:  Juspreet Singh Sandhu (Harvard)</font></b></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font size="4"><br></font></div><b style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem">Title: </font></b><font size="4">Local Quantum Algorithms and the Overlap Gap Property</font></div><div><b style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><br></font></b></div><div><span style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/94899452899?pwd=QmN0M28waDYzeHRtQjVwMU1XYzNKUT09">link</a>]</font></span></div><div><br></div><div><div dir="auto"><font style="color:rgb(49,49,49);font-size:1.125rem;word-spacing:1px"><b style="font-size:1.125rem">Abstract: </b></font><font size="4">We briefly give an overview of a recent result in which we obstruct all _local_ algorithms (classical or quantum) on almost all instances of _any_ constraint satisfaction problem that satisfies a peculiar property called the coupled-Overlap Gap Property. Our results rely on using some involved combinatorics and a martingale argument to prove strong concentration properties of a notion of local algorithm we term \"generic local\" - This notion subsumes local classical and local quantum algorithms.</font></div><font size="4"><br>The work is closely motivated by and/or tied to some interesting open questions at the intersection of Spin Glass Theory, Quantum inapproximability, Random & Algebraic Graph Theory and the Average-Case Complexity of CSPs. We mention some of these questions, which are currently ongoing work with collaborators at Bocconi University, ETH Zurich and University of Chicago.<br><br>Based on joint work with Chi-Ning Chou, Peter J. Love & Jonathan Shi.</font></div></div><div><font size="4"><br></font></div><div><span style="font-size:large">[<a href="https://orecchia.net/event/theory-lunch/" target="_blank">Theory Lunch Webpage</a>]<br>[<a href="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" target="_blank">Theory Lunch Calendar</a>]</span></div><div dir="auto"><font size="4"><br></font></div><div dir="auto"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span></div></div>