Cover Image

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Ye, Yuhan
Format:	Preprint
Published:	2026
Subjects:	Optimization and Control Computational Complexity Machine Learning 68Q27 (Primary), 90C60, 68Q17, 49J52, 52B55 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm
by: Ye, Yuhan, et al.
Published: (2026)

Learning Decision-Sufficient Representations for Linear Optimization
by: Ye, Yuhan, et al.
Published: (2026)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Undecidability of Translational Tiling with 2 Polycubes
by: Kim, Yoonhu
Published: (2025)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Blended Conditional Gradients: the unconditioning of conditional gradients
by: Braun, Gábor, et al.
Published: (2018)

Proof-Carrying Verification for ReLU Networks via Rational Certificates
by: Gokavarapu, Chandrasekhar
Published: (2025)

On the Hardness of Short and Sign-Compatible Circuit Walks
by: Borgwardt, Steffen, et al.
Published: (2024)

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
by: Schaefer, Marcus, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
by: Chan, Swee Hong, et al.
Published: (2023)

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method
by: Yang, Xiangyu, et al.
Published: (2021)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
by: Emmerich, Michael T. M., et al.
Published: (2026)

Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis
by: Chu, Hong T. M.
Published: (2026)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Solving Regularized Multifacility Location Problems with Unknown Number of Centers via Difference-of-Convex Optimization
by: Geremew, W., et al.
Published: (2026)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

On creating convexity in high dimensions
by: Johnston, Samuel G. G.
Published: (2025)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Think Thrice Before You Speak: Dual knowledge-enhanced Theory-of-Mind Reasoning for Persuasive Agents
by: Ma, Minghui, et al.
Published: (2026)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Weighted Automata and Logics Meet Computational Complexity
by: Kostolányi, Peter
Published: (2023)

Undecidability of Tiling the Plane with a Set of 5 Polyominoes
by: Kim, Yoonhu
Published: (2025)

How Does Machine Learning Manage Complexity?
by: Fortnow, Lance
Published: (2026)

Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)

Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
by: Pak, Igor, et al.
Published: (2025)

Vanishing of Schubert coefficients in probabilistic polynomial time
by: Pak, Igor, et al.
Published: (2025)

The Subspace Flatness Conjecture and Faster Integer Programming
by: Reis, Victor, et al.
Published: (2023)

From approximate to exact integer programming
by: Dadush, Daniel, et al.
Published: (2022)

Some asymptotic formulae for torsion in homotopy groups
by: Boyde, Guy, et al.
Published: (2023)

Homotopy connectivity of Čech complexes of spheres
by: Adams, Henry, et al.
Published: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Permanental rank versus determinantal rank of random matrices over finite fields
by: Ghasemi, Fatemeh, et al.
Published: (2025)

Optimal quantization with branched optimal transport distances
by: Pegon, Paul, et al.
Published: (2023)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Quantum Computing in Logistics and Supply Chain Management an Overview
by: Phillipson, Frank
Published: (2024)

Nonlocal loss of first homotopy in polyhedral approximations of Peano continua
by: Brazas, Jeremy, et al.
Published: (2025)