top of page

Research interests

  • Probabilistic and extremal combinatorics

  • Random graphs

  • Algorithms

  • Model theory and descriptive complexity

  • Logical limit laws

  • Extreme value theory

Papers

Preprints

  1. A. Cohen Antonir, I. Hosen, M. Zhukovskii, A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs, 2026

    ​

  2. A. Cohen Antonir, L. Lichev, M. Zhukovskii, Universality in random graphs via optimal linking systems: trees and beyond, 2026

    ​

  3. S. Vakhrushev, M. Zhukovskii, Spanning triangulations in random graphs, 2026

    ​

  4. B. Kolesnik, T. Makai, R. Nenadov, X. Pérez-Giménez, P. Pralat, M. Zhukovskii, The critical activation density in graph bootstrap percolation, 2026

     

  5. J. Rybicki, O. Verbitsky, M. Zhukovskii, What can be computed in average anonymous networks?​, 2026

    ​

  6. M. Benedikt, M. Zhukovskii, A logical approach to concentration, 2026
     

  7. M. Isaev, T. Makai, B. McKay, P. Pralat, J. Tan, M. Zhukovskii, Canonical labelling of random regular graphs, 2026
     

  8. M. Anastos, S. Diskin, L. Lichev, M. Zhukovskii, Diameter and mixing time of the giant component in the percolated hypercube, 2025
    ​​

  9. M. Akhmejanova, I. Vorobyev, M. Zhukovskii, Weak saturation numbers of large complete bipartite graphs, 2025
     

  10. ​A. Cohen Antonir, Y. Peled, A. Shapira, M. Tyomkyn, M. Zhukovskii, When does a tree activate the random graph?, 2025
    ​​

  11. M. Krivelevich, M. Zhukovskii, Non-isomorphic subgraphs in random graphs, 2025
     

  12. M. Zhukovskii, Sharp thresholds for spanning regular subgraphs, 2025
     

  13. J. Sylvester, V. Zamaraev, M. Zhukovskii, Functionality of random graphs, 2024
     

  14. S. Diskin, I. Hoshen, M. Zhukovskii, Tree tilings in random regular graphs, 2024
     

  15. O. Verbitsky, M. Zhukovskii, Canonical labeling of sparse random graphs, 2024
     

  16. F. Fuhlbrück, J. Köbler, O. Verbitsky, M. Zhukovskii, Gathering information about a graph by counting walks from a single vertex, 2024

    ​​​​

  17. É. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, M. Zhukovskii, Tight bounds on adjacency labels for monotone graph classes, 2023
     

  18. O. Verbitsky, M. Zhukovskii, Canonization of a random graph by two matrix-vector multiplications, 2023
     

  19. Y. Demidovich, Ya. Panichkin, M. Zhukovskii, Reconstruction of graph colourings, 2023

Representative journal publications

