28 August 2010

deterministic 3SAT in O*(1.334^n) time

Filed under: Commentary — András Salamon @ 0:31

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…)


27 August 2010

InfiniteStack / TheoryOverflow / CSTheory public beta

Filed under: Commentary — András Salamon @ 22:46

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

A simple reduction

Filed under: Commentary — András Salamon @ 3:01
Tags: ,

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

P not equal to NP (P ≠ NP) consequences

Filed under: Commentary,Question — András Salamon @ 20:43

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

Deolalikar’s manuscript

Filed under: Commentary — András Salamon @ 17:39
Tags: ,

Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled P \ne NP (or in words, “P is not equal to NP”). (more…)

3 August 2010

TheoryOverflow nearing beta

Filed under: Commentary — András Salamon @ 21:57

The TheoryOverflow site was proposed a few weeks ago for discussion of research-level questions in theoretical computer science. I am committed to using this service, and encourage others in the community to try it out.

Create a free website or blog at