The Large Deviations of the Whitening Process in Random Constraint Satisfaction Problems

on YouTube ↗47m

" summary

Analyzes the whitening process in random constraint satisfaction problems, focusing on its large deviation properties. Uses probabilistic and statistical physics techniques to characterize atypical trajectories and rare events in how variables become forced or frozen under whitening. Targets random CSP ensembles and studies rates and mechanisms of deviations from typical whitening behavior.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 2:20Outline
3. 2:45An example of CSP
4. 13:14One more phase transition: rigidity
5. 17:07Frozen variables and algorithmic difficulty
6. 20:10Main results (0)
7. 23:49The idea of the computation
8. 28:49Main results (11)
9. 31:29Minimal contagious sets
10. 39:55Conclusions and perspectives

" related talks

• 24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin GlassesChris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi · ITCS 2023
• 58mSmoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And CertificatesPravesh K. Kothari · Rigorous Evidence for Information-Computation Trade-offs
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 47mExploiting Combinatorial Structure in Constraint Programming: ...Gilles Pesant · Satisfiability: Theory, Practice, and Beyond 2023
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013
• 01h 02mPrediction, Generalization, Complexity: Revisiting the Classical View from Statistics Part 2Ryan Tibshirani · Modern Paradigms in Generalization Boot Camp 2024
• 01h 02mTheory and Big DataRavi Kannan · Big Data Boot Camp 2013
• 01h 03mSampling Crash Course (continued)Andreas Eberle · Geometric Methods in Optimization and Sampling Boot Camp