Pith. sign in

REVIEW 2 major objections 4 minor 51 references

An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An argmax principle over high pseudo-moments yields degree-O(sqrt(n/eps)) SoS algorithms for Best Separable State, multiplicative 2->4 norm approximation, and a shorter proof of the known sphere-polynomial convergence bound.

desk verdict Argmax principle is genuinely new and the BSS/2→4 results are solid, but Theorem 1.3 overclaims rational p→q — the body only proves even integer p. read the letter →

arxiv 2608.02594 v1 pith:LN4CHVZQ submitted 2026-08-03 cs.CC quant-ph

Fernando Jeronimo Granha , Pei Wu , Haochen Xu This is my paper · ORCID
classification cs.CCquant-ph
keywords degree-givesargmaxconvergenceepsilonpreviouslyprincipleapproximation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Many hard optimization problems can be framed as maximizing a polynomial over the unit sphere. Sum-of-squares (SoS) relaxation replaces the search over actual vectors with a search over pseudo-distributions: formal moment sequences that obey the constraints in an algebraic sense. If such a pseudo-distribution exists with large objective, one still has to round it to an actual vector. This paper proposes a simple way to read a pseudo-distribution: build the polynomial Phi_k(v) = E~[^{2k}] that measures how strongly the pseudo-distribution points in direction v, and take its maximizer u. Because u is optimal, first and second derivative conditions along the sphere force the pseudo-distribution to concentrate near u after a reweighting. This concentration is exactly what is needed to prove approximation guarantees. The same principle is used three times. For Best Separable State, it gives a degree-O(sqrt(n/eps)) SoS algorithm in the perfect-completeness regime, improving the prior O~(sqrt(n)/eps^2) analysis and matching ETH-based hardness for inverse-linear gaps. For the matrix 2->4 norm, the same mechanism gives a multiplicative (1+eps)-approximation with degree O(sqrt(n)/eps), upgrading a previous constant-gap decision algorithm. For degree-d polynomial optimization, the argmax is chosen over folds rather than directions, and it recovers a known O_d((n/k)^{d/2-1}) convergence bound with a shorter proof. The paper introduces no new relaxation; it gives a new way to analyze existing SoS relaxations.
Extended reading notes

Core claim

The load-bearing principle is: 'The argmax of a high-moment polynomial built from a feasible pseudo-expectation is a rounding object for understanding SoS convergence.' Concretely, Theorems 1.1-1.4 claim: degree-O(sqrt(n/eps)) SoS decides the (1,1-eps) Best Separable State gap problem; degree-O(sqrt(n)/eps) SoS gives a multiplicative (1+eps)-approximation for the matrix 2->4 norm; and degree-O(k) SoS gives approximation ratio O_d((n/k)^{d/2-1}) for degree-d polynomial optimization on the sphere.

Load-bearing premise

The proofs treat pseudo-expectations and SDP solvers as exact: every constraint is enforced exactly, and the reweighing denominator eE[w] is assumed strictly positive with no numerical error. All rounding algorithms are analyzed under exact real arithmetic; the paper gives no stability or approximate-SDP error analysis. In practice an SoS solver returns an eps-feasible pseudo-expectation, and the derived bounds (e.g., Theorems 3.6, 4.5, 5.6) have no margin to absorb solver error. This premise enters in Section 2.3 (real-arithmetic SDP model) and in Algorithms 3.1, 4.1, and 5.1.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops an 'argmax principle' for analyzing sum-of-squares relaxations on the sphere: from a feasible pseudo-expectation Ẽ, form a high-moment polynomial (e.g., Φ_k(u)=Ẽ⟨x,u⟩^{2k}, or a fold-based analogue), then use a maximizer of this polynomial as the rounding object; first/second-order or global optimality conditions convert into reweighed moment inequalities that drive the convergence analysis. Applications: (1) perfect-completeness Best Separable State, where a degree-O(√(n/ε)) SoS is shown to distinguish h_sep=1 from h_sep≤1−ε through the rank-one-subspace reduction, with an ETH-based tightness discussion for inverse-linear gaps; (2) the projector 2→4 norm, where degree-O(√n/ε) SoS gives a (1+O(ε))-multiplicative approximation via a threshold relaxation and binary search, plus an existential rounding proof and a claimed deterministic finite-search rounding; (3) degree-d polynomial optimization, where a fold-selection argument with pseudo-Hölder and spherical-moment identities recovers the BGG+17 bound O_d((n/k)^{d/2−1}). The paper also advertises an extension to p→q norms for rational p and even q (Theorem 1.3), and works throughout in the exact real-arithmetic SDP model.

