Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width

Prelegent(ci)

Kacper Kluk

Język referatu

angielski

Termin

20 lutego 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveling Salesperson Problem. Our lower bounds are higher than the currently fastest algorithms that rely on algebra and give evidence that these algebraic aspects are unavoidable for competitive worst case running times. Specifically, we study input graphs with a small width parameter such as treewidth and pathwidth and show that for any k there exists a graph  of pathwidth at most k and k^O(1) vertices such that any tropical circuit calculating the optimal value of a Traveling Salesperson round tour uses at least 2^Omega(k log k) gates. We establish this result by linking tropical circuit complexity to the nondeterministic communication complexity of specific compatibility matrices.

This is a joint work with Jesper Nederlof

---