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

Laboratory of Theoretical Computer Science

A Conditional Information Inequality and its Combinatorial Applications

Vereshchagin N., Kaced T., Romashchenko A.

IEEE Transactions on Information Theory. 2018. Vol. 64. No. 5. P. 3610-3615.

Book chapter
On Emptiness and Membership Problems for Set Automata

Rubtsov A. A., Vyalyi M.

In bk.: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846. Springer, 2018. P. 295-307.

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.

Illustration for news: Laboratory of Theoretical Computer Science Researchers Get Grant from RFBR and Royal Society

Laboratory of Theoretical Computer Science Researchers Get Grant from RFBR and Royal Society

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.

The staff member of the laboratory participated in the workshop “Aperiodicity and Hierarchical Structures in Tilings”

Guilhem Gamard, research fellow of the international laboratory of theoretical computer science, took part in the workshop in Lyon, France.

Computer Science Faculty Hosts Conference on Theoretical Computer Science

On June 14 the workshop ‘Complexity of Computation, Communication, Descriptions, and Proofs’, organized by the Laboratory of Theoretical Computer Science, was held at HSE Faculty of Computer Sciences. The conference was organized as part of the major international conference ‘Computer Science in Russia’.

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.