Significance. The argmax principle is genuinely unifying, and the paper is rich in verifiable content: explicit derivative identities (3.3)–(3.6), the reweighing/block-PSD residual bound in Theorem 3.6, argmax concentration Lemma 4.4, the Bernstein-grid discretization, and the pseudo-Hölder/polarization machinery of Section 6 all come with explicit constants and complete proofs. If the main theorems stand after the fixes below, the contributions are substantial: an essentially tight BSS degree with a proof simpler than BKS17; a (claimed) first multiplicative (1+ε)-approximation for the projector 2→4 norm in subexponential time; and a short proof of the BGG+17 convergence rate. The paper introduces no new relaxation, involves no fitting, and is free of circularity. However, the advertised rational-p extension is not proved in the body, and a numerical inequality in the finite-search rounding proof is false; the stated scope therefore needs correction.

major comments (2)
  1. [Section 1.1 Theorem 1.3 vs. Section 5 / Theorem 5.2 / Lemma 5.1] Theorem 1.3 advertises p→q-norm approximation for every rational 1<p<q with even q, but the body proves only even integers: Section 5 opens with 'fixed even integers 2≤p<q' and disclaims 'the mixed regime 1<p<2<q'. Evenness is load-bearing: Lemma 5.1 encodes the ℓ_p ball by g_p(x)=1−Σ_j x_j^p, a valid SoS certificate only for even p. For p=3, x=(−2,0) satisfies g_3(x)=9>0 but ∥x∥_3=2>1, so (5.4a) does not enforce the intended constraint; for non-integer rational p, x_j^p is not a polynomial and (5.4) is undefined. Note p=3/2, q=4 is exactly the disclaimed regime. Fix: restrict Theorem 1.3 and the abstract to even integers 2≤p<q (matching Theorem 5.2), or supply a different relaxation for rational p.
  2. [Section 4.6, Theorem 4.14, Eq. (4.34)] The asserted bound 4Δ_α/τ^{3/4} ≤ (ε/16)τ^{1/4} is false. With (4.32), α=ε²τ²/216 (when the min is active), and (4.27), Δ_α=2√α/(1−α), so 4Δ_α/τ^{3/4} = (8ετ/(6√6))/((1−α)τ^{3/4}) ≥ (4/(3√6))ετ^{1/4} ≈ 0.544ετ^{1/4} > (ε/16)τ^{1/4}; the τ-dependence cancels, so no regime makes the inequality true. Consequently the derivation of τ^{1/4}−a ≤ (ε/4)τ^{1/4} collapses. Corollary 4.6 and Theorem 4.1 do not use Algorithm 4.2 and are unaffected, but the advertised deterministic finite-search rounding needs a corrected parameter, e.g., α=Θ(ε²τ^{3/2}) with a small constant, which still gives polynomial 1/α for τ≥1/n.
minor comments (4)
  1. [Section 2.3; Algorithms 3.1, 4.1, 5.1] The paper works in the exact real-arithmetic SDP model and assumes pseudo-expectations are exactly feasible with positive reweighing denominators. This is a standard convention, and it is disclosed, but the guarantees (e.g., (3.6), (4.16), (5.19)) have no slack for solver error; a stability analysis would strengthen the algorithmic claims.
  2. [Section 5] Notation: w denotes both the reweighing weight (Sections 3–4) and the p∗-unit direction maximizing Φ_k in Section 5; s similarly denotes both ⟨x,u⟩ and ⟨w,x⟩. Distinct symbols would considerably improve readability.
  3. [Theorem 1.3] Once Theorem 1.3 is restricted to even p (see Major 1), the parameter λ(p)=max{p,2} is never used and could be removed from the statement.
  4. [Appendix A, proof of Theorem 3.8] The line 'Choose a universal constant 2√2 δ0 < 1 − 1/√2' is garbled (presumably 2√2·δ0 < 1 − 1/√2); please fix the typesetting. The same passage would benefit from a pointer to the exact trust-region assumption labels of [BAC19].
Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The central claims rest on standard SoS machinery, standard spherical-moment and polarization facts, a black-box Riemannian optimization theorem, and ETH. No free parameters are fitted to data, and no new entities are introduced. The only scope mismatch is that the intro's rational-p p->q theorem is not supported by the body's even-p proof.

