4 papers · 1 filter
An optimal deterministic algorithm for finding a strict saddlepoint
Justin Dallant
Given an matrix , a saddlepoint of is an entry that is the maximum in its row and the minimum in its column. It is a strict saddlepoint if no other entry in its…
Quantum Space-Time Tradeoffs for TSP and Hypercube Path via Extremal Set Systems
Justin Dallant
We give a quantum analogue of the extremal set-system framework introduced by Ameli, Nederlof and Wang (FOCS 2026) and Dallant and Kozma (FOCS 2026) for space-time tradeoffs in TSP…
Optimal chain density, entropy, and space-time tradeoffs for the TSP
Alexandr Andoni, Justin Dallant, László Kozma +1
We nearly settle a natural extremal question about set systems over : the tradeoff between the {size} (number of sets) and the number of {full chains}. This question was initi…
Improved space-time tradeoff for TSP via extremal set systems
Justin Dallant, László Kozma
The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximat…