The Rump Session

One of the nice aspects of the Complexity Conference, the rump session, I don't see at many other conferences. Here anyone who wants to, mostly students, get ten minutes to lay out their latest research.

This year we had one of the best rump sessions ever with five really neat results, listed below. Don't worry if you don't immediately understand the results, I will talk about some of them in more detail in future posts. All but Vereshchagin are students.

1. Nikolai Vereshchagin: A combinatorial theorem proven by Kolmogorov complexity with no known direct combinatorial proof.
2. Troy Lee: For every finite set A and x in A, CND^A(x) ≤ log |A| + O(log³|x|). CND is the nondeterministic version of Sipser's distinguishing complexity.
3. Scott Aaronson: Everything efficiently quantumly computable with a polynomial amount of arbitrarily entangled quantum advice can be simulated in exponential time with a polynomial amount of classical advice.
4. Kristoffer Hansen: Constant-width planar circuits compute exactly ACC⁰, constant depth circuits with a mod gate for some fixed composite.
5. Samik Sengupta: If co-NP has an Arthur-Merlin game with a polylogarithmic number of rounds then co-NP is in NP with quasipolynomial advice and the exponential hierarchy collapses at the third level.