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

Laboratory of Theoretical Computer Science

2

January 31

In January, the laboratory of theoretical computer science planned to hold two seminars. Ivan Arzhantsev spoke at the first seminar. At the second seminar, our colleague from Nizhny Novgorod, Dmitry Sirotkin, spoke about his results.

February 12, 2018

Researchers from the HSE Laboratory of Theoretical Computer Science have won a competition organized by the Russian Foundation for Basic Research (RFBR) and the Royal Society of London for Improving Natural Knowledge.
Publications
Article
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

Podolskii V. V., Kulikov A. S.

Theory of Computing Systems. 2019. Vol. 63. No. 5. P. 956-986.

Book chapter
Two Characterizations of Finite-State Dimension

Kozachinskiy A., Shen A.

In bk.: Fundamentals of Computation Theory, 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings. Vol. 11651. Springer, 2019. P. 80-94.

Working paper
Stochasticity in Algorithmic Statistics for Polynomial Time

Vereshchagin N., Milovanov A.

Electronic Colloquium on Computational Complexity. Technical report . Weizmann Institute of Science, 2017. No. TR17-043.

The Laboratory  of Theoretical Computer Science  was founded in December 2015. Structurally, it is a part of Big Data and Information Retrieval School at the Faculty of Computer Science.

The main research directions of the laboratory are computational complexity, algorithmic information theory, algorithmic statistics, combinatorial optimization, algorithmic aspects of game theory.