Теоретическая информатика

About Theoretical Computer Science Department

Department of theoretical computer science founded in 1994. The members of the department are specialists in different branches of mathematics and theoretical computer science: combinatorics, complexity of computations, probabilistic methods, mathematical logics, formal methods of program analysis, logical programming, mathematical cryptography.

Main directions of research:

  • Complexity of computations, analysis and development of efficient algorithms for different discrete optimization problems. We consider mainly computationally hard (NP-hard) problems and propose modern ways to solve them efficiently using:
    • randomized algorithms;
    • approximation algorithms;
    • inapproximability thresholds;
    • average case analysis;
    • different heuristics (genetic algorithms, local search, etc).
  • Foundations of software security including obfuscation theory, computations with encrypted (encoded) data, theoretical foundations of cryptography.

Team members teach some courses for students of Lomonosov Moscow State University and Moscow Institute for Physics and Technology:

  • Complexity of combinatorial algorithms.
  • Distributed algorithms.
  • Mathematical logics.
  • Mathematical cryptography.
  • Theoretical foundations of numerical analysis.
  • Efficient algorithms.
  • Lattices, algorithms and modern cryptography.