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, CNDA(x) ≤ log |A| + O(log3|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 ACC0, 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.
Post a Comment