Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy
cs.CC
Submitted: 2026-11-06
Updated: 2026-11-06
Terminology
Sources
- Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
- Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
- Spherical Harmonics
- Convergence of SDP hierarchies for polynomial optimization on the hypersphere
- The sum-of-squares hierarchy on the sphere, and applications in quantum information theory
- On the number of connected components of random algebraic hypersurfaces
- Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
- Decomposition of the Kostlan--Shub--Smale model for random polynomials
- Most tensor problems are NP-hard
- The power of sum-of-squares for detecting hidden structures
- New SDP Roundings and Certifiable Approximation for Cubic Optimization
- An Argmax Principle for Sum-of-Squares Relaxations on the Sphere
- Statistics on Hilbert's Sixteenth Problem
- A hierarchy of eigencomputations for polynomial optimization on the sphere
- On the Number of Nodal Domains of Random Spherical Harmonics
- On Bernstein's inequality for polynomials
- An extension of Wick's theorem
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?