Some easy optimization problems have the overlap-gap property

TL;DR

This paper challenges a common heuristic in theoretical computer science: the "overlap-gap property" (OGP) is often seen as a predictor of algorithmic hardness. The authors demonstrate that the seemingly simple shortest path problem in random graphs possesses the OGP, yet it can be solved efficiently by low-degree polynomial algorithms. This finding suggests that the OGP might not be as universally indicative of intractability as previously thought, prompting a re-evaluation of its predictive power.

What Problem Does This Paper Address?

In theoretical computer science, particularly in the study of average-case complexity, researchers often encounter optimization problems where the set of near-optimal solutions is structured in a particular way. This structure, known as the "overlap-gap property" (OGP), describes a situation where near-optimal solutions are either very close to each other or very far apart, with no intermediate distances. This property has been instrumental in proving unconditional lower bounds against certain classes of algorithms, such as "smooth" or "low-degree polynomial" algorithms. The intuition is that if near-optimal solutions are clustered into well-separated groups, it becomes difficult for algorithms that rely on small, local changes (like smooth algorithms) to transition between these clusters.

A key question arises: does the OGP always imply algorithmic hardness? Historically, for many problems where the OGP holds, the known computational thresholds for solving them align with the hardness predictions derived from the OGP. This paper investigates whether this alignment is universal, specifically by examining the shortest path problem in random graphs. This problem is known to be computationally easy, solvable by standard polynomial-time algorithms. The authors aim to see if the OGP, when applied to this easy problem, still predicts hardness, and if so, why.

Methods

The paper's core contribution lies in demonstrating that the shortest path problem in sparse random graphs (specifically, Erdős-Rényi graphs $G(n, q)$ where $q = \Theta(\log n)$) exhibits the overlap-gap property. They achieve this using a combination of:

• First and Second Moment Methods: These probabilistic techniques are standard for analyzing random graphs and are used here to characterize the length of shortest paths and to bound the number of such paths.
• Invariance Principles: The authors leverage an invariance principle (from Caravenna et al., 2023) to show that symmetric low-degree polynomials are "stable" (a technical term related to their resilience to noise) on average-case inputs. This is crucial for deriving lower bounds against low-degree polynomial algorithms.
• Combinatorial Arguments: Detailed counting arguments are employed to analyze the overlap between different paths and to establish the OGP.
• Analysis of Polynomial Estimators: The paper constructs and analyzes low-degree polynomial estimators that can effectively approximate the shortest path, directly contradicting the hardness predictions that would typically be inferred from the OGP.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of random graph models rather than empirical evaluation on specific datasets.

Key Insights and Ideas

• OGP is not a universal predictor of hardness: The most significant insight is that the overlap-gap property, while a powerful tool for proving lower bounds, does not always imply computational intractability. The shortest path problem serves as a counterexample, possessing the OGP yet being efficiently solvable.
• Smoothness vs. Success Probability: The OGP typically implies lower bounds against algorithms with ultra-high success probability. This paper shows that algorithms with decent success probability can exist even when the OGP holds, highlighting a subtlety in the interpretation of OGP-based hardness results.
• Low-degree polynomials are more powerful than expected: The authors demonstrate that low-degree polynomial algorithms can solve the shortest path problem effectively, even in the presence of the OGP. This suggests that the "smoothness" property, often associated with low-degree polynomials, might not be as restrictive as previously assumed in certain contexts.
• Re-evaluating the OGP's scope: The findings necessitate a re-evaluation of when and why the OGP is a reliable heuristic for predicting computational hardness. The paper suggests that structural properties of the problem, beyond just the OGP itself, might play a crucial role.

Key Results

• Shortest Path has OGP: The shortest $s$-$t$ path problem in sparse random graphs ($G(n, q)$ with $q = \Theta(\log n)$) exhibits the overlap-gap property with high probability.
• Low-Degree Polynomial Solvability: The paper shows that the shortest path problem can be solved by degree-$O(\log n)$ polynomial estimators with high success probability. This is a direct challenge to the typical implications of the OGP.
• Approximate Shortest Paths are Sampleable: The set of approximate shortest paths can be enumerated in polynomial time, making sampling easy, even though the problem exhibits "disorder chaos" (a stronger form of OGP).
• Lower Bounds Against Smooth Algorithms: Consistent with OGP theory, the paper derives unconditional lower bounds against "smooth" algorithms for solving the shortest path problem. However, these bounds are shown to be weaker than what might be expected if the OGP were a universal indicator of hardness.

Limitations and Future Work

• Subtlety of OGP Interpretation: The paper highlights that OGP-based lower bounds often rule out algorithms with ultra-high success probability. The authors suggest that future work should focus on understanding when algorithms with merely decent success probability can be ruled out, especially in non-planted average-case problems.
• Appropriateness of Stable Algorithms: The authors question whether "stable" or "smooth" algorithms are the right class to consider for non-planted average-case optimization problems, suggesting that other algorithmic paradigms (like linear programming) might be more relevant.
• Power of Low-Degree Polynomials: The paper raises the question of how powerful degree-$O(\log n)$ polynomials are in the context of non-planted optimization problems. It's unclear if they can solve problems like finding a large clique in $G(n, p)$.
• Conditions for OGP as a Hardness Heuristic: The authors propose revisiting "easy" problems from introductory algorithms courses to check if they have the OGP. This systematic approach could help identify additional conditions under which the OGP is a good heuristic for hardness, or why it fails.
• Algebraic Structure: Problems with algebraic structure, like $k$-XOR, are known "black sheep" where OGP heuristics fail. The paper speculates that structural features of shortest paths (e.g., unbroken path constraint, size of solution set) might be responsible for the OGP's predictive failure in this case.
• Sampling Algorithms: While the paper shows sampling is easy for shortest paths, it raises the question of whether this is a general phenomenon for problems exhibiting disorder chaos.