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

Laboratory of Theoretical Computer Science

Classical and quantum computation

Kitaev A. Y., Shen A. H., Vyalyi M.

AMS, 2002.

A convex programming-based algorithm for mean payoff stochastic games with perfect information In print

Boros E., Elbassioni K., Gurvich V. et al.

Optimization Letters. 2017.

Book chapter
Computing majority by constant depth majority circuits with low fan-in gates

Kulikov A., Podolskii V. V.

In bk.: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, Germany. Vol. 66. Leipzig: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 49:1-49:14.

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.

Silver medal in International Mathematical Competition for students

On July 25-31 in Bulgaria was held an International Mathematical Competition for University Students (IMС 2016).

Conference "Mathematical logic, algebra and computation"

On July 18-19 a conference “Mathematical logic, algebra and computation" was held in Moscow. It was organized by the Steklov Mathematical Institute of Russian Academy of Science. The conference was dedicated to the 85th anniversary of academician S. I. Adian.

International Computer Science Symposium in Russia 2016

On June 9-13 Computer Science Symposium in Russia (CSR) 2016 was held in St. Petersburg.

Workshop on Theoretical Computer Science

On April 6-8 the laboratory held Workshop on Theoretical Computer Science. The workshop was a part of Computer Science Days and the celebration of the faculty's birthday.