​

  1. B. Kolesnik, G. Zakharov, M. Zhukovskii, On the threshold for triangulations inside convex polygons, Random Structures & Algorithms (accepted)

    ​

  2. T. Hershko, M. Zhukovskii, First order distinguishability of sparse random graphs, Journal of Symbolic Logic (accepted)

    ​

  3. I. Benjamini, G. Zakharov, M. Zhukovskii, Majority dynamics on finite trees, Random Structures & Algorithms (accepted)

    ​

  4. M. Akhmejanova, V. Kozhevnikov, M. Zhukovskii, Maximum induced trees and forests of bounded degree in random graphs, Random Structures & Algorithms (accepted)

    ​

  5. S. Diskin, M. Krivelevich, I. Markbreit, M. Zhukovskii, A large hole in pseudo-random graphs, Combinatorics, Probability and Computing (accepted)

    ​

  6. Hoshen, W. Samotij, M. Zhukovskii, Stability of large cuts in random graphs, Transactions of the American Mathematical Society (accepted)

    ​

  7. M. Axenovich, L. Kießle, A. Sagdeev, M. Zhukovskii, Faces in girth-saturated graphs on surfaces, Discrete & Computational Geometry (accepted)
     

  8. D. Demin, M. Zhukovskii, First order complexity of finite random structures, Israel Journal of Mathematics (accepted)

    ​

  9. N. Alon, I. Benjamini, G. Zakharov, M. Zhukovskii, Sums along the edges of bounded degree graphs, Israel Journal of Mathematics (accepted)
     

  10. Yu. Malyshkin, M. Zhukovskii, Logical convergence laws via stochastic approximation and Markov processes, Electronic Journal of Probability 30 (2025) pp 1-23
     

  11. S. Diskin, I. Hoshen, D. Korándi, B. Sudakov, M. Zhukovskii, Saturation in random hypergraphs, Combinatorics, Probability and Computing published online (2025) pp 1-19
     

  12. O. Verbitsky, M. Zhukovskii, Canonization of a random circulant graph by counting walks, Combinatorics, Probability and Computing published online (2025) pp 1-29
     

  13. N. Terekhov, M. Zhukovskii, Weak saturation rank: a failure of linear algebraic approach to weak saturation, Combinatorica, 45 (2025) https://doi.org/10.1007/s00440-025-01380-x

    ​

  14. S. Diskin, I. Hoshen, M. Zhukovskii, A Jump of the Saturation Number in Random Graphs?, Random Structures & Algorithms, 66:4 (2025) e70009
     

  15. O. Pikhurko, O. Verbitsky, M. Zhukovskii, New bounds for the optimal density of covering single-insertion codes via the Turán density, IEEE Transactions on Information Theory (2025) doi: 10.1109/TIT.2025.3557393
     

  16. I. Benjamini, M. Zhukovskii,  A very sharp threshold for first order logic distinguishability of random graphs'', Discrete Analysis (2025) https://doi.org/10.19086/da.138190
     

  17. M. Isaev, B. D. McKay, A. Southwell, M. Zhukovskii, Sprinkling with random regular graphs, Electronic Journal of Probability, 30:17 (2025) pp 1–20
     

  18. N. Terekhov, M. Zhukovskii, Weak saturation in graphs: a combinatorial approach, Journal of Combinatorial Theory B, 172 (2025) pp 146–167
     

  19. I. Benjamini, Y. Dikstein, R. Gross, M. Zhukovskii, Randomly twisted hypercubes - between structure and randomness, Random Structures & Algorithms, 66:1 (2025) e21267
     

  20. M. Isaev, M. Zhukovskii, On the maximum number of common neighbours in dense random regular graphs, European Journal of Combinatorics, 126 (2025) 104106
     

  21. É. 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) pp 1578–1601
     

  22. S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii, On anti-stochastic properties of unlabeled graphs, SIAM Journal on Discrete Mathematics, 38:4 (2024) pp 3043–3078
     

  23. S. Vakhrushev, M. Zhukovskii, Maximum number of symmetric extensions in the random graph, SIAM Journal on Discrete Mathematics, 38:3 (2024) pp 2468–2488
     

  24. M. Krivelevich, M. Zhukovskii, Maximum chordal subgraphs of random graphs, Combinatorics, Probability and Computing, 33:5 (2024) pp 611–623

    ​

  25. M. Isaev, I. Rodionov, R. Zhang, M. Zhukovskii, Extremal independence in discrete random systems, Annales de l'Institut Henri Poincaré (B) 60:4 (2024) pp 2923–2944
     

  26. 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
     

  27. Y. Yarovikov, M. Zhukovskii, Spectrum of FO logic with quantifier depth 4 is finite, ACM Transactions on Computational Logic, 25:2 (2024) pp 9:1–9:24
     

  28. S. Diskin, I. Hoshen, M. Krivelevich, M. Zhukovskii, On vertex Ramsey graphs with forbidden subgraphs, Discrete Mathematics, 347:3 (2024) 113806
     

  29. 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
     

  30. Y. Demidovich, M. Zhukovskii, Tight asymptotics of clique-chromatic numbers of dense random graphs, Journal of Graph Theory, 103:3 (2023) pp 451–461
     

  31. O. Kalinichenko, M. Zhukovskii, Weak saturation stability, European Journal of Combinatorics 114 (2023) 103777
     

  32. Yu. Demidovich, A. Skorkin, M. Zhukovskii, Cycle saturation in random graphs, SIAM Journal on Discrete Mathematics, 37:3 (2023) pp 1359–1385
     

  33. V. Kozhevnikov, M. Zhukovskii, Large cycles in generalized Johnson graphs, Journal of Graph Theory (2023) pp 1-15, published online
     

  34. I. Rodionov, M. Zhukovskii, The distribution of the maximum number of common neighbors in the random graph, European Journal of Combinatorics, 107 (2023) 103602
     

  35. 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
     

  36. 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
     

  37. M. Isaev, A. Southwell, M. Zhukovskii, Distribution of tree parameters by martingale approach, Combinatorics, Probability and Computing, 31:5 (2022) pp 737–764

    ​

  38. J. Balogh, M. Zhukovskii, On the sizes of large subgraphs of the binomial random graph, Discrete Mathematics, 345:2 (2022) 112675
     

  39. D. Dmitriev, M. Zhukovskii, On a generalization of a Ramanujan conjecture for binomial random variables, Statistics & Probability Letters, 177 (2021) 109147
     

  40. D. Kamaldinov, A. Skorkin, M. Zhukovskii, Maximum sparse induced subgraphs of the binomial random graph with given number of edges, Discrete mathematics, 344:2 (2021) 112205
     

  41. M. Zhukovskii, Logical laws for short existential monadic second order sentences about graphs, Journal of Mathematical Logic, 2:2 (2020) 2050007
     

  42. A. Egorova, M. Zhukovskii, Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020) 103017
     

  43. 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) pp 505–514
     

  44. O. Verbitsky, M. Zhukovskii, Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, 20:2 (2019) pp 9:1–9:18
     

  45. A. Kupavskii, M. Zhukovskii, Short monadic second order sentences about sparse random graphs, SIAM Journal on Discrete Mathematics, 32:4 (2018) pp 2916–2940
     

  46. M. Zhukovskii, On the zero-one k-law extensions, European Journal of Combinatorics, 60 (2017) pp 66–81
     

  47. L. Ostrovsky, M. Zhukovskii, Monadic second-order properties of very sparse random graphs, Annals of pure and applied logic, 168 (2017) pp 2087–2101
     

  48. J. Spencer, M. Zhukovskii, Bounded quantifier depth spectra for random graphs, Discrete Mathematics, 339:6 (2016) pp 1651–1664
     

  49. M. Zhukovskii, A. Raigorodskii, Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys, 70:1 (2015) pp 33–81.

