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

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

2016

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

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


Milovanov A. Algorithmic Statistics: Normal Objects and Universal Models, in: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings Vol. 9691: Lecture Notes in Computer Science. Switzerland : Springer, 2016. doi P. 280-293. doi
Milovanov A. Algorithmic Statistics, Prediction and Machine Learning, in: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54. P. 1-13. doi
Gurvich V., Endre B., Khaled E., Kazuhisa M., Vladimir O. Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden $2 \times 2$ subgames // International Journal of Game Theory. 2016. Vol. 45. No. 4. P. 1111-1131. doi
Vereshchagin N. Algorithmic Minimal Sufficient Statistics: a New Approach // Theory of Computing Systems. 2016. Vol. 58. No. 3. P. 463-481. doi
Brody J., Buhrman H., Koucký M., Loff B., Speelman F., Vereshchagin N. Towards a Reverse Newman’s Theorem in Interactive Information Complexity // Algorithmica. 2016. Vol. 76. No. 3. P. 749-781. doi
Kozachinskiy A. On Slepian–Wolf Theorem with Interaction, in: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings Vol. 9691: Lecture Notes in Computer Science. Switzerland : Springer, 2016. doi P. 207-222. doi
Bienvenu L., Desfontaines D., Shen A. Generic algorithms for halting problem and optimal machines revisited // Logical Methods in Computer Science. 2016. Vol. 12. No. 2 doi