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

2017

Руководитель: Верещагин Николай Константинович, Гурвич Владимир Александрович

Подразделение: Международная лаборатория теоретической информатики

Проект выполнен в рамках Программы фундаментальных исследований ВШЭ.

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

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

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

Podolskii V. V., Zakharyaschev M., Bienvenu M., Kikot S., Ryzhikov V., Kontchakov R. The complexity of ontology-based data access with OWL2QL and bounded treewidth queries, in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems Part F127745. ACM, 2017. P. 201-216. doi

Vereshchagin N., Milovanov A. Stochasticity in Algorithmic Statistics for Polynomial Time, in: 32nd Computational Complexity Conference. Вадерн : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18. doi

Milovanov A. On Algorithmic Statistics for Space-Bounded Algorithms, in: Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017) Vol. 10304. Luxemburg : Springer, 2017. doi P. 232-244. doi

Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017) Vol. 10304. Luxemburg : Springer, 2017. doi

Kulikov A., Podolskii V. V. Computing majority by constant depth majority circuits with low fan-in gates, in: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, Germany Т. 66. Лейпциг : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 1-14. doi

Vereshchagin N. Short lists with short programs from programs of functions and strings // Theory of Computing Systems. 2017. Vol. 61. No. 4. P. 1440-1450. doi

Boros E., Elbassioni K., Gurvich V., Makino K. A convex programming-based algorithm for mean payoff stochastic games with perfect information // Optimization Letters. 2017. Vol. 11. No. 8. P. 1499-1512. doi

Voronenko A. A., Mikhail N. Vyalyi. Lower estimate for the cardinality of the domain of universal functions for the class of linear Boolean functions / Пер. с рус. // Discrete Mathematics and Applications. 2017. P. 319-324. doi

Gerasimova O., Podolskii V. V., Kikot S., Zakharyaschev M. On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom, in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.. Aachen : CEUR Workshop Proceedings, 2017. Ch. 19. P. 1-12.

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

Milovanov A. Some Properties of Antistochastic Strings // Theory of Computing Systems. 2017. Vol. 61. No. 2. P. 521-535. 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.

Boros E., Elbassioni K., Gurvich V., Makino K. A nested family of k-total effective rewards for positional games // International Journal of Game Theory. 2017. Vol. 46. No. 1. P. 263-293. doi

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

Gerasimova O., Kikot S., Podolskii V. V., Zakharyaschev M. More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom, in: Proceedings of the 8th international Conference on Knowledge Engineering and Semantic Web. Berlin : Springer, 2017. doi P. 143-158. doi

Podolskii V. V., Grigoriev D. Tropical Combinatorial Nullstellensatz and Fewnomials Testing // Lecture Notes in Computer Science. 2017. Vol. 10472. P. 284-297. 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, 2017. doi P. 332-344. doi