The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions
cs.DS, cs.DM, math.CO
Submitted: 2026-11-02
Updated: 2026-11-02
Terminology
Sources
- A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity
- Sublinear Algorithms for MAXCUT and Correlation Clustering
- Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians
- Product-state Approximations to Quantum Ground States
- Subsampling Mathematical Relaxations and Average-case Complexity
- A Faster Algorithm for Max Cut in Dense Graphs
- Tolerant Bipartiteness Testing in Dense Graphs
- Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
- Limits of CSP Problems and Efficient Parameter Testing
- A vector-contraction inequality for Rademacher complexities
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles