Dense Subset Sum May Be the Hardest
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Examines the computational difficulty of dense instances of Subset Sum, comparing them to other hard problems; discusses lower bounds and tight algorithmic results in the context of parameterized and exponential-time complexity, focusing on Dense Subset Sum as a candidate for the hardest case.
AI-written summary · about
chapters (6)
- 0:00Start
- 0:21Complexity of NPC problems
- 2:10Worst Case Subset Sum
- 9:49Average Case Subset Sum
- 27:08Open Question 4: Orthogonal Vectors
- 28:23Uniquely Decodable Code Pairs (UDCP)
related talks
01h 32mInapproximability of Constraint Satisfaction Problems I
25mOn computing homological hitting sets
01h 01mComplexity and Algorithmic Game Theory I
34mNew Tools for Peak Memory Scheduling
23mWorst-Case to Expander-Case Reductions
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
17mLifting to Parity Decision Trees Via Stifling
19mLook Ma, I Know My Algorithms!