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

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

2018

Задачи исследования:

  • Разрешимость по Нэшу и изучение алгоритмов поиска ситуаций равновесия в позиционных и стохастических играх.

  • Изучение двойственных графов на ориентируемых и неориентированных поверхностях. Нахождение описания невозможных би-векторов валентностей.

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

  • Исследование дескриптивной сложности разделения регулярных языков.Оценка сложности вычисления знака перестановочной матрицы в слабых моделях вычисления и эффективность метода символического детерминанта для подсчета числа совершенных паросочетаний.

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

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

  • Изучение возможности дерандомизации алгоритмов, решающих задачу равенства нулю многочлена.

  • Обобщение теоремы Goos, Pitassi, Watson о связи коммуникационной сложности композиций Булевых функций с разрешающей сложностью.

  • Перенос слабо-полиномиального алгоритма поиска потока Гольдберга-Рао на кососимметрические сети.

  • Поиск кратчайшего пути в графе в метрике k-sum (сумма k максимальных рёбер пути, где k - заранее определённый параметр).Улучшение оценок на вероятность возрастания колмогоровской сложности слова при случайной замене небольшой константной доли битов в нём.

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


Bienvenu M., Kikot S., Kontchakov R., Podolskii V. V., Zakharyaschev M. Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity // Journal of the ACM. 2018. Vol. 65. No. 5. P. 28:1-28:51. doi
Podolskii V. V., Grigoriev D. Tropical Effective Primary and Dual Nullstellensätze // Discrete and Computational Geometry. 2018. Vol. 59. No. 3. P. 507-552. doi
Kozachinskiy A. On Slepian–Wolf Theorem with Interaction // Theory of Computing Systems. 2018. Vol. 62. No. 3. P. 583-599. doi
Romashchenko A., Kaced T., Vereshchagin N. A Conditional Information Inequality and its Combinatorial Applications // IEEE Transactions on Information Theory. 2018. Vol. 64. No. 5. P. 3610-3615. doi
Вялый М. Н. Сложность вычисления знака перестановки в модели разрешающих деревьев и подсчет совершенных паросочетаний в двудольных графах // В кн.: Труды X международной конференции "Дискретные модели в теории управляющих систем". Москва и Подмосковье, 23-25 мая 2018 г. / Отв. ред.: В. Алексеев, Д. Романов, Б. Данилов. М. : МАКС Пресс, 2018. С. 94-97.
Rubtsov A. A., Vyalyi M. On Emptiness and Membership Problems for Set Automata, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi P. 295-307. doi
Klenin E., Kozachinskiy A. One-Sided Error Communication Complexity of Gap Hamming Distance, in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) Vol. 117. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. doi P. 1-15. doi
Kozachinskiy A. Recognizing Read-Once Functions from Depth-Three Formulas, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi P. 232-243. doi
Kozachinskiy A. From Expanders to Hitting Distributions and Simulation Theorems, in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) Vol. 117. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. doi P. 1-15. doi
Gurvich V. Backward induction in presence of cycles // Journal of Logic and Computation. 2018. Vol. 28. No. 7. P. 1635-1646. doi
Milovanov A. Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms, in: Sailing Routes in the World of Computation. Springer, 2018. doi P. 287-296. doi
Rubtsov A. A. A Structural Lemma for Deterministic Context-Free Languages, in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. Cham : Springer, 2018. doi P. 553-565. doi
Gurvich V., Nhan Bao H. On tame, pet, domestic, and miserable impartial games // Discrete Applied Mathematics. 2018. Vol. 243. P. 54-72. doi
Posobin G. I., Shen A., Andreev M. Plain stopping time and conditional complexities revisited, in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) Vol. 117. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. doi P. 1-24. doi
Gurvich V., Andrade D. V., Boros E. On graphs whose maximal cliques and stable sets intersect, in: Optimization Problems in Graph Theory Book 139. Springer, 2018. doi P. 3-63. doi
Gurvich V. Complexity of Generation, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi P. 1-14. doi
Vereshchagin N., Bauwens B. F., Makhlin A., Zimand M. Short lists with short programs in short time // Computational Complexity. 2018. Vol. 27. No. 1. P. 31-61. doi
Gurvich V., Boros E., Elbassioni K., Makino K. A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games // Dynamic Games and Applications. 2018. Vol. 8. No. 1. P. 22-41. doi
Gurvich V., Boros E., Milanič M., Oudalov V., Vičič J. A three-person deterministic graphical game without Nash equilibria // Discrete Applied Mathematics. 2018. Vol. 243. P. 21-38. doi
Gurvich V., Boros E., Manthey B., Elbassioni K., Fouz M., Makino K. Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions // Algorithmica. 2018. Vol. 80. No. 11. P. 3132-3157. doi
Gurvich V., Boros E., Kazuhisa M., Mursic P., Nhan Bao H. On the Sprague-Grundyfunction of Exact k- Nim // Discrete Applied Mathematics. 2018. Vol. 239. P. 1-14. doi