Maksim Zhukovskii

Photo by zoom

Maksim
Zhukovskii

MIPT, Moscow
Research interests:

Random graphs, extremal combinatorics, descriptive complexity, model theory

zhukmax@gmail.com

Current position

Researcher since Jan 2020, Moscow Institute of Physics and Technology, Laboratory of Combinatorial and Geometric structures

Positions held

Associate Professor Sep 2014 - Jun 2022, Moscow Institute of Physics and Technology, Department of Discrete Mathematics
Reseacher May 2016 - Dec 2020, Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Networks Applications
Researcher May 2011 - May 2017, Yandex Research
Junior Researcher May 2010 - Oct 2010, Sep 2012 - Oct 2014, Department of Math Statistics and Random Processes, Lomonosov Moscow State University, Mechanics and Mathematics Faculty
Assistant Prof, Sep 2010 - Aug 2014, Moscow Institute of Physics and Technology, Department of Discrete Mathematics

Visiting positions

Monash University, Australia, Melbourne, Nov - Dec 2019
Weizmann Institute of Science, Israel, Rehovot, Apr - Jul 2022
Tel Aviv University, Israel, Tel Aviv, Aug - Sep 2022

Lab videos

Publications

Submitted papers

  1. I. Bogdanov, O. Grigoryan, M. Zhukovskii
  2. S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii
  3. Y. Demidovich, M. Zhukovskii
  4. M. Isaev, I. Rodionov, R. Zhang, M. Zhukovskii
  5. V. Kozhevnikov, M. Zhukovskii

Selected journal publications

  1. O. Kalinichenko, M. Zhukovskii
    Weak saturation stability, European Journal of Combinatorics, to appear.
  2. Yu. Demidovich, A. Skorkin, M. Zhukovskii
    Cycle saturation in random graphs, SIAM Journal on Discrete Mathematics, to appear.
  3. Y. Yarovikov, M. Zhukovskii
    Spectrum of FO logic with quantifier depth 4 is finite, ACM Transactions on Computational Logic, to appear.
  4. M. Akhmejanova, M. Zhukovskii
    EMSO(FO$^2$) 0-1 law fails for all dense random graphs, SIAM Journal on Discrete Mathematics, to appear.
  5. M. Podder, M. Zhukovskii
    Zero-one laws for existential first order sentences of bounded quantifier depth, ACM Transactions on Computational Logic (2022) Vol 23 Issue 2, No:12 pp:1-27.
  6. M. Isaev, A. Southwell, M. Zhukovskii
    Distribution of tree parameters by martingale approach, Combinatorics, Probability and Computing (2022) pp. 1-28.
  7. A. Egorova, M. Zhukovskii,
  8. M. Podder, M. Zhukovskii
    Zero-one laws for existential first order sentences of bounded quantifier depth, ACM Transactions on Computational Logic, to appear.
  9. V.S. Kozhevnikov, A.M. Raigorodskii, M.E. Zhukovskii
    Large cycles in random generalized Johnson graphs, Discrete Mathematics, 345:3 (2022) 112721.
  10. M.R. Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii
    Threshold for weak saturation stability, Journal of Graph Theory, to appear.
  11. Jozsef Balogh, Maksim Zhukovskii
    On the sizes of large subgraphs of the binomial random graph, Discrete Mathematics, 345:2 (2022) 112675.
  12. I.V. Rodionov, M.E. Zhukovskii
  13. Y. Malyshkin, M. Zhukovskii
  14. D. Dmitriev, M. Zhukovskii
    On a generalization of a Ramanujan conjecture for binomial random variables, Statistics & Probability Letters, 177, 2021, 109147.
  15. M. Krivoshapko, M. Zhukovskii
    Maximum induced forests in random graphs, Discrete Applied Mathematics, 305, 2021, pp 211-213.
  16. D. Kamaldinov, A. Skorkin, M. Zhukovskii
  17. Y. Malyshkin, M. Zhukovskii
    MSO zero-one law for recursive random trees, Statistics & Probability Letters, 173, 2021, 109061.
  18. M.E. Zhukovskii
  19. A. Egorova, M. Zhukovskii,
  20. R. Zhang, M.E. Zhukovskii, M.I. Isaev, I.V. Rodionov,
    Stochastic extreme value theory for triangular arrays of dependent random variables, Russian Mathematical Surveys 75:5, 2020, 968-970.
  21. O. Grigoryan, M. Makarov, M. Zhukovskii,
    First-order definitions of subgraph isomorphism through the adjacency and order relations, Moscow Journal of Combinatorics and Number Theory, 9:3, 2020, 293-302.
  22. 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.
  23. S.N. Popova, M.E. Zhukovskii,
  24. O. Verbitsky, M. Zhukovskii,
    On the First-Order Complexity of Induced Subgraph Isomorphism, Logical Methods in Computer Science, Volume 15, Issue 1, 2019, 25:1-25:24.
  25. O. Verbitsky, M. Zhukovskii,
    Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism, ACM Transactions on Computational Logic, Volume 20, Issue 2, 2019.
  26. A.D. Matushkin, M.E. Zhukovskii,
    First order sentences about random graphs: small number of alternations, Discrete Applied Mathematics, 2018, 236: 329-346.
  27. D.I. Dmitriev, M.E. Zhukovskii,
    On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels, Russian Mathematical Surveys, 2018, Vol. 73:4, P. 173-174.
  28. A. Kupavskii, M. Zhukovskii,
    Short monadic second order sentences about sparse random graphs, SIAM J Disc Math, 2018, Vol. 32, No. 4, P. 2916-2940.
  29. M.E. Zhukovskii,
    On the zero-one k-law extensions, European J. of Combinatorics, 60 (2017): 66-81.
  30. L.B. Ostrovsky, M.E. Zhukovskii,
    Monadic second-order properties of very sparse random graphs, Annals of pure and applied logic, 2017, Vol. 168, 2087-2101.
  31. J.H. Spencer, M.E. Zhukovskii,
    Bounded quantifier depth spectra for random graphs, Discrete Mathematics, 2016, 339(6): 1651-1664.
  32. M.E. Zhukovskii,
    On infinite spectra of first order properties of random graphs, Moscow Journal of Combinatorics and Number Theory, 2016, Vol. 6, No. 4, 73-102.
  33. M.E. Zhukovskii, A.M. Raigorodskii,
    Random graphs: models and asymptotic characteristics, Russian Mathematical Surveys, 2015, Vol. 70, No 1, 33-81.
  34. M.E. Zhukovskii,
    The spectra of first-order formulae having low quantifier rank, Russian Mathematical Surveys, 2015, Vol. 70, No. 6, 1176-1178.
  35. M.E. Zhukovskii,
  36. M.E. Zhukovskii,
    Zero-One k-Law, Discrete Mathematics, 2012, 312: 1670-1688.
  37. M.E. Zhukovskii,
    On a sequence of random distance graphs subject to the zero-one law, Problems of Information Transmission, 2011, 47(3): 251-268.

Invited plenary presentations

  1. Dagstuhl Seminar 22061: Logic and Random Discrete Structures, Dagstuhl, Germany, 2022
  2. International conference IPMCCC 2019, Tehran, Iran 2019
  3. International conference Net 2019, Moscow, Russia 2019
  4. 2nd Russian-Hungarian Combinatorial Workshop, Budapest, Hungary, 2018
  5. International conference GraphHPC 2017, Moscow, Russia, 2017
  6. International conference PMDM 2016, Petrozavodsk, Russia, 2016
  7. International conference Net 2016, Nizhniy Novgorod, Russia, 2016
  8. Workshop on Logic and Random Graphs, Leiden, the Netherlands, 2015
  9. I. Bogdanov, O. Grigoryan, M. Zhukovskii,
    Covering three-tori with cubes, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 811-816.
  10. Yu. Demidovich, M. Zhukovskii,
    Cycle saturation in random graphs, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 772-777.

Refereed Conferences Publications

  1. S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii,
    On anti-stochastic properties of unlabeled graphs, 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022)
  2. I. Bogdanov, O. Grigoryan, M. Zhukovskii,
    Covering three-tori with cubes, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 811--816
  3. Yu. Demidovich, M. Zhukovskii,
    Cycle saturation in random graphs, Trends in Mathematics Research Perspectives CRM Barcelona Vol. 14, Extended Abstracts EuroComb 2021, pp. 772--777
  4. J. Balogh, M.E. Zhukovskii,
  5. O. Verbitsky, M. Zhukovskii,
  6. O. Verbitsky, M. Zhukovskii,
  7. Lev Bogolubsky, Pavel Dvurechensky, Alexander Gasnikov, Gleb Gusev, Yurii Nesterov, Andrei Raigorodskii, Aleksey Tikhonov, Maksim Zhukovskii,
  8. Maxim Zhukovskiy, Tsimafei Khatkevich, Gleb Gusev, Pavel Serdyukov,
  9. Maxim Zhukovskiy, Gleb Gusev, Pavel Serdyukov,
  10. M.E. Zhukovskii,
    Extension of the Zero-one k-law, Electronic Notes in Discrete Mathematics, 2013
  11. Maksim Zhukovskii, Gleb Gusev, Pavel Serdyukov,
  12. Maxim Zhukovskiy, Andrei Khropov, Gleb Gusev, Pavel Serdyukov,
  13. Maxim Zhukovskiy, Andrei Khropov, Gleb Gusev, and Pavel Serdyukov,
    Fresh BrowseRank, SIGIR 2013
  14. Maxim Zhukovskiy, Dmitry Vinogradov, Yuri Pritykin, Liudmila Ostroumova, Evgeny Grechnikov, Gleb Gusev, Pavel Serdyukov, Andrei Raigorodskii,
  15. Maxim Zhukovskiy, Dmitry Vinogradov, Gleb Gusev, Pavel Serdyukov, Andrei Raigorodskii,