Detection of Planted Solutions for Flat Satisfiability Problems

Quentin Berthet, Jordan S. EllenbergAISTATS 2019 · OpenReview

Introduction

In the study of computational complexity and statistical inference, a fundamental tension exists between the amount of data required to solve a problem (statistical complexity) and the time required to process that data (computational complexity). This paper explores this tension through the lens of $k$-FLAT, a geometric generalization of the classic $k$-Satisfiability ($k$-SAT) problem. By moving from the discrete boolean clauses of $k$-SAT to affine subspaces (flats) over finite fields ($\mathbb{F}_2$), the authors provide a mathematically cleaner framework to analyze the "hard" regimes where solutions exist but remain computationally inaccessible.

The $k$-FLAT Framework

The $k$-FLAT problem is defined over the vector space $\mathbb{F}_2^n$. While $k$-SAT uses boolean constraints, $k$-FLAT utilizes $m$ flats of dimension $n-k$. This geometric symmetry allows for a more precise pinpointing of phase transitions. The research specifically focuses on the "planted" version of the problem: distinguishing a purely random formula (likely unsatisfiable) from one where a specific solution $x^*$ has been intentionally embedded.

To test the limits of algorithmic detection, the authors define three types of instances:

  1. Random $k$-FLAT: $m$ flats drawn uniformly at random.
  2. Planted $k$-FLAT: A hidden solution $x^*$ is chosen first, and constraints are selected such that they do not exclude $x^*$.
  3. Lightly Planted $k$-FLAT: A novel benchmark where a solution is planted only with a specific probability $\pi$, introducing noise into the planting process.

Methodology

The authors employ a multi-faceted approach to map the complexity landscape of $k$-FLAT:

Probabilistic Analysis

Using first and second moment methods, the paper identifies the sharp phase transition threshold, $\Delta_k \approx 2^k \ln(2)$. This threshold represents the critical ratio of constraints-to-variables where a random instance transitions from being almost certainly satisfiable to almost certainly unsatisfiable. The authors prove that the likelihood ratio test is the optimal statistical method for detection, and its success coincides with this threshold.

Algorithmic Design: The Lifting Test

For computational detection, the authors propose a polynomial-time test ($\psi_L$) based on Veronese embedding, or "lifting." This technique transforms a system of degree-$k$ polynomial equations into a linear system in a higher-dimensional space of approximately $n^k$ dimensions. Once lifted, the system can be solved using standard Gaussian elimination. However, this efficiency comes at a cost: the algorithm requires the number of samples $m$ to scale with $n^k$.

Hardness and LPN Reduction

To establish the computational hardness of the problem, the authors reduce the "lightly planted" $k$-FLAT problem to the Learning Parity with Noise (LPN) problem. LPN is a foundational problem in lattice-based cryptography, widely believed to be resistant to efficient classical and quantum attacks. This reduction suggests that the difficulty of $k$-FLAT is not a byproduct of the model but a fundamental computational barrier.

Key Insights: The Statistical-Computational Gap

The most significant finding is the massive gap between statistical and computational requirements. Statistically, a planted solution can be detected with a linear number of constraints ($m \approx 2^k n$). However, the most effective known polynomial-time algorithms require $m \approx n^k$ constraints. For high-dimensional problems, this gap is astronomical, creating a vast "hard" regime where the information exists within the data, but no known algorithm can extract it efficiently.

Furthermore, the research highlights the "brittleness" of current algorithms. Many efficient methods rely on the absolute consistency of the planted solution (i.e., the solution must satisfy every constraint). The introduction of "light planting" demonstrates that even a small amount of noise causes these algorithms to fail, even though the statistical evidence for the solution remains present.

Conclusion and Future Directions

The $k$-FLAT model serves as a powerful tool for understanding the structural reasons behind computational hardness. The authors suggest that the "shattering" of the solution space—where a single cluster of solutions fragments into numerous isolated islands—may be the physical phenomenon driving this complexity.

Future work remains to determine if sub-exponential (but super-polynomial) algorithms can bridge the gap between $n$ and $n^k$. Additionally, while this paper focuses on detection (identifying if a solution exists), the more difficult task of recovery (finding the specific $x^*$) remains a primary objective for subsequent research in geometric satisfiability.

Summary updated

Abstract

We study the detection problem of finding planted solutions in random instances of flat satisfiability problems, a generalization of boolean satisfiability formulas. We describe the properties of r...
BibTeX
@inproceedings{berthet2019detection,
  author = {Quentin Berthet and Jordan S. Ellenberg},
  title = {{Detection of Planted Solutions for Flat Satisfiability Problems}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=n7HDXwy449V},
}
Figure