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.

- Nikolai Vereshchagin: A combinatorial theorem proven by Kolmogorov complexity with no known direct combinatorial proof.
- Troy Lee: For every finite set A and x in A, CND
^{A}(x) ≤ log |A| + O(log^{3}|x|). CND is the nondeterministic version of Sipser's distinguishing complexity. - 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.
- Kristoffer Hansen: Constant-width planar circuits compute exactly
ACC
^{0}, constant depth circuits with a mod gate for some fixed composite. - 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.

## No comments:

## Post a Comment