Stochastic Integration via Error-Correcting Codes
summary
Proposes estimating a partition function by taking medians of maxima over random subsets defined as solutions to linear parity systems, using a generator matrix to turn the search into optimization over a smaller cube. Replaces dense random parities with LDPC parity constraints that preserve pairwise independence–like behavior, keep variance low, and remain solver-friendly; integrates with SAT/local-search and CPLEX. Achieves a 32-approximation, matches long-parity accuracy on benchmarks, scales to thousands of variables and reports up to 1000x speedup in practice.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:31Setting
- 1:37Quality Guarantee
- 2:26General Idea
- 4:27Thought Experiment
- 13:16Recap
- 15:40Linear error correcting codes
- 23:26Maximizing unconstrained optimization
- 23:40Blackbox
- 25:58Satisfiability
- 26:34Low Density ParityCheck Codes
- 30:29Conditional Probability
- 32:40Computational Complexity
- 34:40ErrorCorrecting Codes
- 36:35Running Time
- 37:37Experimental Results
related talks
43mCoded matrix computation: numerical stability, partial stragglers and sparse input matrices
31mStatistical Estimation on Graphs
51mRandom Projections for Probabilistic Inference
32mApproximate coding computing
12mIterative Methods and High-Dimensional Statistics
25mLucky Talk: From Coding to Clustering
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4