Computational Complexity of Polynomial Time Problems: Introduction
summary
Overview of fine-grained complexity that pins down why many polynomial-time problems resist improvement: conjectures named are ETH/SETH, 3SUM, orthogonal vectors and APSP; reductions preserve exponent improvements via fine-grained reductions rather than polytime preservation; key construction is a split-and-list reduction from k-CNF to orthogonal vectors producing about 2^{n/2} vectors of dimension ≈n, so subquadratic OV would give faster-than-2^n SAT; web of equivalences links string, geometric, graph and dynamic problems and implicates combinatorial BMM limits.
AI-written summary · about
chapters (17)
- 0:00Start
- 0:46The real world and easy problems
- 3:23In theoretical CS polynomial time = efficient/easy.
- 4:25The "easy" problems
- 4:39What do we know about O(N2) time?
- 7:47Sequence alignment A fundamental problem from computational biology Given two DNA strings
- 8:41Longest Common Subsequence
- 12:42Why are we stuck
- 13:12A canonical hard problem
- 14:14Why is K-SAT hard?
- 15:31Addressing the hardness of easy problems
- 16:58CNF SAT is conjectured to be really hard
- 23:05Orthogonal vectors (OV): Given a set of n vectors
- 27:38Fine-grained reductions
- 49:24Another popular conjecture
- 51:50BMM conjecture consequences
- 55:48Which conjectures are more believable?
related talks
01h 21mComputational Complexity in Theory and in Practice
29mAn Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
10mQuery, Communication and Discrepancy
23mTowards General and Tight Hardness Results for Graph Problems
35mSuperlinear Lower Bounds for Multipass Graph Processing
25mLower Bounds for Problems Parameterized by Clique-width
29mImproved Deterministic Algorithms for Sparse Max-SAT