The Computational Benefit of Correlated Instances
summary
Two theoretical papers claim concrete speedups when many instances share structure: for Boolean constraint‑satisfaction, order log n auxiliary instances produced by flipping solution bits let a polynomial‑time algorithm recover a close (random case) or exact (worst case when given bit‑difference locations) solution via solving sparse linear systems; for string similarity (LCS, edit, DTW) mapping each position to an O(log n)-bit vector and using hashing on O(log n)-bit vectors plus nearest‑neighbor tools drops running time well below Θ(n^2). Results require specific perturbation/correlation models and are validated only theoretically.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:45What is this about
- 2:08Factoring integers
- 4:55Examples
- 6:15Algorithms
- 7:58Model
- 11:16Rules of Thumb
- 14:30Constraint Satisfaction
- 19:02Correlations
- 33:56Dynamic Time
- 35:42Finegrained Complexity Theory
- 37:09Strict Model
- 42:23Relaxed Model
- 43:49Algorithm
- 45:12Matches
- 49:35Smooth analysis
related talks
01h 00mAverage-case Complexity for Polynomials, and All That
38mSome Easy Optimization Problems Have the Overlap-Gap Property
01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
57mIt ain't over till it's over
01h 05mNearest Neighbor Methods I
42mLearning What Works Best When
11mFinding Friends in High Dimensions...