  The dynamic programming solution to the traveling salesman problem due to
Bellman, and independently Held and Karp, runs in time $O(2^n n^2)$, with no
improvement in the last sixty years. We break this barrier for the first time
by designing an algorithm that runs in deterministic time $2^n n^2 /
2^{\Omega(\sqrt{\log n})}$. We achieve this by strategically remodeling the
dynamic programming recursion as a min-plus matrix product, for which
faster-than-na\"ive algorithms exist.
