A New Conjecture on Hardness of Low-Degree 2-CSP’s with...
summary
Conjectures that a d-to-d bipartite 2-CSP conjecture with d = 2^{log^{ε} n}, completeness 0.5 and soundness s = 2^{-log^{0.5+ε} n} is NP-hard, and shows this implies a 2^{log^{ε} n}-factor hardness for DkS (a subpolynomial gap between previous superconstant and near-polynomial results). The reduction builds a global assignment graph by replacing each CSP variable with a gadget and planting assignment truth tables, then uses a hypothesized DkS oracle recursively plus decomposition and preprocessing to distinguish yes and no instances.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:10Density Subgroup Problem
- 5:05approximation equivalence
- 7:24equivalence in approximation results
- 10:07new conjecture
- 13:27Gap problem
- 17:45Remarks
- 18:45Proof
related talks
01h 16mIn Search of the Hard Instances
40mUtilizing Structure in Combinatorial Solving and Reasoning
29mGraph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
35mClique is hard on average for unary Sherali-Adams
59mThe Proof Complexity of Integer Programming
30mOn Bounded Depth Proofs For Tseitin Formulas On The Grid; Revisited
48mBeyond SAT - Proofs for QBF, and more
01h 01mCDCL SAT Solving and Applications to Optimization Problems