# Constraints

## 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.

Allender and Lange, Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. This shows that LogCFL coincides with the class of languages accepted by a symmetric polynomial-time bounded auxiliary pushdown automaton.

Hrubeš, Wigderson, Yehudayoff, Relationless completeness and separations. Of special interest is Theorem 5, showing how to construct the smallest tree which contains as minors all binary trees with $n$ leaves. This universal tree has polynomial size $O(n^4)$ and can be constructed in polynomial time $O(n^4)$.

Marx, Completely inapproximable monotone and antimonotone parameterized problems. Shows that either weighted monotone circuit satisfiability has no FPT approximation algorithm (for any approximation ratio), or FPT = W[1]. Most people seem to believe that FPT $\ne$ W[1] holds, and Dániel’s result serves to further increase this belief in the unlikeliness of FPT = W[1]. (I discussed this kind of conditional result in a previous post, Is P=NP a reasonable hypothesis?) Note that the abstract in the original version has a typo, the $\ne$ should be an equality.