assumptions (8)
  • standard math The pseudo-expectation/SoS framework is consistent, including positivity, pseudo-Cauchy-Schwarz, and reweighing that preserves constraints at reduced degree.
    Invoked throughout Section 2.3 and used in every proof.
  • standard math Univariate nonnegative even polynomials are SOS, and x^T B x for B>=0 is SOS.
    Used in Fact 2.2, Lemma C.2, and Lemma 5.1.
  • standard math Spherical moment identities and the lower bound c_{n,k} >= sqrt(k/(3en)) for 2<=k<=n.
    Lemma C.4 is central to Sections 3, 4, 5, and 6.
  • standard math The pseudo-Holder log-convexity lemma (Lemma C.5).
    Used in the degree-d polynomial optimization proof, Section 6.2.
  • standard math The polarization lemma for symmetric multilinear forms (Banach) with loss factor d!/d^d.
    Lemma C.6, used in Section 6.2 and referenced to [Ban38, HLZ10, So11, BGG+17].
  • domain assumption Riemannian trust-region global convergence theorem of Boumal-Absil-Cartis.
    Used in Appendix A to obtain approximate second-order local maximizers for BSS rounding; not proved in the paper.
  • domain assumption ETH and the QMA(2) protocol of Le Gall-Nakagawa-Nishimura with local dimension D = eTheta(L) and inverse-linear gap.
    Used in Section 3.6 to argue tightness; external complexity-theoretic assumption.
  • domain assumption Complex BSS instances can be realified with only constant-factor changes to local dimensions and gap scales.
    Stated in Section 2.2; needed to pass from real-symmetric proofs to general BSS.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Argmax Principle for Sum-of-Squares Relaxations on the Sphere." pith.science (2026). https://pith.science/paper/LN4CHVZQ

@misc{pith2026260802594,
  author       = {Pith},
  title        = {Pith review of: An Argmax Principle for Sum-of-Squares Relaxations on the Sphere},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LN4CHVZQ}},
  note         = {Machine review of arXiv:2608.02594}
}
abstract

We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $\Phi_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/\epsilon})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/\epsilon)$ SoS gives a multiplicative $(1+\epsilon)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 8 linked inside Pith

  1. [1]

    The power of unentanglement

    Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. The power of unentanglement. In Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC) , pages 223--236, 2008

    2008

  2. [2]

    Prashanti Anderson, Ainesh Bakshi, and Samuel B. Hopkins. Entrywise low-rank approximation and matrix p q norms via global correlation rounding. CoRR , abs/2604.22699, 2026

    arXiv 2026

  3. [3]

    Subexponential algorithms for unique games and related problems

    Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. Journal of the ACM , 62(5):1--25, 2015

    2015

  4. [4]

    Absil, and Coralia Cartis

    Nicolas Boumal, P.-A. Absil, and Coralia Cartis. Global rates of convergence for nonconvex optimization on manifolds. IMA Journal of Numerical Analysis , 39(1):1--33, 2019

    2019

  5. [5]

    \"uber homogene polynome in (L^2)

    Stefan Banach. \"uber homogene polynome in (L^2) . Studia Mathematica , 7:36--44, 1938

    1938

  6. [6]

    Boaz Barak, Fernando G. S. L. Brand \ a o, Aram W. Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 307--326, New York, NY, USA, 2012. Association for Computing Machinery

    2012

  7. [7]

    Fernando G. S. L. Brand \ a o, Matthias Christandl, and Jon Yard. Faithful squashed entanglement. Communications in Mathematical Physics , 2011

    2011

  8. [8]

    Weak decoupling, polynomial folds, and approximate optimization over the sphere

    Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. Weak decoupling, polynomial folds, and approximate optimization over the sphere. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science ( FOCS ) , pages 1008--1019. IEEE Computer Society, 2017

    2017

