The exact k-SAT threshold for large k
1 hour 1 min,
235.47 MB,
iPod Video
480x270,
29.97 fps,
44100 Hz,
527.03 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
Description: |
Sun, N (Massachusetts Institute of Technology)
Thursday 23 April 2015, 15:30-16:30 |
---|
Created: | 2015-04-24 18:07 |
---|---|
Collection: | Random Geometry |
Publisher: | Isaac Newton Institute |
Copyright: | Sun, N |
Language: | eng (English) |
Distribution: | World (downloadable) |
Explicit content: | No |
Aspect Ratio: | 16:9 |
Screencast: | No |
Bumper: | UCS Default |
Trailer: | UCS Default |
Abstract: | Co-authors: Jian Ding (University of Chicago), Allan Sly (University of California--Berkeley)
We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k0. That is, there is a single critical value α∗(k) such that a random k-SAT formula at clause-to-variable ratio α is with high probability satisfiable for α less than α∗(k), and unsatisfiable for α greater than α∗(k). The threshold α∗(k) matches the explicit prediction derived by statistical physicists on the basis of the one-step replica symmetry breaking (1RSB) heuristic. In the talk I will describe the main obstacles in computing the threshold, and explain how they are overcome in our proof. Joint work with Jian Ding and Allan Sly. |
---|
Available Formats
Format | Quality | Bitrate | Size | |||
---|---|---|---|---|---|---|
MPEG-4 Video | 640x360 | 1.96 Mbits/sec | 896.85 MB | View | Download | |
WebM | 640x360 | 470.36 kbits/sec | 210.15 MB | View | Download | |
iPod Video * | 480x270 | 527.03 kbits/sec | 235.47 MB | View | Download | |
MP3 | 44100 Hz | 252.44 kbits/sec | 112.79 MB | Listen | Download | |
Auto | (Allows browser to choose a format it supports) |