Maksim Zhukovskii

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

SubmittedSelectedTalksConferences
SubmittedSelectedTalksConferences

Submitted papers

  1. I. Bogdanov, O. Grigoryan, M. Zhukovskii
    Covering three-tori with cubes, 2021, preprint
  2. S. Kiselev, A. Kupavskii, O. Verbitsky, M. Zhukovskii
    On anti-stochastic properties of unlabeled graphs, 2021, preprint
  3. Y. Demidovich, M. Zhukovskii
    Tight asymptotics of clique-chromatic numbers of dense random graphs, 2021, preprint
  4. M. Isaev, I. Rodionov, R. Zhang, M. Zhukovskii
    Extremal independence in discrete random systems, 2021, preprint
  5. V. Kozhevnikov, M. Zhukovskii
    Large cycles in generalized Johnson graphs, 2022, preprint

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,
    Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020).
  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
    The distribution of the maximum number of common neighbors in the random graph, European Journal of Combinatorics, to appear.
  13. Y. Malyshkin, M. Zhukovskii
    $\gamma$-variable first-order logic of uniform attachment random graphs, Discrete Mathematics, 345 (2022) 112802
  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
    Maximum sparse induced subgraphs of the binomial random graph with given number of edges, Discrete mathematics 34:2, 2021.
  17. Y. Malyshkin, M. Zhukovskii
    MSO zero-one law for recursive random trees, Statistics & Probability Letters, 173, 2021, 109061.
  18. M.E. Zhukovskii
    Logical laws for short existential monadic second order sentences about graphs, Journal of Mathematical Logic, Vol 2, No 2, 2020.
  19. A. Egorova, M. Zhukovskii,
    Existential monadic second order convergence law fails on sparse random graphs, European Journal of Combinatorics, 83 (2020).
  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,
    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.
  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,
    The Law of Large Numbers for the Number of Active Particles in an Epidemic Model, Theory Probab. Appl., 58(2), 297–313, 2014.
  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,
    Maximum induced subgraphs of the binomial random graph, Eurocomb 2019
  5. O. Verbitsky, M. Zhukovskii,
    The Descriptive Complexity of Subgraph Isomorphism Without Numerics, CSR 2017
  6. O. Verbitsky, M. Zhukovskii,
    On the First-Order Complexity of Induced Subgraph Isomorphism, CSL 2017
  7. Lev Bogolubsky, Pavel Dvurechensky, Alexander Gasnikov, Gleb Gusev, Yurii Nesterov, Andrei Raigorodskii, Aleksey Tikhonov, Maksim Zhukovskii,
    Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods, NIPS 2016
  8. Maxim Zhukovskiy, Tsimafei Khatkevich, Gleb Gusev, Pavel Serdyukov,
    An Optimization Framework for Propagation of Query-Document Features by Query Similarity Functions, CIKM 2015
  9. Maxim Zhukovskiy, Gleb Gusev, Pavel Serdyukov,
    Supervised Nested PageRank, CIKM 2014
  10. M.E. Zhukovskii,
    Extension of the Zero-one k-law, Electronic Notes in Discrete Mathematics, 2013
  11. Maksim Zhukovskii, Gleb Gusev, Pavel Serdyukov,
    URL Redirection Accounting for Improving Link-Based Ranking Methods, ECIR 2013
  12. Maxim Zhukovskiy, Andrei Khropov, Gleb Gusev, Pavel Serdyukov,
    Introducing search behavior into browsing based models of page's importance, WWW 2013
  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,
    Empirical validation of the Buckley-Osthus model for the web host graph: degree and edge distributions, CIKM 2012
  15. Maxim Zhukovskiy, Dmitry Vinogradov, Gleb Gusev, Pavel Serdyukov, Andrei Raigorodskii,
    Recency-sensitive model of web page authority, CIKM 2012

Prize for Young Mathematicians of Russia

August 13, 2021
Maksim Zhukovskii became one of the winners in the nomination "Young Scientists" of the first Prize for Young Mathematicians of Russia.

Learn more