SciPost Submission Page
On the topology of solutions to random continuous constraint satisfaction problems
by Jaron Kent-Dobias
Submission summary
| Authors (as registered SciPost users): | Jaron Kent-Dobias |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/2409.12781v3 (pdf) |
| Date submitted: | 2025-03-12 11:27 |
| Submitted by: | Kent-Dobias, Jaron |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approach: | Theoretical |
Abstract
We consider the set of solutions to $M$ random polynomial equations whose $N$ variables are restricted to the $(N-1)$-sphere. Each equation has independent Gaussian coefficients and a target value $V_0$. When solutions exist, they form a manifold. We compute the average Euler characteristic of this manifold in the limit of large $N$, and find different behavior depending on the target value $V_0$, the ratio $\alpha=M/N$, and the variances of the coefficients. We divide this behavior into five phases with different implications for the topology of the solution manifold. When $M=1$ there is a correspondence between this problem and level sets of the energy in the spherical spin glasses. We conjecture that the transition energy dividing two of the topological phases corresponds to the energy asymptotically reached by gradient descent from a random initial condition, possibly resolving an open problem in out-of-equilibrium dynamics. However, the quality of the available data leaves the question open for now.
Author indications on fulfilling journal expectations
- Provide a novel and synergetic link between different research areas.
- Open a new pathway in an existing or a new research direction, with clear potential for multi-pronged follow-up work
- Detail a groundbreaking theoretical/experimental/computational discovery
- Present a breakthrough on a previously-identified and long-standing research stumbling block
Author comments upon resubmission
List of changes
A latexdiff of the changes since the first submission is available here: https://kent-dobias.com/files/2409.12781v2-v3_diff.pdf
An itemized list of changes follows.
* Affiliations, contact email, and funding information were updated.
* A sentence was appended to the abstract emphasizing the imprecision of the evidence supporting our conjecture.
* More context was added to references in the introduction, and some references were added.
* A comment was added referencing that *H* must be a Morse function.
* A footnote was added explaining the interpretation of the order parameter *m*.
* A footnote was added explaining the agreement of the satisfiability threshold computed here and that computed using the zero-temperature equilibrium calculation.
* A footnote was added explaining our choice to favor a specific interpretation of a large Euler characteristic.
* Some minor mistakes were fixed in the beginning of section 3.
* A footnote was added explaining the commutation of limits *N* → ∞ and α → 0.
* Paragraphs were added discussing the relationship of our dynamic conjecture with other algorithms and with problems with a deterministic piece.
* The references regarding the use of superspace coordinates were given more introduction.
* A footnote was added to explain subscript notation of the determinant.