About

Going beyond worst-case complexity, there have been exciting developments in the understanding of complexity of random instances of CSPs such as: (1) Refutation of random CSPs: The method of Kikuchi matrices has led to new algorithms for refutation, and resolution of related conjectures on hypergraphs. (2) Hardness thresholds and limits of local algorithms for random CSPs have been identified via overlap gap property and low-degree hardness. This workshop will present results from these two lines of work, and related results.

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.

Chairs/Organizers
Register

Registration is required for in-person attendance, access to the livestream, and early access to the recording. Space may be limited, and you are advised to register early. 

For additional information please visit: https://simons.berkeley.edu/participating-workshop.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials.