• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Теоретическая информатика

2017

Цели научного исследования:

  • Развитие новых методов и концепций в теории игр и комбинаторике.
  • Изучение разных вариантов колмогоровской сложности и их взаимосвязи.
  • Продолжение изучения того, насколько переносимы классические теоремы Колмогоровской сложности на сложность с ограничением ресурсов.
  • Изучение алгоритмической сложности алгебраических задач.
  • Изучение различных вопросов коммуникационной сложности.
  • Исследование автоматов и контекстно-свободных языков.

Публикации по проекту:


Mikhail N. Vyalyi, Voronenko A. A. Lower estimate for the cardinality of the domain of universal functions for the class of linear Boolean functions / Пер. с рус. // Discrete Mathematics and Applications. 2017 doi
Rubtsov A. A., Vyalyi M. On Computational Complexity of Set Automata, in: Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. Cham : Springer International Publishing, 2017. doi P. 332-344. doi
M.N.Vyalyi, Lawrencenko S., Zgonnik L. Grunbaum coloring and its generalization to arbitrary dimension // Australasian Journal of Combinatorics. 2017. Vol. 67. No. 2. P. 119-130.
M.N.Vyalyi, Babenko A. On the linear classification of even and odd permutation matrices and the complexity of computing the permanent / Пер. с рус. // Computational Mathematics and Mathematical Physics. 2017. Vol. 57. No. 2. P. 362-371. doi
M.N.Vyalyi, Khuziev I. Fast protocols for leader election and spanning tree construction in a distributed network / Пер. с рус. // Problems of Information Transmission. 2017. Vol. 53. No. 2. P. 183-201. doi
Vereshchagin N., Bauwens B. F., Makhlin A., Zimand M. Short lists with short programs in short time // Computational Complexity. 2017 doi