Compressing in Moscow

This week finds me in Moscow for a pair of workshops, the Russian Workshop on Complexity and Model Theory and a workshop on Randomness, Information and Complexity. The latter celebrates the lives of Alexander Shen and Nikolay Vereshchagin on their 60th birthdays.

Alexander Shen might be best known in computational complexity for his alternate proof of IP = PSPACE. In 1989, Lund, Fortnow, Karloff and Nisan gave an interactive proof for the permanent, which got the entire polynomial-time hierarchy by Toda's theorem. But we didn't know how to push the protocol to PSPACE, we had a problem keeping degrees of polynomials low. Shamir had the first proof by looking at a specific protocol for PSPACE. Shen had the brilliant but simple idea to use a degree reducing operator, taking the polynomial modulo x²-x. The three papers appeared back-to-back-to-back in JACM.

Shen and Vereshchagin though made their careers with their extensive work on Kolmogorov complexity and entropy, often together. Vereshchagin and I have co-authored some papers together during our mutual trips to Amsterdam, including on Kolmogorov Complexity with Errors and how to increase Kolmogorov Complexity. My favorite work of Shen and Vereshchagin, which they did with Daniel Hammer and Andrei Romashchenko showed that every linear inequality that holds for entropy also holds for Kolmogorov complexity and vice-versa, the best argument that the two notions of information, one based on distributions, the other based on strings, share strong connections.

Today is Russia Day that celebrates the reestablishment of Russia out of the Soviet Union in 1990. Just like how the British celebrate their succession from the US in 1776 I guess. But I'm celebrating Russia day by honoring these two great Russians. Congrats Sasha and Kolya!