On the topology of solutions to random continuous constraint satisfaction problems

1- The study addresses a gap in understanding the loss landscape of CS problems, a field that has been challenging due to technical complexity.
2- The application of the Kac-Rice formula to study Euler characteristics in high-dimensional settings is, to my knowledge, novel and simplifies the calculations considerably. This approach could potentially be extended to other problems where progress has been hindered by the sign of the determinant.
3- Technically, this remains a difficult problem, highlighting the significance of the result.
4- The results provide valuable insights, identifying a complex picture of the landscape and several regimes that may help elucidate the dynamics.
5- The final question addressed in the paper is significant, as it has remained elusive in previous studies. While I am not fully convinced by the author's argument (detailed later), it introduces valuable new elements to the discussion.

1- The paper provides insufficient discussion of previous work. The author condenses key background and literature into two brief sentences (at the start of the second paragraph of Section 1 and at the end of page 2). Even for readers familiar with these references, this is hard to parse. I had to go into the bibliography and see which paper the author was referring to in order to follow. I strongly recommend expanding the introduction and discussing prior work in greater detail to provide adequate context for the reader.
2- The interpretation of magnetization m is unclear. While briefly mentioned at the beginning of Section 2.2, the explanation is insufficient. Since there is no planting in this problem, the physical meaning of an arbitrary random direction is still unclear to me.
3- Although the introduction to Euler characteristics in Section 2.1 is generally well-presented, I am still uncertain about some aspects:
3.1- At the beginning of Section 2.2, the author notes compatibility with an N−M−1 sphere, yet the Euler characteristic should be 2 for any hypersphere regardless of dimension. Can something be concluded about dimensionality here?
3.2- The large Euler characteristic could result from either many disconnected components or the manifold being a product of many manifolds, but the analysis does not distinguish between these cases. How might these scenarios lead to different landscapes? Can we say something about the possible implications for the dynamics?
4- The connection with the dynamics is not fully convincing. In particular, the theory provided in the paper does not explain the relationship between dynamics and the temperature dependence observed in references [26, 27]. These references identify different behaviours based on the initial temperature in a mixed p-spin model, yet this aspect does not seem to emerge.
4.1- Additionally, I wonder if the authors have considered how planting would affect the landscape. In the mixed p-spin case, planting simplifies the picture compared to what was observed in [26, 27].
5- The derivation lacks sufficient detail in some sections. The author uses properties of the superdeterminant without providing references, making it difficult to follow. For example, the steps leading to equations (37-39) are unclear.
5.1- In equation (47), a superdeterminant with a suffix is introduced without a definition, which makes it challenging to interpret.

This paper addresses a technically challenging and important problem, making a significant contribution to the study of loss landscapes in constraint satisfaction problems. The innovative application of the Kac-Rice formula and the identification of new regimes add meaningful insights to the field. Although there are some areas requiring clarification and expansion, especially regarding background context, the interpretation of the order parameter, and the connection to dynamics, these revisions mainly pertain to the clarity and depth of exposition rather than fundamental issues. Overall, I recommend acceptance, contingent on addressing the previously mentioned issues in a revised version.

1- Expand the introduction, providing more context for the problem and discussing relevant previous contributions.
2- Clarify the physical interpretation of the order parameter m.
3- Discuss the different scenarios that could result from a large Euler characteristic and their implications for the landscape and dynamics.
4- Provide further clarity on the connection with dynamics, specifically addressing the temperature dependence observed in prior work and the potential effect of planting.
5- Provide additional detail in the derivation, particularly in Sections A and B.1.

Ask for minor revision

In this article, the author considers the statistics (mostly the average) of the Euler characteristics for solutions of $M$ random constraint satisfaction problems $V_k({\bf x})=V_0$ where the vector ${\bf x}\in \sqrt{N}{\cal S}_{N-1}$ is on the $N$-sphere. This quantity provides interesting information on the topology of the solution space. The author considers specifically the limit $N,M\to \infty$ with fixed ratio $\alpha=M/N$. From the expression of the average Euler characteristics, the author obtains a phase diagram for the model, separating various topologies for the space of solutions. The results on the average are further confirmed and extended by computations of the second moment as well as the average logarithm of the Euler characteristics.

As a byproduct of the computations, the author derives interesting conjectures on spherical spin-glass model by taking the limit $\alpha,V_0\to 0$, with $E=\alpha^{-1/2}V_0$ fixed. For $M=1$, the solutions of the constraint satisfaction problem indeed coincide with level-sets of the spherical spin-glass.

The article is very well written and reports new and interesting results. I therefore recommend it for publication in SciPost Physics.

Please find below a short list of comments/ typos:

