Color Coding-Related Techniques
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Gives a concise comparison of three concrete algorithmic tools: color coding (randomized k-colorings plus 2^k dynamic programming entries), divide and color (recursive 2-coloring using n,k-universal families, yielding roughly 4^k deterministic routines and handling weights), and narrow sieves (multilinear detection + inclusion–exclusion over F2, fastest but randomized and poor for weights). Describes representative sets for pruning DP families, cites a black‑box construction that shrinks states, and reports a combined divide‑color + representative‑sets method that empirically improves directed k‑path running time.
AI-written summary · about
chapters (8)
- 0:00Color Coding-Related Techniques
- 2:10Color Coding: Directed k-Path Given a directed graph G, seek a path on k nodes.
- 6:00Divide-and-Color: Directed k-Path
- 8:57Multilinear Detection & Narrow Sieves Multilinear Detection: 1. Potential solution → Monomial.
- 12:37Narrow Sieves: Directed k-Path
- 15:26Representative Sets: Definition
- 18:09Representative Sets: Directed k-Path
- 23:22Mixing: Directed k-Path
related talks
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 00mCorrespondence Colouring of Random Graphs
06mThe 5 Colour Theorem
37m"Algorithms" is Not a Four-Letter Word
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
34mNew Tools for Peak Memory Scheduling
32mCompetitive Data Structure Dynamization
34mTesting Intersectingness of Uniform Families or how Dana and I intersected