3 papers
math.OC2026
Complexity of Output Feedback Stabilization
Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang +1
We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linea…
math.CO2026
Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust OR Polynomials
Ijay Narang, Yukai Tang
We introduce a robust OR polynomial framework for composing positive semidefinite certificates across OR constraints. We demonstrate the power of this method in two applications. T…
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…