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.
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.
Stepan Kuznetsov solved a problem by Buszkowski (2007) on the Lambek calculus extended with iteration, or Kleene star, axiomatised by means of
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