-p 10: "This fact mirrors another another that was made clear recently"

-Some of the results derived for the spherical spin-glass stem from the limit mentioned above. It is clear that this limit may be relevant as some important energy scales are recovered that way. Note however that starting from a regime $\alpha=M/N=O(1)$ and taking the limit $\alpha\to 0$ should in fact match with the limit $M\to \infty$ of the regime $M=O(1)$. Thus there is no guarantee that it should provide relevant information on the case $M=1$. A direct study of the level set of the spherical spin-glass model as done in Appendix D should allow to confirm this prediction. It was not entirely clear from the manuscript whether this analysis indeed does confirm the relevance of $E_{\rm sh}$.

-As mentioned by the author, the numerical data does not allow to judge the relevance of the energy scale $E_{\rm sh}$ and this direction deserves further investigation

Publish (meets expectations and criteria for this Journal)

1- The work deals with a constraint satisfaction problem that was introduced recently, which serves as a toy model for both confluent tissues and non-linear regression in high dimension; it addresses a problem (the characterization of the topology of the solution space) that is of interest for this model, but also beyond.

2 - The author points out a limit in which the constraint satisfaction problem maps into well known mean-field models of glasses, allowing them to formulate a conjecture on the dynamical meaning of the shattering transition in this limit.

3 - The appendices contain some careful analysis (e.g. of lower order contributions which contribute to the refactor of the average Euler characteristics). The main text remains very readable, the content is well distributed between main and appendices.

1 - The comparison with previous results in the literature and the discussion on the instability towards RSB phases could be clarified further (see comments below).

The work characterizes the topology of the manifold of solutions of a high-dimensional, random constant satisfaction problem, which was introduced recently in the literature in connection to problems of confluent tissues and of non-linear regression in high dimension. The topology is characterized by computing the average Euler characteristics of the solution manifold, in the limit of large dimensionality N of the configuration space. The analysis allows to identify five distinct regimes as a function of the model's control parameter V0. These regimes differ by the magnitude of the average Euler characteristics (exponential in N vs order one in N), by its sign and by the regions of configuration space that contribute dominantly to it. A scaling limit is also discussed, in which this analysis corresponds to the characterization of the topology of level sets of the energy landscape of spherical p-spin models. Within this context, the author proposes a dynamical interpretation of the "shattering energy”, which corresponds to the energy level where a transition occurs between different topological phases, as being predictive of the dynamic threshold.

The manuscript is clear and self-contained. Below are some questions and requests for clarifications:

(i) It is argue in the paper that in the regime V<V_sh, where the action at m=0 is complex, that in the regime where the action at, the solution should not be discarded as it indicates a negative average Euler characteristic. This argument is supported by the calculation of the second moment and the equality (18). Regarding the m* solutions, the action at m* becomes complex above V_on: is there an interpretation for these solutions in the regime V> V_on?

(ii) It is mentioned that the naive satisfiability threshold predicted from the vanishing of (12) coincides with the threshold obtained within the replica symmetric analysis of the cost function (3). By reading the manuscript, I have missed if/how the satisfiability threshold arising from the analysis of the average Euler characteristics compares with the threshold obtained from the zero-temperature analysis of the equilibrium problem with energy (3): could the Author comment on this?

(iii) Related to (ii): a general discussion on the instability of the average Euler characteristics to RSB is presented in Appendix C2, leading to the prediction (79). In the case of the spherical models illustrated in Figures 3 and 4, this instability seems not to be relevant in the regions where the SAT-UNSAT transition occurs. It is not clear to me whether all the cases illustrated in the plot are such that the correct ground state is found within a simple RS formalism from the T=0 equilibrium calculations, or whether there is no relation between the RSB instabilities occurring within the two calculations. A comment on this could be added in the text.

(iv) If understand correctly, the vector x0 is arbitrary and it is introduced with the purpose of decomposing the contributions to the Euler characteristics in terms of m. Given the arbitrarily of x0, one would naively expect that the “observable” part of the solution space corresponds to m=0, and that any analysis of the constraint satisfaction problem that is x0-independent should be unable to pick up the transition between Regime II and Regime III: is this the case?

1- I would clarify the connection to previous results, if available, particularly in relation to points (ii) and (iii) mentioned above.

2- Possibly add some comments on the other points in the report.

3- Consider adding more information to Fig. 2, such as the notation for the values of the order parameters where transitions occur (V_on, V_sh, V_SAT), and the key features of the average Euler characteristics in each regime.

4- Include a comment stating that the functions in equation (7) are Morse, which justifies the use of equation (6). The Smale condition is mentioned, but not explained.

Publish (meets expectations and criteria for this Journal)