REVIEW 2 cited by
Some easy optimization problems have the overlap-gap property
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
abstract
We show that the shortest $s$-$t$ path problem has the overlap-gap property in (i) sparse $\mathbf{G}(n,p)$ graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse $\mathbf{G}(n,p)$ graphs, shortest path is solved by $O(\log n)$-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem.
Forward citations
Cited by 2 Pith papers
-
Polynomial-time sampling despite disorder chaos
Disorder chaos does not prevent polynomial-time Wasserstein sampling: Glauber dynamics samples the hardcore model on G(n,1/2) in O(n) time even though tiny graph perturbations radically change the target distribution.
-
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.