# Constraints

## 4 April 2011

### Beware normal hypergraph landmine

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

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.
(more…)

## 9 November 2010

### New ACC circuit lower bounds

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

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.
(more…)

## 28 August 2010

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

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

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

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

## 5 July 2010

### FOCS 2010 accepted papers

Filed under: Commentary — András Salamon @ 1:38
Tags: ,

The FOCS 2010 accepted papers were announced a few days ago. This is a quick summary of a few papers that caught my eye.
(more…)

## 14 June 2010

### CCC 2010

Filed under: Commentary — András Salamon @ 20:55
Tags: ,

There were several interesting papers at Computational Complexity 2010. Here are just a few, the full list of accepted papers is here. (more…)

Next Page »

Create a free website or blog at WordPress.com.