Random Combinatorial Matrices

on YouTube ↗50m

" summary

Proves that sparse random F2 matrices (Bernoulli model) are replica symmetric but not strongly: for density D>e the posterior overlap concentrates but randomly flips between two values α_lower and α_upper instead of a single deterministic limit. Main tools are the pinning lemma, a fixed‑point equation for the fraction of frozen variables, and an explicit combinatorial construction using warning propagation that identifies slush variables freeze with probability 1/2. Results match known satisfiability thresholds and are rigorously established.

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 6:02Bayes-optimal inference problems
3. 14:40Sparse random matrices
4. 21:13The nullity
5. 28:19The Bernoulli matrix
6. 42:39Contributions

" related talks

• 58mRandom Constraint Satisfaction ProblemsNike Sun · Counting Complexity and Phase Transitions Boot Camp
• 29mExtended Formulations and Information ComplexityAnkur Moitra · Information Theory in Complexity Theory and Combinatorics 2015
• 01h 00mMatrix Rank – Extensions, Applications and Open ProblemsAvi Widgerson · Geometric Complexity Theory 2014
• 01h 03mDecay of Correlations in Spin SystemsYitong Yin · Counting Complexity and Phase Transitions Boot Camp
• 01h 02mApproximate Counting ILeslie Ann Goldberg · Counting Complexity and Phase Transitions Boot Camp
• 30mA New Look at Gallager's BoundsNati Linial · Information Theory in Complexity Theory and Combinatorics 2015
• 23mExtending Symmetric CircuitsGregory Wilsenach · Symmetry, Logic, Computation 2016
• 24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for TuringRan Raz, Kunal Mittal · ITCS 2021