Research interests
-
Probabilistic and extremal combinatorics
-
Random graphs
-
Algorithms
-
Model theory and descriptive complexity
-
Logical limit laws
-
Extreme value theory
Papers
Preprints
-
O. Verbitsky, M. Zhukovskii, Canonical labeling of sparse random graphs, 2024.
-
O. Pikhurko, O. Verbitsky, M. Zhukovskii, New bounds for the optimal density of covering single-insertion codes via the Turán density, 2024
-
F. Fuhlbrück, J. Köbler, O. Verbitsky, M. Zhukovskii, Gathering Information about a Graph by Counting Walks from a Single Vertex, 2024
-
M. Akhmejanova, V. Kozhevnikov, M. Zhukovskii, Maximum induced trees and forests of bounded degree in random graphs, 2024
-
N. Terekhov, M. Zhukovskii, Weak saturation rank: a failure of linear algebraic approach to weak saturation, 2024
-
T. Hershko, M. Zhukovskii, First order distinguishability of sparse random graphs, 2024
-
S. Diskin, I. Hoshen, D. Korándi, B. Sudakov, M. Zhukovskii, Saturation in random hypergraphs, 2024
-
M. Krivelevich, M. Zhukovskii, Reconstructing random graphs from distance queries, 2024
-
I. Hoshen, W. Samotij, M. Zhukovskii, Stability of large cuts in random graphs, 2024
-
D. Demin, M. Zhukovskii, First order complexity of finite random structures, 2024
-
É. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, M. Zhukovskii, Tight bounds on adjacency labels for monotone graph classes, 2023
-
O. Verbitsky, M. Zhukovskii, Canonization of a random graph by two matrix-vector multiplications, 2023
-
O. Verbitsky, M. Zhukovskii, Canonization of a random circulant graph by counting walks, 2023
-
M. Isaev, B. D. McKay, A. Southwell, M. Zhukovskii, Sprinkling with random regular graphs, 2023
-
Y. Demidovich, Ya. Panichkin, M. Zhukovskii, Reconstruction of colours, 2023
-
N. Terekhov, M. Zhukovskii, Weak saturation in graphs: a combinatorial approach, 2023
-
M. Miralaei, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii, Saturation numbers of bipartite graphs in random graphs, 2023
-
S. Diskin, I. Hoshen, M. Zhukovskii, A Jump of the Saturation Number in Random Graphs?, 2023
-
Yu. Malyshkin, M. Zhukovskii, Logical convergence laws via stochastic approximation and Markov processes, 2022
-
I. Benjamini, M. Zhukovskii, A very sharp threshold for first order logic distinguishability of random graphs'', 2022
-
I. Bogdanov, O. Grigoryan, M. Zhukovskii, Covering three-tori with cubes, 2021
Selected journal publications
-
I. Benjamini, Y. Dikstein, R. Gross, M. Zhukovskii, Randomly twisted hypercubes - between structure and randomness, Random Structures & Algorithms, 66:1 (2025) e21267
-
É. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, M. Zhukovskii, Small but unwieldy: A Lower Bound on Adjacency Labels for Small Classes, SIAM Journal on Computing, 53:5 (2024) 1578-1601
-
M. Isaev, M. Zhukovskii, On the maximum number of common neighbours in dense random regular graphs, European Journal of Combinatorics (to appear)
-
S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii, On anti-stochastic properties of unlabeled graphs, SIAM Journal on Discrete Mathematics (to appear)
-
S. Vakhrushev, M. Zhukovskii, Maximum number of symmetric extensions in the random graph, SIAM Journal on Discrete Mathematics, 38:3 (2024) 2468-2488
-
M. Krivelevich, M. Zhukovskii, Maximum chordal subgraphs of random graphs, Combinatorics, Probability and Computing, 33:5 (2024) 611-623
-
M. Isaev, I. Rodionov, R. Zhang, M. Zhukovskii, Extremal independence in discrete random systems, Annales de l'Institut Henri Poincaré (B) 60:4 (2024) 2923–2944
-
M.R. Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii, Threshold for stability of weak saturation, Journal of Graph Theory, 106:3 (2024) pp 474-495
-
Y. Yarovikov, M. Zhukovskii, Spectrum of FO logic with quantifier depth 4 is finite, ACM Transactions on Computational Logic (2024) published online: https://doi.org/10.1145/3641547
-
S. Diskin, I. Hoshen, M. Krivelevich, M. Zhukovskii, On vertex Ramsey graphs with forbidden subgraphs, Discrete Mathematics, 347:3 (2024) 113806
-
I. Benjamini, H. Helman Tov, M. Zhukovskii, Global information from local observations of the noisy voter model, Annals of Probability, 51:5 (2023) pp 1963-1992
-
Y. Demidovich, M. Zhukovskii, Tight asymptotics of clique-chromatic numbers of dense random graphs, Journal of Graph Theory, 103:3 (2023) pp 451-461
-
S. Demyanov, M. Zhukovskii, Tight concentration of star saturation number in random graphs, Discrete Mathematics, 346:10 (2023) 113572
-
O. Kalinichenko, M. Zhukovskii, Weak saturation stability, European Journal of Combinatorics 114 (2023) 103777
-
Yu. Demidovich, A. Skorkin, M. Zhukovskii, Cycle saturation in random graphs, SIAM Journal on Discrete Mathematics, 37:3 (2023) pp 1359-1385
-
V. Kozhevnikov, M. Zhukovskii, Large cycles in generalized Johnson graphs, Journal of Graph Theory (2023) pp 1-15, published online
-
I. Rodionov, M. Zhukovskii, The distribution of the maximum number of common neighbors in the random graph, European Journal of Combinatorics, 107 (2023) 103602
-
M. Akhmejanova, M. Zhukovskii, EMSO(FO^2) 0-1 law fails for all dense random graphs, SIAM Journal on Discrete Mathematics, 36:3 (2022) 10.1137/21M1429655
-
M. Podder, M. Zhukovskii, Zero-one laws for existential first order sentences of bounded quantifier depth, ACM Transactions on Computational Logic, 23:2 (2022) Article 12: 1-27
-
M. Isaev, A. Southwell, M. Zhukovskii, Distribution of tree parameters by martingale approach, Combinatorics, Probability and Computing, 31:5 (2022) pp. 737-764
-
Y. Malyshkin, M. Zhukovskii, γ-variable first-order logic of uniform attachment random graphs, Discrete Mathematics, 345 (2022) 112802
-
V. Kozhevnikov, A. Raigorodskii, M. Zhukovskii, Large cycles in random generalized Johnson graphs, Discrete Mathematics, 345:3 (2022) 112721
-
J. Balogh, M. Zhukovskii, On the sizes of large subgraphs of the binomial random graph, Discrete Mathematics, 345:2 (2022) 112675
-
D. Dmitriev, M. Zhukovskii, On a generalization of a Ramanujan conjecture for binomial random variables, Statistics & Probability Letters, 177 (2021), 109147
-
M. Krivoshapko, M. Zhukovskii, Maximum induced forests in random graphs, Discrete Applied Mathematics, 305 (2021), 211-213
-
D. Kamaldinov, A. Skorkin, M. Zhukovskii, Maximum sparse induced subgraphs of the binomial random graph with given number of edges, Discrete mathematics 34:2 (2021)
-
Y. Malyshkin, M. Zhukovskii, MSO zero-one law for recursive random trees, Statistics & Probability Letters, 173 (2021), 109061
-
M. Zhukovskii, Logical laws for short existential monadic second order sentences about graphs, Journal of Mathematical Logic, 2:2 (2020)
-
A. Egorova, M. Zhukovskii, Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020) 103017
-
A.S. Razafimahatratra, M. Zhukovskii, Zero-one laws for $k$-variable first-order logic of sparse random graphs, Discrete Applied Mathematics 276 (2020) 121-128
-
S. Popova, M. Zhukovskii, 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
-
O. Verbitsky, M. Zhukovskii, On the First-Order Complexity of Induced Subgraph Isomorphism, Logical Methods in Computer Science, 15:1 (2019) 25:1-25:24
-
O. Verbitsky, M. Zhukovskii, Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, 20:2 (2019)
-
A. Matushkin, M. Zhukovskii, First order sentences about random graphs: small number of alternations, Discrete Applied Mathematics, 236 (2018) 329-346
-
D. Dmitriev, M. Zhukovskii, On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels, Russian Mathematical Surveys, 73:4 (2018) 173-174
-
A. Kupavskii, M. Zhukovskii, Short monadic second order sentences about sparse random graphs, SIAM Journal on Discrete Mathematics, 32:4 (2018) 2916-2940
-
M. Zhukovskii, On the zero-one k-law extensions, European Journal of Combinatorics, 60 (2017): 66-81
-
L. Ostrovsky, M. Zhukovskii, Monadic second-order properties of very sparse random graphs, Annals of pure and applied logic, 168 (2017) 2087-2101
-
M. Zhukovskii, Quantifier Alternation in First-Order Formulas with Infinite Spectra, Problems of Information Transmission, 53:4 (2017) 391-403
-
J. Spencer, M. Zhukovskii, Bounded quantifier depth spectra for random graphs, Discrete Mathematics, 339:6 (2016): 1651-1664
-
M. Zhukovskii, A. Raigorodskii, Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys, 70:1 (2015) 33-81
-
M. Zhukovskii, The Law of Large Numbers for the Number of Active Particles in an Epidemic Model, Theory of Probability & Its Applications. 58:2 (2014) 297-313
-
M. Zhukovskii, Zero-One k-Law, Discrete Mathematics, 312 (2012) 1670-1688
Refereed publications in conference proceedings
-
T. Hershko, M. Zhukovskii, First order distinguishability of sparse random graphs, LICS 2024 (The 39th Annual ACM/IEEE Symposium on Logic in Computer Science) accepted
-
D. Demin, M. Zhukovskii, First order complexity of finite random structures, LICS 2024 (The 39th Annual ACM/IEEE Symposium on Logic in Computer Science) accepted
-
É. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, M. Zhukovskii, Tight bounds on adjacency labels for monotone graph classes, ICALP 2024 (The 51st EATCS International Colloquium on Automata, Languages, and Programming) accepted
-
O. Verbitsky, M. Zhukovskii, Canonization of a random circulant graph by counting walks, WALCOM 2024 (The 18th International Conference and Workshops on Algorithms and Computation) 319-334
-
É. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, M. Zhukovskii, Small but unwieldy: a lower bound on adjacency labels for small classes, SODA 2024 (ACM-SIAM Symposium on Discrete Algorithms) 1147-1165
-
O. Verbitsky, M. Zhukovskii. Canonization of a random graph by two vector-matrix multiplications, ESA 2023 (The European Symposium on Algorithms), Amsterdam, Netherlands, September 2023. Best paper award
-
S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii. On anti-stochastic properties of unlabeled graphs, WG 2022 (48th international Workshop on graph-theoretics concepts in Computer Science), Tübingen, Germany, June 2022
-
I. Bogdanov, O. Grigoryan, M. Zhukovskii, Covering three-tori with cubes, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, 811-816
-
Yu. Demidovich, M. Zhukovskii, Cycle saturation in random graphs, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, 772-777
-
J. Balogh, M. Zhukovskii, Maximum induced subgraphs of the binomial random graph, Abstracts to the talks at Eurocomb 2019, Bratislava, Slovakia, August, 2019
-
O. Verbitsky, M. Zhukovskii, The Descriptive Complexity of Subgraph Isomorphism Without Numerics, CSR 2017: 308-322, Kazan, Russia, June, 2017
-
M. Zhukovskii, Monotone convergence of the number of P_3 in G(n,p), SPA 2017 (39th Conference on Stochastic Processes and Their Applications): 128-129, Moscow, Russia, July, 2017
-
O. Verbitsky, M. Zhukovskii, On the First-Order Complexity of Induced Subgraph Isomorphism, CSL 2017 (26th EACSL Annual Conference on Computer Science Logic), 40:1-40:16, Stockholm, Sweden, August 2017
-
M. Zhukovskii, First order and monadic second order logic of very sparse random graphs, Abstracts to the talks at the international conference BGW 2016, Bordeaux, France, November, 2016
-
L. Bogolubsky, P. Dvurechensky, A. Gasnikov, G. Gusev, Yu. Nesterov, A. Raigorodskii, A. Tikhonov, M. Zhukovskii, Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods, NeurIPS 2016: 4907-4915, Spain, Barcelona, 2016
-
M. Zhukovskii, T. Khatkevich, G. Gusev, P. Serdyukov, An Optimization Framework for Propagation of Query-Document Features by Query Similarity Functions, CIKM 2015: 981-990, Melbourne, Australia, 2015.
-
M. Zhukovskii, G. Gusev, P. Serdyukov, Supervised Nested PageRank, CIKM 2014: 1059-1068, Shanghai, China, 2014.
-
M. Zhukovskii, A, Khropov, G. Gusev, P. Serdyukov, Introducing search behavior into browsing based models of page's importance, WWW 2013: 129-130, Rio de Janeiro, Brazil, 13th-17th May, 2013.
-
M. Zhukovskii, A. Khropov, G. Gusev, P. Serdyukov, Fresh BrowseRank, SIGIR 2013: 1029-1032, Dublin, Ireland, July, 2013.
-
M. Zhukovskii, G. Gusev, P. Serdyukov, URL Redirection Accounting for Improving Link-Based Ranking Methods, ECIR 2013: 656-667, Moscow, Russia, March 2013.
-
M. Zhukovskii, D. Vinogradov, G. Gusev, P. Serdyukov, A. Raigorodskii, Recency-sensitive model of web page authority, CIKM 2012: 2627-2630, Maui, Hawaii, USA, October-November 2012.
-
M. Zhukovskii, D, Vinogradov, Yu. Pritykin, L. Ostroumova, E. Grechnikov, G. Gusev, P. Serdyukov, A. Raigorodskii, Empirical validation of the Buckley-Osthus model for the web host graph: degree and edge distributions, CIKM 2012: 1577-1581, Maui, Hawaii, USA, 2012.
-
M. Zhukovskii, On the Weak Zero-One Laws for the Random Distance Graphs, Abstracts of the talks at the international conference Eurocomb 2009, Bordeaux, France, September, 2009.
Recent invited presentations
-
Probability meets Combinatorics at ISTA, Klosterneuburg, Austria, 2024
-
Banff International Research Station "Bootstrap Percolation & Its Applications", Canada, 2024
-
Probability in the North East, Sheffield, UK, 2023
-
Dagstuhl Seminar 22061: Logic and Random Discrete Structures, Dagstuhl, Germany, 2022
-
International conference Net 2019, Moscow, Russia, 2019
-
2nd Russian-Hungarian Combinatorial Workshop, Budapest, Hungary, 2018
Awards
-
ESA best paper 2023
-
Robert Bartnik Visiting Fellowship, Monash University, 2019
-
Fellowship of the Russian Academy of Sciences for young teachers and scientists, 2011
-
Moscow State University Excellence Scholarship for undergraduate students, 2005 - 2009