From Channel Assignment to Subgraph Isomorphism
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows a concrete compression that encodes n bits into k log k via merging permutations, producing channel-assignment instances of size roughly n / log n and deriving ETH-based lower bounds for both general and L-bounded versions. Translates the same permutation-compression and a simpler one-to-many packing trick (a reduction from graph homomorphism to subgraph isomorphism) into a subgraph-isomorphism lower bound, yielding a near-tight exponential time barrier of roughly 2^{Ω(n sqrt(log n))} under ETH.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:15Graph Coloring Recall the Graph Coloring problem.
- 0:57The Channel Assignment problem.
- 1:52Algorithms for Channel Assignment
- 2:28CSP Hierarchy
- 3:04Permutation Encoding
- 6:31Naive Encoding
- 8:34Need some colors!
- 12:41Guessing is cheap
- 14:37Tight lower bound for Subgraph Isomorphism
- 15:01Back to the Channel Assignment
- 17:02Summary of Channel Assignment
related talks
27mHow to Compress Asymmetric Communication
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
55mSparsification Lemma and ETH
18mAutomated distribution of quantum circuits via hypergraph partitioning
35mSuperlinear Lower Bounds for Multipass Graph Processing
39mPolar Codes For Ids Channels
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)