SciPost Submission Page
Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
by Silvio Franz, Giorgio Parisi, Maksim Sevelev, Pierfrancesco Urbani, Francesco Zamponi
This is not the latest submitted version.
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Silvio Franz · Maxime Sevelev · Pierfrancesco Urbani |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/1702.06919v1 (pdf) |
| Date submitted: | 2017-02-25 01:00 |
| Submitted by: | Urbani, Pierfrancesco |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approach: | Theoretical |
Abstract
Random constraint satisfaction problems (CSP) have been studied extensively using statistical physics techniques. They provide a benchmark to study average case scenarios instead of the worst case one. The interplay between statistical physics of disordered systems and computer science has brought new light into the realm of computational complexity theory, by introducing the notion of clustering of solutions, related to replica symmetry breaking. However, the class of problems in which clustering has been studied often involve discrete degrees of freedom: standard random CSPs are random K-SAT (aka disordered Ising models) or random coloring problems (aka disordered Potts models). In this work we consider instead problems that involve continuous degrees of freedom. The simplest prototype of these problems is the perceptron. Here we discuss in detail the full phase diagram of the model. In the regions of parameter space where the problem is non-convex, leading to multiple disconnected clusters of solutions, the solution is critical at the SAT/UNSAT threshold and lies in the same universality class of the jamming transition of soft spheres. We show how the critical behavior at the satisfiability threshold emerges, and we compute the critical exponents associated to the approach to the transition from both the SAT and UNSAT phase. We conjecture that there is a large universality class of non-convex continuous CSPs whose SAT-UNSAT threshold is described by the same scaling solution.
Current status:
Reports on this Submission
Report #2 by Anonymous (Referee 2) on 2017-4-25 (Invited Report)
- Cite as: Anonymous, Report on arXiv:1702.06919v1, delivered 2017-04-25, doi: 10.21468/SciPost.Report.121
Strengths
It looks like an exemplar piece of theoretical work
Weaknesses
Probably is connected to its strength. It's too technical and hard to follow for somebody without a background in disordered systems.
Report
I must admit that I didn't have the time to properly check all the results presented by the authors, although they look to me reasonable, physically sound and feasible to be reproduced with the technical information provided in the manuscript.
The paper is very well written, the results are original and it probably concludes the analysis of the thermodynamics of the problem already started by the authors and other collaborators in ref's [14], [16]-[19]. Therefore I strongly recommend this work as an important piece in the study of disordered systems with continuous variables.
Requested changes
1-However, I would like to suggest to the authors to make clearer in the conclusions that their statement that the SAT/UNSAT transition is fullRSB, is a statement valid strictly for the model studied in the manuscript and not necessarily valid for other non-convex continuous CSP. At least, in the way that I understood the manuscript. If this is not the case, it is worth to say a few words about why the authors believe this statement is more general than that.
Author: Pierfrancesco Urbani on 2017-04-29 [id 123]
(in reply to Report 2 on 2017-04-25)We thank the referee for her/his report. We have followed her/his suggestion and we have added a sentence in the conclusions underlining what she/he was mentioning. We are not able to prove that the non-convex jamming transition is always in a fullRSB phase. Nevertheless there are at least two models where this is the case that are the random perceptron and hard spheres in high dimension. We resubmit an updated version of the paper with very few typos corrected.
Report #1 by Anonymous (Referee 1) on 2017-4-13 (Contributed Report)
- Cite as: Anonymous, Report on arXiv:1702.06919v1, delivered 2017-04-13, doi: 10.21468/SciPost.Report.109
Strengths
1- brings together two fields, jamming and constraint satisfaction problems (CSP) with continuous variables
2- paper is complete, detailed and very well written
3- show signatures of universalities in mean field jamming/CSP transitions
4- phase diagram and exponents computed exactly
Weaknesses
1 - The paper is very technical, perhaps a little bit difficult to read by non experts. However all the pointers are given to the readers.
Report
This is an impressive paper which builds a complete and deep connection between jamming transitions and sat/unsat transitions in random constraint satisfaction problems (CSP) with continuous interactions.
The paper is extremely well written. It provides all the physical insights and definitions of the jamming observables which are needed to interpret the full phase diagram of CSP problems in physical terms. The sphere packing problem in high dimension is represented as a perceptron model with appropriate (negative) stability. The corresponding packing problem is highly non convex as in jamming. Quite remarkably the full T=0 phase diagram is derived, including all levels of symmetry breaking.
The analysis is taken to its limits by computing the scaling solution at the SAT phase boundary of the perceptron. The scaling relations between critical exponents is interpreted in terms of gaps and force distribution at the jamming point.
In my opinion, this paper deserves publication in its present form. There is no doubt that it provides an important unifying perspective on jamming transitions at mean-field level. Moreover is also provides new insight for random CSPs with continuous variables.
The fact that the perceptron model and hard spheres have the same mean field exponents (in infinite dimension) is important. The authors outline some interesting perspectives for future studies aimed at establishing the degree of universality of these results.
Requested changes
1- no changes
Pierfrancesco Urbani on 2017-04-19 [id 118]
We warmly thank our referee: we could not agree more with her/his report.