Seminars: N. K. Vereshchagin, Short lists with short programs in short time

SEMINARS


Kolmogorov seminar on computational complexity and descriptive complexity December 17, 2012 16:45, Moscow

Short lists with short programs in short time N. K. Vereshchagin
Abstract: We show how to construct for each string $x$ a list of size $O( \|x\|^2 )$ containing a $O(1)$-short program for $x$. The proof is based on the construction of graphs with online matching, introduced by Musatov, Romashchenko, and Shen.