Friday, November 15, 2013 — 3:30 PM to 4:30 PM EST

Solution geometry of a random k-XORSAT near the clustering threshold

Speaker: Jane Gao
Affiliation: University of Toronto
Room: Mathematics and Computer Building (MC) 5158

Abstract

Since the early 2000s statistical physicists have predicted, using a non-rigorous technique called the "cavity method", that the solution spaces of many random constraint satisfiability problems (CSPs) and combinatorial problems have a clustering phenomenon. When the density of a random CSP (the number of constraints divided by the number of variables) is below a critical value c*, all solutions form a single well-connected cluster: one can "walk" from one solution to any other, via a path of solutions, by changing a small number of variables at a time. Above c*, solutions are partitioned into exponentially many well-connected, well-separated clusters: the Hamming distance between any two solutions in different clusters is Ω(n). This clustering phenomenon was proved to be true for several random CSPs by mathematicians; it gives insight into the existence of an "algorithmic barrier" observed in many CSPs. In this talk, I will depict the clustering of random k-XORSAT solutions, in particular when the k-XORSAT density is approaching c*, the clustering threshold: we investigate how clusters are born.
 
This is joint work with Mike Molloy.
Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)