2 papers
cs.DS2026
A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting
Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang
We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perf…
math.OC2026
On Approximate Computation of Critical Points
Amir Ali Ahmadi, Georgina Hall
We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a…