Tuesday, April 02, 2013

LICS 2013 Accepted Papers

This is not news anymore, but the list of accepted papers for LICS 2013 is available here.

As usual, the accepted papers look very interesting and I hope to find the time to read several of them when they become available. (This might be wishful thinking. It seems that finding time to read papers is getting harder by the day, alas.)

For what it is worth, here are two papers that immediately caught my attention browsing through the list of accepted papers and that are available on line.
To whet your appetite, here is what is probably the main result in the latter paper.
Theorem: In sets with equality atoms, there is a language that is decidable in nondeterministic polynomial time, but not deterministically semi-decidable.
Before you get carried away, here is what the authors write below the statement of this theorem.
A consequence of the theorem is that, with atoms, P is not equal to NP. It is not our intention to play up the significance of this result. In a sense, the theorem is too strong for its own good: it shows that computation with atoms is so different from computation without atoms, that results on the power of nondeterminism in the presence of atoms are unlikely to shed new light on the power of nondeterminism without atoms.
Congratulations to all the authors of accepted papers.

2 comments:

Anonymous said...

Can someone help me refine my mental map of TCS.

What is the relation between the scope of LICS, and that mysterious entity known as 'Theory B'?

E. T. said...

@anon 1: LICS is the major conference for "Theory B", and so its scope "defines" the major trends of the field.
Nevertheless, LICS has also some non-trivial intersection with Theory A, via complexity: descriptive complexity, proof complexity, bounded arithmetic, etc.