[Theory] [Theory Lunch] Juspreet Singh Sandhu (Harvard), Wednesday 2/25 12:30pm-1:30pm, JCL 390.

[Antares Chen]

************************************************************
**************************

*Date:* February 25, Wednesday
*Time: *12:30pm CT
*Location: *JCL 390

*Speaker:  Juspreet Singh Sandhu (Harvard)*

*Title: *Local Quantum Algorithms and the Overlap Gap Property

*Zoom: *[link
<https://uchicago.zoom.us/j/94899452899?pwd=QmN0M28waDYzeHRtQjVwMU1XYzNKUT09>
]

*Abstract: *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.

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.

Based on joint work with Chi-Ning Chou, Peter J. Love & Jonathan Shi.

[Theory Lunch Webpage <https://orecchia.net/event/theory-lunch/>]
[Theory Lunch Calendar
<https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220221/0b292afc/attachment.html>