Plan for the lecture

  • Finish faster exponential-time algorithms in small space — specifically inclusion–exclusion, the zeta transform and Möbius inversion 0:00.
  • Then switch, for the rest of this class and the next, to streaming and sketching — the lecturer's own research area 0:38.

The inclusion–exclusion fact (proved last time)

  • For all sets R ⊆ T: Σ_{R ⊆ S ⊆ T} (−1)^{|T − S|} = [R = T] 1:25.
  • Notation convention: a Boolean expression in brackets is 1 if true, 0 otherwise 1:25.

The zeta transform

  • For f mapping sets into some ring, the zeta transform is f̂(S) = Σ_{R ⊆ S} f(R) 2:07.

Last lecture's k-coloring claim

  • Let f(S) = [S is a non-empty independent set in G] 2:59.
  • Claim: G is k-colorable iff Σ_{S ⊆ V} (−1)^{|V − S|} · f̂(S)^k > 0 3:29, 4:19.
  • The scribe notes contain the direct inclusion–exclusion proof; the lecture instead derives the formula as a special case of something more general, because deriving is harder (and more useful) than verifying 4:46, 5:01.

Known bounds for computing the transform

BoundSpaceSource
O*(3^n) timepoly(n)brute force / this lecture 5:33
O*(2^n) timeO*(2^n)Yates's algorithm 5:33
O*(2.2461^n) timepoly(n)Björklund–Husfeldt–Koivisto (FOCS '06) 6:40
  • Two independent papers published at the same time give the O*(2^n)-style results: Björklund–Husfeldt (FOCS '06) and Koivisto (FOCS '06) — the second name is garbled as "Kowalczyk" in the auto-transcript 6:05, 6:40.
  • Open problem: achieve roughly 2^n time with polynomial space 7:16.