Show all 51 references
  1. [9]

    Inapproximability of matrix p q norms

    Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. Inapproximability of matrix p q norms. SIAM Journal on Computing , 52(1):132--155, 2023

    2023

  2. [10]

    Inapproximability of finding sparse vectors in codes, subspaces, and lattices

    Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, and Xuandi Ren. Inapproximability of finding sparse vectors in codes, subspaces, and lattices. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1295--1303, 2025

    2025

  3. [11]

    Brand \ a o and Aram W

    Fernando G.S.L. Brand \ a o and Aram W. Harrow. Quantum de finetti theorems under local measurements with applications. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC) , 2013

    2013

  4. [12]

    Positive Definite Matrices

    Rajendra Bhatia. Positive Definite Matrices . Princeton Series in Applied Mathematics. Princeton University Press, 2007

    2007

  5. [13]

    Mitali Bafna, Jun-Ting Hsieh, and Pravesh K. Kothari. Rounding large independent sets on expanders. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing ( STOC ) , STOC '25, page 631–642, New York, NY, USA, 2025. Association for Computing Machinery

    2025

  6. [14]

    Kelner, and David Steurer

    Boaz Barak, Jonathan A. Kelner, and David Steurer. Rounding sum-of-squares relaxations. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 31--40, New York, NY, USA, 2014. Association for Computing Machinery

    2014

  7. [15]

    Kothari, and David Steurer

    Boaz Barak, Pravesh K. Kothari, and David Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 975--988, New York, NY, USA, 2017. Association for Computing Machinery

    2017

  8. [16]

    Robust linear regression: Optimal rates in polynomial time

    Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing ( STOC ) , pages 102--115. Association for Computing Machinery, 2021

    2021

  9. [17]

    Rounding semidefinite programming hierarchies via global correlation

    Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 472--481, 2011

    2011

  10. [18]

    A quantum characterization of NP

    Hugue Blier and Alain Tapp. A quantum characterization of NP . Computational Complexity , 21(3):499--510, 2012

    2012

  11. [19]

    Low cardinality admissible meshes on quadrangles, triangles and disks

    Len Bos and Marco Vianello. Low cardinality admissible meshes on quadrangles, triangles and disks. Mathematical Inequalities & Applications , 15(1):229--235, 2012

    2012

  12. [20]

    Short multi-prover quantum proofs for sat without entangled measurements

    Jing Chen and Andrew Drucker. Short multi-prover quantum proofs for sat without entangled measurements. CoRR , abs/1011.0716, 2010

    2010 arXiv

  13. [21]

    Alessandro Chiesa and Michael A. Forbes. Improved soundness for QMA with multiple provers. Chicago Journal of Theoretical Computer Science , 2013(1), 2013

    2013

  14. [22]

    Convergence analysis for lasserre’s measure-based hierarchy of upper bounds for polynomial optimization

    Etienne De Klerk, Monique Laurent, and Zhao Sun. Convergence analysis for lasserre’s measure-based hierarchy of upper bounds for polynomial optimization. Mathematical Programming , 162(1):363--392, 2017

    2017

  15. [23]

    Doherty, Pablo A

    Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. Complete family of separability criteria. Physical Review A , 69(2):022308, 2004

    2004

  16. [24]

    Convergence of sdp hierarchies for polynomial optimization on the hypersphere

    Andrew C Doherty and Stephanie Wehner. Convergence of sdp hierarchies for polynomial optimization on the hypersphere. arXiv preprint arXiv:1210.5048 , 2012

    2012 arXiv

  17. [25]

    Schwankung von polynomen zwischen gitterpunkten

    Hartmut Ehlich and Karl Zeller. Schwankung von polynomen zwischen gitterpunkten. Mathematische Zeitschrift , 86:41--44, 1964

    1964

  18. [26]

    The sum-of-squares hierarchy on the sphere and applications in quantum information theory

    Kun Fang and Hamza Fawzi. The sum-of-squares hierarchy on the sphere and applications in quantum information theory. Mathematical Programming , 190(1--2):331--360, 2021

    2021

  19. [27]

    Estimating the matrix p q norm

    Larry Guth, Dominique Maldague, and John Urschel. Estimating the matrix p q norm. CoRR , abs/2311.07677, 2023

    2023 arXiv

  20. [28]

    Classical deterministic complexity of Edmonds' problem and quantum entanglement

    Leonid Gurvits. Classical deterministic complexity of Edmonds' problem and quantum entanglement. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 10--19, New York, NY, USA, 2003. Association for Computing Machinery

    2003

  21. [29]

    Hopkins and Jerry Li

    Samuel B. Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 1021--1034. Association for Computing Machinery, 2018

    2018

  22. [30]

    Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

    Simai He, Zhening Li, and Shuzhong Zhang. Approximation algorithms for homogeneous polynomial optimization with quadratic constraints. Mathematical Programming , 125(2):353--383, 2010

    2010

  23. [31]

    Harrow and Ashley Montanaro

    Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin--Arthur games and tensor optimization. Journal of the ACM , 60(1):1--43, 2013

    2013

  24. [32]

    Limitations of semidefinite programs for separable states and entangled games

    Aram W Harrow, Anand Natarajan, and Xiaodi Wu. Limitations of semidefinite programs for separable states and entangled games. Communications in Mathematical Physics , 366(2):423--468, 2019

    2019

  25. [33]

    Hopkins and Stefan Tiegel

    Samuel B. Hopkins and Stefan Tiegel. Algorithms with polynomially-improved approximation factors for the 2 q norm, and applications. CoRR , abs/2605.25303, 2026

    2026 arXiv

  26. [34]

    A cheeger inequality for small set expansion

    Akhil Jalan. A cheeger inequality for small set expansion. CoRR , abs/2304.07612, 2023

    2023 arXiv

  27. [35]

    The QMA(2) universecomplexity, entanglement, and optimization

    Fernando Granha Jeronimo, Itai Leigh, and Pei Wu. The QMA(2) universecomplexity, entanglement, and optimization. SIGACT News , 57(1):64–99, March 2026

    2026

  28. [36]

    Kothari, and Raghu Meka

    Adam Klivans, Pravesh K. Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression. In Proceedings of the 31st Conference on Learning Theory ( COLT ) , volume 75 of Proceedings of Machine Learning Research , pages 1420--1430. PMLR , 2018

    2018

  29. [37]

    Quantum Merlin--Arthur proof systems: Are multiple merlins more helpful to arthur? In Algorithms and Computation , pages 189--198

    Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin--Arthur proof systems: Are multiple merlins more helpful to arthur? In Algorithms and Computation , pages 189--198. Springer, 2003

    2003

  30. [38]

    Linear equations modulo 2 and the l1 diameter of convex bodies

    Subhash Khot and Assaf Naor. Linear equations modulo 2 and the l1 diameter of convex bodies. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 318--328. IEEE, 2007

    2007

  31. [39]

    Kothari, Jacob Steinhardt, and David Steurer

    Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing ( STOC ) , pages 1035--1046. Association for Computing Machinery, 2018

    2018

  32. [40]

    Lasserre

    Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization , 11(3):796--817, 2001

    2001

  33. [41]

    Sums of squares, moment matrices and optimization over polynomials

    Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry , volume 149 of IMA Volumes in Mathematics and its Applications , pages 157--270. Springer, 2009

    2009

  34. [42]

    On QMA protocols with two short quantum proofs

    Fran c ois Le Gall , Shota Nakagawa, and Harumichi Nishimura. On QMA protocols with two short quantum proofs. Quantum Information & Computation , 12(7--8):589--600, 2012

    2012

  35. [43]

    Sum-of-squares hierarchies for binary polynomial optimization

    Monique Laurent and Lucas Slot. Sum-of-squares hierarchies for binary polynomial optimization. CoRR , abs/2011.04027, 2022

    2011 arXiv

  36. [44]

    Unentangled stoquastic merlin-arthur proof systems: the power of unentanglement without destructive interference

    Yupan Liu and Pei Wu. Unentangled stoquastic merlin-arthur proof systems: the power of unentanglement without destructive interference. arXiv preprint arXiv:2604.27886 , 2026

    2026 arXiv

  37. [45]

    A statistical model for tensor PCA

    Andrea Montanari and Emile Richard. A statistical model for tensor PCA . Advances in Neural Information Processing Systems , 27, 2014

    2014

  38. [46]

    Nonnegative polynomials and their carath \'e odory number

    Simone Naldi. Nonnegative polynomials and their carath \'e odory number. Discrete & Computational Geometry , 51(3):559--568, 2014

    2014

  39. [47]

    Random walk in a simplex and quadratic optimization over convex polytopes

    Yurii Nesterov. Random walk in a simplex and quadratic optimization over convex polytopes. 2003

    2003

  40. [48]

    Quantum free games

    Anand Natarajan and Tina Zhang. Quantum free games. In Proceedings of the 55th ACM Symposium on Theory of Computing (STOC) , STOC 2023, page 1603–1616, 2023

    2023

  41. [49]

    Pablo A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming , 96(2):293--320, 2003

    2003

  42. [50]

    Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

    Anthony Man-Cho So. Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems. Mathematical programming , 129(2):357--382, 2011

    2011

  43. [51]

    SoS degree reduction with applications to clustering and robust moment estimation

    David Steurer and Stefan Tiegel. SoS degree reduction with applications to clustering and robust moment estimation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , pages 374--393. SIAM , 2021

    2021

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.