Friday, October 25, 2013 — 3:30 PM to 4:30 PM EDT

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

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

Abstract:

Since early 2000s statistical physicists 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 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 O(log n) 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). These clustering phenomena were proved to be true for several random CSPs by mathematicians. In this talk, I will depict clustering of random k-XORSAT solutions, in particular when its 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)