This work is licensed under a
Creative Commons License.
|
Friday, July 11, 2003
A Combinatorial Theorem Proven by Kolmogorov ComplexityDuring the rump session of complexity, Nikolai Vereshchagin presented a combinatorial theorem that he proved using Kolmogorov complexity. Let A be a finite subset of N×N where N is the set of natural numbers. Let m be the size of A, r be the number of nonempty rows of A and c the number of nonempty columns.
We say A is good is every nonempty row has m/r elements and every nomempty column has m/c elements of A. A rectangle has this property, as does a diagonal. We say A is k-good if every nonempty row has at most km/r elements and every nonempty column has at most km/c elements. A is good if it is 1-good.
Vereshchagin's Theorem: There is a constant c such that for all finite subsets B of N×N with n = log |B| there is a partition of B into at most nc sets each of which is nc-good.
Vereshchagin asks whether there is a purely combinatorial proof of this theorem. If you know of one let me know.
For those who know some Kolmogorov complexity, let me sketch the proof: We label each point (x,y) of B with the following five values: KB(x,y), KB(x), KB(y), KB(x|y) and KB(y|x). We partition the points into sets with the same labels. Standard counting arguments from Kolmogorov complexity show that each partition is nc-good for some c.
5:22 AM # Comments []
Wednesday, July 09, 2003
The Rump SessionOne 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.
- 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.
1:59 AM # Comments []
Monday, July 07, 2003
Coming HomeHowdy from Aarhus, Denmark where I am attending the 18th Annual IEEE Conference on Computational Complexity. As readers of this weblog probably have figured out, this is, by far, my favorite conference. Complexity is smaller and more relaxed than the broader theory conferences like STOC and FOCS. I know most of the participants and have a genuine interest in the most of the papers here. While elsewhere theorists try more and more to find connections to applied areas, here we are happy to focus on the fundamental power of efficient computation.
During the rest of the year I attend some conferences in broader areas or in areas that are not in my major focus. But coming to Complexity is coming home, and it always feels great to be back where I belong.
6:45 AM # Comments []