Inside the clustering window for random linear equations

Pu Gao, Michael Molloy

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

We study a random system of cn linear equations over n variables in GF(2), where each equation contains exactly r variables; this is equivalent to r-XORSAT. Previous work has established a clustering threshold, cr for this model: if cc− for any constant > 0 then with high probability all solutions form a well-connected cluster; whereas if cc+, then with high probability the solutions partition into well-connected, well-separated clusters (with probability tending to 1 as n→∞). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly nonrigorous techniques from statistical physics. We extend that study to the range cc+ o(1), and prove that the connectivity parameters of the r-XORSAT clusters undergo a smooth transition around the clustering threshold.
Original languageEnglish
Pages (from-to)197-218
Number of pages22
JournalRandom Structures & Algorithms
Volume52
Issue number2
DOIs
Publication statusPublished - 1 Mar 2018

Keywords

  • clustering threshold
  • critical window
  • phase transition
  • random XORSAT
  • solution geometry

Cite this