Refereed publications in conference proceedings

  1. J. Rybicki, O. Verbitsky, M. Zhukovskii, What can be computed in average anonymous networks?​, DISC 2026 (40th International Symposium on Distributed Computing) accepted

     

  2. M. Isaev, T. Makai, B. McKay, P. Pralat, J. Tan, M. Zhukovskii, Canonical labelling of random regular graphs, ICALP 2026 (The 52d EATCS International Colloquium on Automata, Languages, and Programming) Best paper award

    ​

  3. M. Krivelevich, M. Zhukovskii, Reconstructing random graphs from distance queries, ESA 2025 (The European Symposium on Algorithms) 30:1–30:17

    ​

  4. S. Diskin, I. Hoshen, M. Zhukovskii, Tiling Random Regular Graphs Efficiently, ICALP 2025 (The 51st EATCS International Colloquium on Automata, Languages, and Programming) 70:1–70:17

    ​

  5. O. Verbitsky, M. Zhukovskii, Canonical labeling of sparse random graphs, STACS 2025 (42nd International Symposium on Theoretical Aspects of Computer Science) 75:1-75:20

     

  6. T. Hershko, M. Zhukovskii, First order distinguishability of sparse random graphs, LICS 2024 (The 39th Annual ACM/IEEE Symposium on Logic in Computer Science) 44:1-44:14
     

  7. D. Demin, M. Zhukovskii, First order complexity of finite random structures, LICS 2024 (The 39th Annual ACM/IEEE Symposium on Logic in Computer Science) 31:1-31:14
     

  8. É. 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) 31:1-31:20
     

  9. 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
     

  10. É. 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

    ​

  11. 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
     

  12. 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

    ​

  13. O. Verbitsky, M. Zhukovskii, The Descriptive Complexity of Subgraph Isomorphism Without Numerics, CSR 2017: 308-322, Kazan, Russia, June, 2017

    ​

  14. 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

    ​

  15. 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
     

  16. 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.
     

  17. M. Zhukovskii, G. Gusev, P. Serdyukov, Supervised Nested PageRank, CIKM 2014: 1059-1068, Shanghai, China, 2014.
     

  18. 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.
     

  19. M. Zhukovskii, A. Khropov, G. Gusev, P. Serdyukov, Fresh BrowseRank, SIGIR 2013: 1029-1032, Dublin, Ireland, July, 2013.
     

  20. M. Zhukovskii, G. Gusev, P. Serdyukov, URL Redirection Accounting for Improving Link-Based Ranking Methods, ECIR 2013: 656-667, Moscow, Russia, March 2013.
     

  21. 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.
     

  22. 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.

Recent invited presentations and workshops

​

  1. Bulgarian Workshop on Probabilistic and Extremal Combinatorics (BWPEC 2026), Oryahovitsa, Bulgaria, 2026

    ​

  2. MATRIX Research program "Combinatorics of McKay and Wormald", Creswick, Australia, 2025 

    ​

  3. Random Networks Workshop, Sheffield, UK, 2025
     

  4. Liverpool Discrete Mathematics Colloquium, Liverpool, UK, 2024: invited tutorial
     

  5. The Midlands Graduate School Christmas Seminar, Sheffield, UK, 2024

    ​

  6. Probability meets Combinatorics at ISTA, Klosterneuburg, Austria, 2024

     

  7. Banff International Research Station "Bootstrap Percolation & Its Applications", Canada, 2024
     

  8. Probability in the North East, Sheffield, UK, 2023
     

  9. Dagstuhl Seminar 22061: Logic and Random Discrete Structures, Dagstuhl, Germany, 2022

Awards

  1. ICALP best paper 2026

     

  2. ESA best paper 2023
     

  3. Prize for Young Mathematicians of Russia 2021
     

  4. Robert Bartnik Visiting Fellowship, Monash University, 2019
     

  5. Fellowship of the Russian Academy of Sciences for young teachers and scientists, 2011
     

  6. Moscow State University Excellence Scholarship for undergraduate students, 2005 - 2009

bottom of page