We prove that the active-set method needs an exponential number of iterations in the worst-case to maximize a convex quadratic function subject to linear constraints, regardless of the pivot rule used. This substantially improves over the best previously known lower bound [IPCO 2025], which needs objective functions of polynomial degrees \(\omega(\log d)\) in dimension \(d\), to a bound using a convex polynomial of degree 2. In particular, our result firmly resolves the open question [IPCO 2025] of whether a constant degree suffices, and it represents significant progress towards linear objectives, where the active-set method coincides with the simplex method and a lower bound for all pivot rules would constitute a major breakthrough.

Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new algorithm analysis framework that we call by-the-book analysis. In contrast to earlier frameworks, by-the-book analysis not only models an algorithm's input data, but also the algorithm itself. Results from by-the-book analysis are meant to correspond well with established knowledge of an algorithm's practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances. We apply our framework to the simplex method, an algorithm which is beloved for its excellent performance in practice and notorious for its high running time under worst-case analysis. The simplex method similarly showcased the previous state of the art framework smoothed analysis (Spielman and Teng, STOC'01). We explain how our framework overcomes several weaknesses of smoothed analysis and we prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time. Our results provide analytical justification for these features which are common to all high-quality simplex method implementations.

Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis. Spielman and Teng (STOC ’01) introduced the smoothed analysis framework of algorithm analysis and applied it to the simplex method. Given an arbitrary linear program with d variables and n inequality constraints, Spielman and Teng proved that the simplex method runs in time O(σ−30d55n86), where σ > 0 is the standard deviation of Gaussian distributed noise added to the original LP data. Spielman and Teng’s result was simplified and strengthened over a series of works, with the current strongest upper bound being O(σ−3/2d13/4log(n)7/4) pivot steps due to Huiberts, Lee and Zhang (STOC ’23). We prove that there exists a simplex method whose smoothed complexity is upper bounded by O(σ−1/2d11/4log(n)7/4) pivot steps. Furthermore, we prove a matching high-probability lower bound of Ω(σ−1/2d1/2ln(4/σ)−1/4) on the combinatorial diameter of the feasible polyhedron after smoothing, on instances using n = ⌊(4/σ)d⌋ inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors.

Given a convex set Q ⊆ ℝm and an integer matrix W ∈ ℤm×n, we consider statements of the form ∀b ∈ Q ∩ ℤm ∃x ∈ ℤn s.t. Wx ≤ b. Such statements can be verified in polynomial time with the algorithm of Kannan and its improvements if n is fixed and Q is a polyhedron. The running time of the best-known algorithms is doubly exponential in n. We provide a pseudopolynomial-time algorithm if m is fixed. Its running time is (mΔ)O (m2 ) where Δ is the largest absolute value of an entry in W. Furthermore it applies to general convex sets Q.