Improved Deterministic Algorithms for Sparse Max-SAT

on YouTube ↗29m

" summary

Deterministic algorithms give explicit savings for sparse Max-SAT: savings Ω(n/c) (polynomial space) and savings n/√c (exponential space) for formulas with m = c·n clauses, improving prior c-dependent bounds. Approach uses greedy branching on the most frequent variable, a modified simplification where leaves are 1-CNF (or 2-CNF to invoke Williams' max-2-SAT subroutine), a global concentration lemma (Håstad-style switching ideas) and measure-and-conquer to remove excessive k dependence. The routines are constructive and yield the stated running-time exponents.

AI-written summary · about

" chapters (8)

1. 0:00Problem definition
2. 1:16Understanding algorithm savings
3. 3:55Main result overview
4. 6:12Branching algorithm basics
5. 11:50Adapting to max-SAT
6. 16:07Analysis and concentration
7. 22:18Measure and conquer
8. 25:25Conclusion and discussion

" related talks

• 17mSatisfiability Algorithms Based on Concentrated ShrinkageRuiwen Chen · Connections Between Algorithm Design and Complexity Theory
• 01h 07mSatisfiability Algorithms IMohan Paturi · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 56mSatisfiability Algorithms IIMohan Paturi · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 47mAnalysis of Core-Guided MaxSat Using Cores and Correction SetsNina Narodytska · Satisfiability: Theory, Practice, and Beyond 2023
• 58mCircuit Complexity and Connections IRyan Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 01h 01mCircuit Complexity and Connections IIRyan Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 55mSparsification Lemma and ETHMohan Paturi · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 01h 09mCircuit Analysis AlgorithmsRyan Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015