Breaking of 1RSB in Random Regular MAX-NAE-SAT
© 2019 IEEE. For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. In the unsatisfiable regime, it is natural to consider the problem of max-satisfiability: violating the least number of constra...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137022 |
| _version_ | 1826199122893340672 |
|---|---|
| author | Bartha, Zsolt Sun, Nike Zhang, Yumeng |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Bartha, Zsolt Sun, Nike Zhang, Yumeng |
| author_sort | Bartha, Zsolt |
| collection | MIT |
| description | © 2019 IEEE. For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. In the unsatisfiable regime, it is natural to consider the problem of max-satisfiability: violating the least number of constraints. This is a combinatorial optimization problem on the random energy landscape defined by the problem instance. In the bounded density regime, a very precise estimate of the max-sat value was obtained by Achlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate the nature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) shows that for very large but bounded density, the max-sat value approaches the mean-field (complete graph) limit: This is conjectured to have an 'FRSB' structure where near-optimal configurations form clusters within clusters, in an ultrametric hierarchy of infinite depth inside the discrete cube. A stronger form of FRSB was shown in several recent works to have algorithmic implications (again, in complete graphs). Consequently we find it of interest to understand how the model transitions from 1RSB near the satisfiability threshold, to (conjecturally) FRSB at large density. In this paper we show that in the random regular NAE-SAT model, the 1RSB description breaks down by a certain threshold density that we estimate rather precisely. This is proved by an explicit perturbation in the 2RSB parameter space. The choice of perturbation is inspired by the 'bug proliferation' mechanism proposed by physicists (Montanari and Ricci-Tersenghi, 2003; Krzakala, Pagnani, and Weigt, 2004), corresponding roughly to a percolation-like threshold for a subgraph of dependent variables. |
| first_indexed | 2024-09-23T11:15:06Z |
| format | Article |
| id | mit-1721.1/137022 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:15:06Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1370222023-12-06T21:45:08Z Breaking of 1RSB in Random Regular MAX-NAE-SAT Bartha, Zsolt Sun, Nike Zhang, Yumeng Massachusetts Institute of Technology. Department of Mathematics © 2019 IEEE. For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. In the unsatisfiable regime, it is natural to consider the problem of max-satisfiability: violating the least number of constraints. This is a combinatorial optimization problem on the random energy landscape defined by the problem instance. In the bounded density regime, a very precise estimate of the max-sat value was obtained by Achlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate the nature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) shows that for very large but bounded density, the max-sat value approaches the mean-field (complete graph) limit: This is conjectured to have an 'FRSB' structure where near-optimal configurations form clusters within clusters, in an ultrametric hierarchy of infinite depth inside the discrete cube. A stronger form of FRSB was shown in several recent works to have algorithmic implications (again, in complete graphs). Consequently we find it of interest to understand how the model transitions from 1RSB near the satisfiability threshold, to (conjecturally) FRSB at large density. In this paper we show that in the random regular NAE-SAT model, the 1RSB description breaks down by a certain threshold density that we estimate rather precisely. This is proved by an explicit perturbation in the 2RSB parameter space. The choice of perturbation is inspired by the 'bug proliferation' mechanism proposed by physicists (Montanari and Ricci-Tersenghi, 2003; Krzakala, Pagnani, and Weigt, 2004), corresponding roughly to a percolation-like threshold for a subgraph of dependent variables. 2021-11-01T18:11:14Z 2021-11-01T18:11:14Z 2019 2021-05-26T16:38:13Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137022 Bartha, Zsolt, Sun, Nike and Zhang, Yumeng. 2019. "Breaking of 1RSB in Random Regular MAX-NAE-SAT." Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2019-November. en 10.1109/FOCS.2019.00086 Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Bartha, Zsolt Sun, Nike Zhang, Yumeng Breaking of 1RSB in Random Regular MAX-NAE-SAT |
| title | Breaking of 1RSB in Random Regular MAX-NAE-SAT |
| title_full | Breaking of 1RSB in Random Regular MAX-NAE-SAT |
| title_fullStr | Breaking of 1RSB in Random Regular MAX-NAE-SAT |
| title_full_unstemmed | Breaking of 1RSB in Random Regular MAX-NAE-SAT |
| title_short | Breaking of 1RSB in Random Regular MAX-NAE-SAT |
| title_sort | breaking of 1rsb in random regular max nae sat |
| url | https://hdl.handle.net/1721.1/137022 |
| work_keys_str_mv | AT barthazsolt breakingof1rsbinrandomregularmaxnaesat AT sunnike breakingof1rsbinrandomregularmaxnaesat AT zhangyumeng breakingof1rsbinrandomregularmaxnaesat |