4 April 2011

Beware normal hypergraph landmine

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

In a classic 1972 paper László Lovász proved the (little) Perfect Graph Theorem, that the complement of every perfect graph is perfect. Another theorem from this paper links normal hypergraphs and perfect graphs. Perhaps this discussion will help someone avoid unnecessary grey hairs.


9 November 2010

New ACC circuit lower bounds

Filed under: Commentary — András Salamon @ 17:25

Ryan Williams recently published a draft proving new lower bounds for ACC circuits. ACC (often known as ACC0) is the class of constant depth circuits with unbounded fan-in gates, where the usual AND/OR/NOT gates are supplemented by MODm gates for some constant m.

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.

Next Page »

Blog at