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 leaves. This universal tree has polynomial size and can be constructed in polynomial time .

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 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 should be an equality.

See also Bill Gasarch’s overview of CCC 2010.

*(Edit 20100622: added link to another overview.)*

### Like this:

Like Loading...

*Related*

## CCC 2010

Tags: conferences, papers

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

symmetricpolynomial-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 leaves. This universal tree has polynomial size and can be constructed in polynomial time .

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 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 should be an equality.

See also Bill Gasarch’s overview of CCC 2010.

(Edit 20100622: added link to another overview.)## Like this:

Related