|
Home
| Subject Search
| Help
| Symbols Help
| Pre-Reg Help
| Final Exam Schedule
| My Selections
|
Searched for: 1 subject found.
6.1420 Fixed Parameter and Fine-grained Computation
(
)
Prereq: 6.1200, 6.1210, and (6.1220, 6.1400, or 18.404)
Units: 3-0-9
An overview of the theory of parameterized algorithms and the "problem-centric" theory of fine-grained complexity, both of which reconsider how to measure the difficulty and feasibility of solving computational problems. Topics include: fixed-parameter tractability (FPT) and its characterizations, the W-hierarchy (W[1], W[2], W[P], etc.), 3-sum-hardness, all-pairs shortest paths (APSP)-equivalences, strong exponential time hypothesis (SETH) hardness of problems, and the connections to circuit complexity and other aspects of computing.
V. Vassilevska Williams
| ||||||||
