3 papers
cs.DS2026
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Sergei Kudria, Jason Luo, Mahbod Majid
We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of…
math.CO2026
Beyond halfway to Hadwiger's conjecture
Chun-Hung Liu, Jason Luo
Hadwiger conjectured in 1943 that every graph with no minor has chromatic number at most . Delcourt and Postle proved that every graph with no minor has chromatic…
quant-ph2026
Tight Lower Bounds for State Tomography with Limited Entanglement
Ufuk Keskin, Jason Luo, Mahbod Majid +1
We study state tomography when each measurement acts on at most fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound i…