Discrete Mathematics and Mathematical Logic

Discrete mathematics and mathematical logic are important areas of mathematics. On the one hand, these areas address foundational aspects of mathematics, such as the problems of existence and efficiency of algorithms, or provability or non- provability of mathematical statements. On the other hand, they are especially relevant for applications of mathematical methods in computer science and data science. At SIMC, among other topics, we study asymptotic combinatorics, combinatorial and geometric group theory, computational complexity theory, proof theory, non-classical logics, provability logic and formal arithmetic, branching processes, random walks.

Research areas: asymptotic combinatorics, combinatorial and geometric group theory, computational complexity theory, structural proof theory, non- classical logics, provability logic and formal arithmetic, branching processes, random walks.

2020

Vladimir Podolskii and Alexander Kozachinsky proved an open conjecture in circuit complexity theory concerning the depth of monotone boolean circuits computing the MAJORITY function of $n$ boolean variables. They explicitly showed how to compute this function by a circuit of logarithmic depth consisting of MAJORITY functions of only three variables.

  1. A. Kozachinskiy, V. Podolskii, “Multiparty Karchmer-Wigderson games and threshold circuits”, 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), 169 (2020), 24, 23 pp.

Stepan Kuznetsov solved a problem by Buszkowski (2007) on the Lambek calculus extended with iteration, or Kleene star, axiomatised by means of an $\omega$-rule. He proved that the derivability problem for this calculus is $\Pi_1^0$-hard.

  1. S. Kuznetsov, “Complexity of the infinitary Lambek calculus with Kleene star”, Review of Symbolic Logic, (2020), published online, 28 pp.

Fedor Pakhomov and James Walsh have isolated a natural well-founded partial order structure on the boolean algebra of sentences of second-order arithmetic defined in terms of $\Pi_1^1$-reflection principles. Their results clarify the relationship between reflection and well-foundedness, ordinal ranks and proof-theoretic ordinals of second-order systems, and establish new links between different approaches to proof-theoretic ordinal analysis.

  1. F. Pakhomov, J. Walsh, “Reflection ranks and ordinal analysis”, Journal of Symbolic Logic, (2020), published online, 34 pp.


Highlights:
  • Fedor Pakhomov was awarded the Moscow Mathematical Society prize for young mathematicians in 2020.