TL;DR
This paper introduces a more powerful framework for proving that certain optimization problems are hard to solve using linear programming (LP) and semidefinite programming (SDP) relaxations. By generalizing existing reduction techniques, the authors establish new hardness results for fundamental problems like SparsestCut, MaxCut, and Matching, and demonstrate that the Lasserre hierarchy, a common tool for approximating solutions, can be surprisingly suboptimal.
What Problem Does This Paper Address?
The core problem this paper tackles is understanding the inherent computational difficulty of solving various optimization problems. Specifically, it focuses on how well these problems can be approximated using Linear Programming (LP) and Semidefinite Programming (SDP) relaxations. These relaxations are crucial in designing efficient algorithms for many NP-hard problems. A key measure of difficulty is whether a problem can be formulated with a polynomial number of constraints in an LP or SDP. If not, it's considered LP-hard or SDP-hard, implying that no polynomial-time algorithm based on these relaxations can solve it exactly or provide a good approximation.
The authors build upon previous work that introduced a reduction mechanism to prove such hardness results. However, this prior mechanism had limitations: it required "affine" reductions, meaning the relationships between problems had to be linear. This excluded certain problems and prevented the strongest possible hardness results. This paper aims to overcome these limitations by generalizing the reduction technique, allowing for more complex relationships and extending the framework to fractional optimization problems (where the objective is a ratio of linear functions, like SparsestCut).
Methods
The paper's main technical contribution is a generalized reduction mechanism for LP and SDP hardness proofs. This generalization addresses two key limitations of prior work:
- Relaxing Affineness: The new framework allows for "non-affine" relationships between problems. This means the reduction can involve more complex computations, effectively incorporating "extra computation" into the reduction itself. This is achieved by allowing the reduction maps to have their own small LP/SDP formulations, which bypasses the need for specific techniques like Sherali-Adams reductions for certain problems. This generalization also enables a "weak form of gap-amplification and boosting."
- Extending to Fractional Optimization: The authors introduce a framework for analyzing fractional optimization problems. These problems, where the objective is a ratio of linear functions (e.g., SparsestCut), are challenging because the space of objective functions is high-dimensional and not easily captured by standard LP/SDP formulations. The new framework models the typical approach to solving these problems by optimizing the numerator and denominator simultaneously, allowing for stronger hardness statements.
The paper also leverages the concept of nonnegativity problems and their slack matrices as a unifying tool. This abstract view connects formulation complexity (how complex an LP/SDP formulation needs to be) to combinatorial properties of these slack matrices, specifically their LP and SDP ranks. Reductions between nonnegativity problems are then used to transfer hardness results.
Datasets
Not discussed in the paper. The paper focuses on theoretical hardness results for abstract optimization problems and graph structures, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- More Powerful Reductions: The core insight is that by allowing more complex (non-affine) relationships in reductions, we can prove stronger hardness results for a wider range of problems. This is a significant step beyond previous, more restrictive, reduction techniques.
- Fractional Problems are Harder to Approximate: The paper highlights that fractional optimization problems, like SparsestCut, are inherently difficult to approximate with small LPs/SDPs due to the nature of their objective functions. The new framework provides a way to formally analyze this difficulty.
- Lasserre Hierarchy Isn't Always Tight: A surprising finding is the demonstration of a new, strong Lasserre integrality gap for the IndependentSet problem. This shows that even with a sophisticated hierarchy of SDP relaxations (the Lasserre hierarchy), we can still find instances where the gap between the optimal solution and the relaxation is significantly larger than what LP approximations can achieve, implying the hierarchy doesn't always provide the tightest possible relaxation.
- Unified Framework: The use of nonnegativity problems and slack matrices provides a clean and unified way to study formulation complexity and prove hardness results, connecting different types of problems and relaxations.
Key Results
- New LP/SDP Hardness Results: The paper establishes several new LP-hardness and SDP-hardness results for problems including:
- SparsestCut (even for graphs with bounded treewidth supply)
- BalancedSeparator (even for graphs with bounded treewidth demand)
- MaxCut (specifically, an SDP-hardness result for MaxCut with a factor of 15/16 + ε)
- Matching on 3-regular graphs (showing it doesn't admit small LP formulations)
- Strong Lasserre Integrality Gap: A new, strong Lasserre integrality gap of $n^{1-\gamma}$ is shown for the IndependentSet problem, significantly improving upon previous results and demonstrating the suboptimality of the Lasserre hierarchy.
- Generalized Reduction Theorem: A key theorem (Theorem 3.2) formalizes how hardness is preserved under the new, more general reduction framework, relating the complexity of two problems.
Limitations and Future Work
- Open Problems: The paper explicitly mentions open problems, such as whether the lower bound for Matching on bounded-degree graphs can be strengthened to $2^{\Omega(n)}$.
- Specific Graph Classes: While the paper provides hardness results for problems on graphs with bounded treewidth, further exploration of specific graph classes and their impact on hardness could be beneficial.
- Practical Implications: The theoretical hardness results provide fundamental limits. Future work could explore how these limits inform the design of practical approximation algorithms or heuristics when exact solutions are intractable.
- Further Applications of the Framework: The generalized reduction framework is powerful and could potentially be applied to prove hardness for other optimization problems not covered in this paper.
Summary updated