Friday, July 11, 2003
A Combinatorial Theorem Proven by Kolmogorov Complexity
During 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
Wednesday, July 09, 2003
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
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
- Kristoffer Hansen: Constant-width planar circuits compute exactly
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
Monday, July 07, 2003
Howdy 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
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.