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

Mathematical methods in algorithm theory and computational complexity

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

Publications:


Vyalyi M., Леонтьев В. К. Geometry of Translations on a Boolean Cube / Пер. с рус. // Problems of Information Transmission. 2019. Vol. 55. No. 2. P. 152-173. doi
Boros E., Cepek O., Gurvich V. Separable discrete functions: Recognition and sufficient conditions // Discrete Mathematics. 2019. Vol. 342. No. 5. P. 1275-1292. doi
Durand B., Shen A., Vereshchagin N. On the Structure of Ammann A2 Tilings // Discrete and Computational Geometry. 2019. P. 1-30. doi
Buhrman H., Torenvliet L., Unger F., Vereshchagin N. Sparse Selfreducible Sets and Nonuniform Lower Bounds // Algorithmica. 2019. Vol. 81. No. 1. P. 179-200. doi
Rubtsov A. A., Vyalyi M. On Computational Complexity of Set Automata // Information and Computation. 2019
Rubtsov A. A. Framework for Formal Languages, in: Proceedings of Language and Automata Theory and Applications 2020. Springer, 2020.
Milovanov A. On Algorithmic Statistics for Space-bounded Algorithms // Theory of Computing Systems. 2019. Vol. 63. No. 4. P. 833-848. doi
Milovanov A. #P-completeness of counting roots of a sparse polynomial // Information Processing Letters. 2019. Vol. 142. P. 77-79. doi
Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P. Sprague–Grundy function of symmetric hypergraphs // Journal of Combinatorial Theory, Series A. 2019. Vol. 165. No. 7. P. 176-186. doi