3 papers
cs.DS2026
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang
We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem…
cs.DS2026
An Invitation to "Fine-grained Complexity of NP-Complete Problems"
Jesper Nederlof
Assuming that P is not equal to NP, the worst-case run time of any algorithm solving an NP-complete problem must be super-polynomial. But what is the fastest run time we can get? B…
cs.CC2025
Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
Kacper Kluk, Jesper Nederlof
We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveli…