The Square Root Phenomenon in Planar Graphs -- Survey and New Results
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Survey of the square-root phenomenon in planar graphs: explains the pattern that many computational problems on planar graphs admit algorithms with running time roughly 2^{O(√n)} or n^{O(√n)}, surveys known results and techniques behind these bounds, and presents new formal results extending or tightening those square-root running-time guarantees for particular problems in the planar setting.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:46Better exponential algorithms
- 2:17Overview
- 3:10Chapter 1: Subexponential algorithms using treewidth
- 6:29Lower bounds based on ETH
- 10:05Lower bounds for planar problems
- 10:59Summary of Chapter 1
- 11:38Bidimensionality
- 13:53Planar Excluded Grid Theorem
- 19:40Summary of Chapter 2
- 20:54Chapter 3: Finding bounded-treewidth solutions
- 27:26Main paradigm
- 27:42Counting problems
- 29:38FPT techniques... for counting?
- 32:49Counting Triangulations
- 36:37Lower bounds, anyone?
- 39:24c-change TSP
- 49:11W[1]-hard problems
- 50:41GRID TILING and planar problems
- 51:49Independent Set for unit disks
- 54:36Reduction to unit disks
- 55:46Challenges
related talks
23mWorst-Case to Expander-Case Reductions
37m"Algorithms" is Not a Four-Letter Word
27mSuccinct Preferential Attachment Graphs
34mNew Tools for Peak Memory Scheduling
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
25mBit Complexity of Jordan Normal Form and Spectral Factorization
19mA Formal Disproof of Hirsch Conjecture
01h 31mCircuits of Bounded Depth