Random graphs, extremal combinatorics, descriptive complexity, model theory
Sept 2010 - present: MIPT, Department of Discrete Mathematics, Associate Professor.
May 2016 - present: MIPT, Laboratory of advanced combinatorics and network applications, Senior Researcher.
Jan 2020 - present: MIPT, Laboratory of Combinatorial and Geometric Structures, Senior Researcher.
May 2018 - present, The Russian Presidential Academy of National Economy and Public Administration, Researcher.
Jan 2018 - present, Caucasus mathematical center, Adyghe State University.
Nov 2019 - present, Mathematical Center in Akademgorodok, Researcher.
May 2010 - Oct 2014, Lomonosov Moscow State University, Department of Mathematical Statistics and Random Processes, Junior Researcher.
May 2011 - May 2017, Yandex, Researcher.
July 2016 - Nov 2017, RUDN University, Center of Mathematical modeling for interdisciplinary research, Researcher.
Selected journal publications
- Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020)
- Existential monadic second order logic of undirected graphs: a disproof of the Le Bars conjecture, Annals of Pure and Applied Logic, 170 (2019) 505-514.
- Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, Volume 20, Issue 2, 2019.
- On the First-Order Complexity of Induced Subgraph Isomorphism, Logical Methods in Computer Science, Volume 15, Issue 1, 2019, 25:1--25:24.
- Zero-one laws for k-variable first-order logic of sparse random graphs, 2019, Discrete Applied Mathematics.
- First order sentences about random graphs: small number of alternations, Discrete Applied Mathematics, 2018, 236: 329-346.
- Short monadic second order sentences about sparse random graphs, SIAM J Disc Math, 2018, Vol. 32, No. 4, P. 2916-2940.
- On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels, Russian Mathematical Surveys, 2018, Vol. 73:4, P. 173-174.
- Logical laws for short existential monadic second order sentences about graphs, Journal of Mathematical Logic, 2020.
- Monadic second-order properties of very sparse random graphs, Annals of pure and applied logic, 2017, Vol. 168, 2087-2101.
- On the zero-one k-law extensions, European J. of Combinatorics, 60 (2017): 66-81.
- Quantifier Alternation in First-Order Formulas with Infinite Spectra, Problems of Information Transmission, 2017, 53(4): 391-403.
- On infinite spectra of first order properties of random graphs, Moscow Journal of Combinatorics and Number Theory, 2016, Vol. 6, No. 4, 73-102.
- Bounded quantifier depth spectra for random graphs, Discrete Mathematics, 2016, 339(6): 1651-1664.
- Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys, 2015, Vol. 70, No 1, 33-81.
- The Law of Large Numbers for the Number of Active Particles in an Epidemic Model, Theory Probab. Appl., 58(2), 297–313, 2014.
- Zero-One k-Law, Discrete Mathematics, 2012, 312: 1670-1688.
Refereed Conferences Publications
- Maximum induced subgraphs of the binomial random graph., Eurocomb 2019
- Supervised Nested PageRank., CIKM 2014
- Extension of the Zero-one k-law., Electronic Notes in Discrete Mathematics, 2013
- Fresh BrowseRank., SIGIR 2013