• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Mathematical methods in computational complexity theory and algorithm game theory

Priority areas of development: IT and mathematics, mathematics
2020
The project has been carried out as part of the HSE Program of Fundamental Studies.

Publications:


Durand B., Shen A., Vereshchagin N. On the Structure of Ammann A2 Tilings // Discrete and Computational Geometry. 2020. Vol. 63. P. 577-606. doi
Chistikov D., Mikhail Vyalyi. Re-pairing brackets, in: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020. Association for Computing Machinery (ACM), 2020. P. 312-326. doi
Gurvich V., Vyalyi M. Computational hardness of multidimensional subtraction games, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings Vol. 12159. Springer, 2020. doi P. 237-249. doi
Grigoriev D., Podolskii V. V. Tropical Combinatorial Nullstellensatz and Sparse Polynomials // Foundations of Computational Mathematics. 2020. Vol. 20. No. 4. P. 753-781. doi
Chistopolskaya A., Podolskii V. V. On the Decision Tree Complexity of Threshold Functions, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings Vol. 12159. Springer, 2020. doi P. 198-210. doi
Boros E., Gurvich V., Milanic M. Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1‐Sperner hypergraphs // Journal of Graph Theory. 2020. Vol. 94. No. 3. P. 364-397. doi
Vereshchagin N. Descriptive complexity of computable sequences revisited // Theoretical Computer Science. 2020. Vol. 809. P. 531-537. doi