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.

See also Bill Gasarch’s overview of CCC 2010.

(Edit 20100622: added link to another overview.)


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a free website or blog at

%d bloggers like this: