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. O. Verbitsky, M. Zhukovskii, Canonical labeling of sparse random graphs, 2024.
     

  2. O. Pikhurko, O. Verbitsky, M. Zhukovskii, New bounds for the optimal density of covering single-insertion codes via the Turán density, 2024
     

  3. F. Fuhlbrück, J. Köbler, O. Verbitsky, M. Zhukovskii, Gathering Information about a Graph by Counting Walks from a Single Vertex, 2024

  4. M. Akhmejanova, V. Kozhevnikov, M. Zhukovskii, Maximum induced trees and forests of bounded degree in random graphs, 2024
     

  5. N. Terekhov, M. Zhukovskii, Weak saturation rank: a failure of linear algebraic approach to weak saturation, 2024
     

  6. T. Hershko, M. Zhukovskii, First order distinguishability of sparse random graphs, 2024
     

  7. S. Diskin, I. Hoshen, D. Korándi, B. Sudakov, M. Zhukovskii, Saturation in random hypergraphs, 2024
     

  8. M. Krivelevich, M. Zhukovskii, Reconstructing random graphs from distance queries, 2024
     

  9. I. Hoshen, W. Samotij, M. ZhukovskiiStability of large cuts in random graphs, 2024
     

  10. D. Demin, M. Zhukovskii, First order complexity of finite random structures, 2024
     

  11. M. Isaev, M. Zhukovskii, On the maximum number of common neighbours in dense random regular graphs, 2023
     

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

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

  14. O. Verbitsky, M. Zhukovskii, Canonization of a random circulant graph by counting walks, 2023
     

  15. M. Isaev, B. D. McKay, A. Southwell, M. Zhukovskii, Sprinkling with random regular graphs, 2023
     

  16. Y. Demidovich, Ya. Panichkin, M. Zhukovskii, Reconstruction of colours, 2023
     

  17. N. Terekhov, M. Zhukovskii, Weak saturation in graphs: a combinatorial approach, 2023
     

  18. M. Miralaei, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii, Saturation numbers of bipartite graphs in random graphs, 2023
     

  19. S. Diskin, I. Hoshen, M. Zhukovskii, A Jump of the Saturation Number in Random Graphs?, 2023
     

  20. Yu. Malyshkin, M. Zhukovskii, Logical convergence laws via stochastic approximation and Markov processes, 2022
     

  21. I. Benjamini, M. Zhukovskii,  A very sharp threshold for first order logic distinguishability of random graphs'', 2022
     

  22. I. Bogdanov, O. Grigoryan, M. Zhukovskii, Covering three-tori with cubes, 2021

Selected journal publications

  1. I. Benjamini, Y. Dikstein, R. Gross, M. Zhukovskii, Randomly twisted hypercubes - between structure and randomness, Random Structures & Algorithms (to appear)
     

  2. É. 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 (to appear)
     

  3. S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii, On anti-stochastic properties of unlabeled graphs, SIAM Journal on Discrete Mathematics (to appear)
     

  4. S. Vakhrushev, M. Zhukovskii, Maximum number of symmetric extensions in the random graph, SIAM Journal on Discrete Mathematics (to appear)
     

  5. M. Krivelevich, M. Zhukovskii, Maximum chordal subgraphs of random graphs, Combinatorics, Probability and Computing (2024) published online: https://doi.org/10.1017/S0963548324000154
     

  6. M. Isaev, I. Rodionov, R. Zhang, M. Zhukovskii, Extremal independence in discrete random systems, Annales de l'Institut Henri Poincaré (B) (to appear)
     

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

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

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

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

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

  12. S. Demyanov, M. Zhukovskii, Tight concentration of star saturation number in random graphs, Discrete Mathematics, 346:10 (2023) 113572
     

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

  14. Yu. Demidovich, A. Skorkin, M. Zhukovskii, Cycle saturation in random graphsSIAM Journal on Discrete Mathematics, 37:3 (2023) pp 1359-1385
     

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

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

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

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

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

  20. Y. Malyshkin, M. Zhukovskii, γ-variable first-order logic of uniform attachment random graphs, Discrete Mathematics, 345 (2022) 112802
     

  21. V. Kozhevnikov, A. Raigorodskii, M. Zhukovskii, Large cycles in random generalized Johnson graphs, Discrete Mathematics, 345:3 (2022) 112721
     

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

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

  24. M. Krivoshapko, M. Zhukovskii, Maximum induced forests in random graphs, Discrete Applied Mathematics, 305 (2021), 211-213
     

  25. 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)
     

  26. Y. Malyshkin, M. Zhukovskii, MSO zero-one law for recursive random trees, Statistics & Probability Letters, 173 (2021), 109061
     

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

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

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

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

  31. O. Verbitsky, M. Zhukovskii, On the First-Order Complexity of Induced Subgraph IsomorphismLogical Methods in Computer Science, 15:1 (2019) 25:1-25:24
     

  32. O. Verbitsky, M. Zhukovskii, Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, 20:2 (2019)
     

  33. O. Verbitsky, M. Zhukovskii, The Descriptive Complexity of Subgraph Isomorphism without Numerics, Theory of Computing Systems, 63:4 (2019) 902-921
     

  34. A. Matushkin, M. Zhukovskii, First order sentences about random graphs: small number of alternations, Discrete Applied Mathematics, 236 (2018) 329-346
     

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

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

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

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

  39. M. Zhukovskii, Quantifier Alternation in First-Order Formulas with Infinite Spectra, Problems of Information Transmission, 53:4 (2017) 391-403
     

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

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

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

  43. M. Zhukovskii, Zero-One k-Law, Discrete Mathematics, 312 (2012) 1670-1688
     

  44. M. Zhukovskii, A weak zero-one law for sequences of random distance graphs, Sbornik: Mathematics, 203:7 (2012) 1012-1044.

Refereed publications in conference proceedings

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

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

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

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

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

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

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

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

  9. Yu. Demidovich, M. Zhukovskii, Cycle saturation in random graphs, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, 772-777
     

  10. J. Balogh, M. Zhukovskii,  Maximum induced subgraphs of the binomial random graph, Abstracts to the talks at Eurocomb 2019, Bratislava, Slovakia, August, 2019
     

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

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

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

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

  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.
     

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

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

     

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

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

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

  5. International conference Net 2019, Moscow, Russia, 2019
     

  6. 2nd Russian-Hungarian Combinatorial Workshop, Budapest, Hungary, 2018

Awards

  1. ESA best paper 2023
     

  2. Prize for Young Mathematicians of Russia 2021
     

  3. Robert Bartnik Visiting Fellowship, Monash University, 2019
     

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

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

bottom of page