Short lists with short programs from programs
255 views · Published 28 April 2016 · 1:27:30 · Indexed 20 November 2026
Channel: ФКН НИУ ВШЭ · 2016 · Education
Let f_p be an optimal Goedel numbering of the family of computable functions (in Schnorr's sense), where p ranges over binary strings. Assume that a list of strings L(p) is computable from p and for all p contains an f-program for f_p whose length is at most eps bits larger than the length of shortest f-programs for f_p. We show that for infinitely many p the list L(p) must have exponential in (|p|-eps) strings. Here eps is an arbitrary function of p. Speaker: Professor Nikolay Vereshchagin, head of the Laboratory of Theoretical Computer Science, HE University. Workshop on Theoretical Computer Science 2016: https://cs.hse.ru/en/big-data/tcs-lab/tcs2016/ Faculty of Computer Science: https://cs.hse.ru/en/ Follow us: https://www.facebook.com/hsefcs, https://twitter.com/CS_HSE
More from this channel
-
1:18:31
[Коллоквиум]: On scale invariance, multifractal formalism, and their applications
-
1:09:43
[Коллоквиум]: Resourse Allocation in the Cloud - Assaf Schuster, Techion
-
1:08:04
[ИТ-лекторий] Занимательная прикладная аналитика в Яндексе
-
1:17:41
[Коллоквиум]: Probabilistic graphical models: Factor graphs and more
-
1:05:46
[Коллоквиум]: Process Mining: Data Science in Action - Wil van der Aalst
-
2:18
[Презентация факультета в ДК ЗИЛ]: Григорий Бакунов, директор по распрост. инф. технологий Яндекс
-
2:55
[Презентация факультета в ДК ЗИЛ]: Григорий Канторович, проректор по работе с абитуриентами ВШЭ
-
11:34
[Презентация факультета в ДК ЗИЛ]: Иван Аржанцев, декан факультета компьютерных наук