REVIEW 3 cited by
Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We prove constant degree polynomial algorithms cannot optimize pure spherical $p$-spin Hamiltonians beyond the algorithmic threshold $\mathsf{ALG}(p)=2\sqrt{\frac{p-1}{p}}$. The proof goes by transforming any hypothetical such algorithm into a Lipschitz one, for which hardness was shown previously by the author and B. Huang.
Forward citations
Cited by 3 Pith papers
-
Sharp Online Hardness for Large Balanced Independent Sets
In dense random bipartite graphs, the largest gamma-balanced independent set is about log_b n/(gamma(1-gamma)), online algorithms can find only (1-epsilon)log_b n/gamma, and no online algorithm can exceed that by a co...
-
Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
For random order-p tensors with large p, the largest average k×...×k subtensor concentrates around sqrt(2p log(N choose k)/k^p), a greedy algorithm achieves a 2√p/(p+1) fraction of it, and an overlap gap property bloc...
-
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.
Discussion (0). Continue with ORCID to comment.