{"id":"arxiv/2604.02285","url":"https://arxiv.org/abs/2604.02285","tags":["cs.CC","cs.DS","math.OC"],"score":0,"title":"The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization","domain":"cs.CC","source":"arxiv","authors":["Andreas Kontogiannis","Ioannis Panageas","Vasilis Pollatos"],"reviews":0,"subject":"cs.CC","summary":"The complexity of finding second-order stationary points (SOSPs) in constrained settings has remained unclear and has been highlighted as an open question by the works of Hollender and Zampetakis [2023] and Kontogiannis et al. [2024]. In particular, under one established definition (SOSP1) where nonnegative curvature is required only along the null space of the active constraints [Bertsekas, 1997], the problem lies in TFNP, and algorithms with $O(poly(1/ε))$ running times have been proposed. Under another established notion of stationarity (SOSP2) checking is coNP-hard in high dimensions. We…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-02","reactions":{}}