The Computational Benefit of Correlated Instances

on YouTube ↗32m

" summary

Defines a model where hard CSP instances come with extra correlated instances produced by small perturbations of the hidden solution, and studies two correlation types including the known-difference model. Main claims: for random CSPs, O(log n) correlated perturbed instances suffice to recover a solution that matches almost all constraints; with the differences revealed one can recover the exact solution for worst-case instances using shift encoding plus linear-algebraic decoding; without differences the problem reduces to solving noisy linear equations (LPN-like), requiring more elaborate voting and spectral methods.

AI-written summary · about

" chapters (14)

1. 0:00My Berkeley Days 1979-1982
2. 4:22What to Talk About?
3. 5:50The Algorithmic Benefit of Correlated Instances
4. 7:02Example: factoring integers
5. 8:33Correlated instances as a phenomenon
6. 10:07Model for correlated instances
7. 12:39Focus: Constraint satisfaction problems (CSP)
8. 15:03Correlated instances of CSPS
9. 18:02Random CSP: Correlated Instances Help: from Intractable to Tractable Theorem 1 (random CSP)
10. 18:46Worst Case CSP: Correlated Instance + Known Differences
11. 20:27Special Predicates, Two Instances Enough
12. 24:14Details - solving from many instances (Thm 1) not given the differences
13. 25:45Further results and questions 1. Did correlation only help because CSP is easy? No, PCP instances that succumb to correlation 2. Does Correlation Always Help? No and Yes
14. 28:58Why and when is collaboration beneficial?

" related talks

• 10mQuery, Communication and DiscrepancyMakrand Sinha · Meet the Fellows Welcome Event
• 26mPCPs and Instance Compression from a Cryptographic LensLiron Bronfman, Ron D. Rothblum · ITCS 2022
• 01h 03mSecure Computation 2Elette Boyle · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 31mCryptographic Hardness of Correlated SamplingRussell Impagliazzo · Minimal Complexity Assumptions for Cryptography 2023
• 01h 07mSomething about new average-case hard problems?Tselil Schramm · Obfuscation
• 29mImproved Deterministic Algorithms for Sparse Max-SATRahul Santhanam · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 24mCorrelation detection in trees for planted graph alignmentLuca Ganassali, Marc Lelarge, Laurent Massoulié · ITCS 2022
• 01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower BoundsArtur Czumaj · Sublinear Algorithms Boot Camp 2024