• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Mathematical methods in computational complexity theory and algorithm game theory

Priority areas of development: IT and mathematics, mathematics
2020

Publications:


Vereshchagin N. Descriptive complexity of computable sequences revisited // Theoretical Computer Science. 2020. Vol. 809. P. 531-537. doi
Durand B., Shen A., Vereshchagin N. On the Structure of Ammann A2 Tilings // Discrete and Computational Geometry. 2020. Vol. 63. P. 577-606. 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
Boros E., Gurvich V., Bao Ho Nhan, Makino K. On the Sprague–Grundy function of extensions of proper NIM // International Journal of Game Theory. 2020. doi
Podolskii V. V., Sherstov A. A. Inner Product and Set Disjointness: Beyond Logarithmically Many Parties // ACM Transactions on Computation Theory. 2020. Vol. 12. No. 4. P. 26-. 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
Chistikov D., Mikhail V. 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. С. 312-326. 
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.: Springer, 2020. С. 237-249. 
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.: Springer, 2020. С. 198-210. 
Vereshchagin N. A family of non-periodic tilings of the plane by right golden triangles / Cornell University. Series math "arxiv.org". "arXiv:2007.10658". 2020.