<div dir="ltr">This talk is taking place at an unusual time and place.<div>It will be Oct 28 at 10:30 in DL 431.</div><div><br></div><div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13.3333px;line-height:normal"><font size="3"><b>Oct 28: Nike Sun (MIT) 10:30 in DL 431:</b> <font face="arial, sans-serif">&quot;</font></font><span style="color:rgb(0,0,0);font-size:16px;line-height:24px"><font face="arial, sans-serif">The exact k-SAT threshold for large k&quot;</font></span></div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13.3333px;line-height:normal"><span style="color:rgb(0,0,0);font-size:16px;line-height:24px"><font face="arial, sans-serif"><br></font></span></div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13.3333px;line-height:normal"><div style="color:rgb(0,0,0);font-size:16px;line-height:24px"><font face="arial, sans-serif">We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k(0). That is, there is a single critical value c_*(k) such that a random k-SAT formula at clause-to-variable ratio c is with high probability satisfiable for c &lt; c_*(k), and unsatisfiable for c &gt; c_*(k). The threshold c_*(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.</font></div><div style="color:rgb(0,0,0);font-size:16px;line-height:24px"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0);font-size:16px;line-height:24px"><font face="arial, sans-serif">Joint work with Jian Ding and Allan Sly.</font></div><div><font face="arial, sans-serif"><br></font></div></div></div></div>