Robin Moser and Dominik Scheder have put an end to the stream of slight improvements in derandomizing Schöning’s randomized k-SAT algorithm from 1999. (more…)
28 August 2010
27 August 2010
The initial batch of questions and answers at the Theoretical Computer Science Q&A forum seems promising. I encourage theoretical computer scientists to take a look, and to consider contributing.
15 August 2010
Recent online discussion about computational complexity included the notion that the structure of solutions of SAT might be useful in proving separation results. I want to point out a further obstacle to this idea. (more…)
13 August 2010
During the discussion about Vinay Deolalikar’s manuscript, many people commented about the consequences that would follow if we knew that P ≠ NP. I’d like to discuss these consequences in a little more detail.
9 August 2010
Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled (or in words, “P is not equal to NP”). (more…)