Dr Maksim Zhukovskii
School of Computer Science
Senior Lecturer in Verification
M.Zhukovskii@sheffield.ac.uk
Regent Court (DCS)
Full contact details
Dr Maksim Zhukovskii
School of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
School of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
- Profile
-
Maksim is a mathematician working mainly in combinatorics, probability, model theory and related areas. Before joining the Department of Computer Science, in December 2022, Maksim held research visiting positions in Tel Aviv University and Weizmann Institute of Science, Israel. Before that, he was Associate Professor at the department of Discrete Mathematics at Moscow Institute of Physics and Technology. Maksim received his PhD (2012) in mathematics from Moscow State University, Russia.
- Publications
-
Journal articles
- Randomly Twisted Hypercubes: Between Structure and Randomness. Random Structures & Algorithms, 66(1).
- Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. SIAM Journal on Computing, 53(5), 1578-1601.
- On vertex Ramsey graphs with forbidden subgraphs. Discrete Mathematics, 347(3), 113806-113806.
- Weak saturation stability. European Journal of Combinatorics, 114, 103777-103777.
- Tight concentration of star saturation number in random graphs. Discrete Mathematics, 346(10), 113572-113572.
- Global information from local observations of the noisy voter model on a graph. The Annals of Probability, 51(5).
- Cycle Saturation in Random Graphs. SIAM Journal on Discrete Mathematics, 37(3), 1359-1385.
- The distribution of the maximum number of common neighbors in the random graph. European Journal of Combinatorics, 107, 103602-103602.
- EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs. SIAM Journal on Discrete Mathematics, 36(3), 1788-1799.
- γ-variable first-order logic of uniform attachment random graphs. Discrete Mathematics, 345(5), 112802-112802.
- Distribution of tree parameters by martingale approach. Combinatorics, Probability and Computing, 31(5), 737-764.
- Large cycles in random generalized Johnson graphs. Discrete Mathematics, 345(3), 112721-112721.
- On the sizes of large subgraphs of the binomial random graph. Discrete Mathematics, 345(2), 112675-112675.
- Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth. ACM Transactions on Computational Logic, 23(2), 1-27.
- Maximum induced forests in random graphs. Discrete Applied Mathematics, 305, 211-213.
- On monotonicity of Ramanujan function for binomial random variables. Statistics & Probability Letters, 177, 109147-109147.
- MSO 0-1 law for recursive random trees. Statistics & Probability Letters, 173, 109061-109061.
- Maximum sparse induced subgraphs of the binomial random graph with given number of edges. Discrete Mathematics, 344(2), 112205-112205.
- Zero–one laws for
- Existential monadic second order convergence law fails on sparse random graphs. European Journal of Combinatorics, 83, 103017-103017.
- Logical laws for short existential monadic second-order sentences about graphs. Journal of Mathematical Logic, 20(02), 2050007-2050007.
- Maximum induced subgraphs of the binomial random graph. Acta Mathematica Universitatis Comenianae, 88(3), 423-427.
- Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false. Annals of Pure and Applied Logic, 170(4), 505-514.
- Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. ACM Transactions on Computational Logic, 20(2), 1-18.
- On the first-order complexity of induced subgraph isomorphism. Logical Methods in Computer Science, 15(1), 25:1-25:24.
- The Descriptive Complexity of Subgraph Isomorphism Without Numerics. Theory of Computing Systems, 63(4), 902-921.
- Short Monadic Second Order Sentences about Sparse Random Graphs. SIAM Journal on Discrete Mathematics, 32(4), 2916-2940.
- First order sentences about random graphs: Small number of alternations. Discrete Applied Mathematics, 236, 329-346.
- Monadic second-order properties of very sparse random graphs. Annals of Pure and Applied Logic, 168(11), 2087-2101.
- Quantifier Alternation in First-Order Formulas with Infinite Spectra. Problems of Information Transmission, 53(4), 391-403.
- On the zero–one
- Bounded quantifier depth spectra for random graphs. Discrete Mathematics, 339(6), 1651-1664.
- Random graphs: models and asymptotic characteristics. Russian Mathematical Surveys, 70(1), 33-81.
- The Law of Large Numbers for the Number of Active Particles in an Epidemic Model. Theory of Probability & Its Applications, 58(2), 297-313.
- Extension of the Zero-one k-law. Electronic Notes in Discrete Mathematics, 43, 263-269.
- Zero-one
- On a sequence of random distance graphs subject to the zero-one law. Problems of Information Transmission, 47(3), 251-268.
- Maximum chordal subgraphs of random graphs. Combinatorics, Probability and Computing, 1-13.
- Threshold for stability of weak saturation. Journal of Graph Theory.
- Spectrum of FO Logic With Quantifier Depth 4 Is Finite. ACM Transactions on Computational Logic.
- Large cycles in generalized Johnson graphs. Journal of Graph Theory.
- Tight asymptotics of clique‐chromatic numbers of dense random graphs. Journal of Graph Theory.
Chapters
- Canonization of a Random Circulant Graph by Counting Walks, WALCOM: Algorithms and Computation (pp. 319-334). Springer Nature Singapore
- Cycle Saturation in Random Graphs, Trends in Mathematics (pp. 811-816). Springer International Publishing
- Covering Three-Tori with Cubes, Trends in Mathematics (pp. 772-777). Springer International Publishing
- On a Category of Cotangent Sums Related to the Nyman-Beurling Criterion for the Riemann Hypothesis, Trigonometric Sums and Their Applications (pp. 1-28). Springer International Publishing
Conference proceedings papers
- First order distinguishability of sparse random graphs. Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
- First order complexity of finite random structures. Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
- Tight Bounds on Adjacency Labels for Monotone Graph Classes. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 297
- Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes (pp 1147-1165)
- Canonization of a Random Graph by Two Matrix-Vector Multiplications. Leibniz International Proceedings in Informatics, Vol. 274
- On Anti-stochastic Properties of Unlabeled Graphs (pp 300-312)
- On the first-order complexity of induced subgraph isomorphism. Leibniz International Proceedings in Informatics, LIPIcs, Vol. 82
- The Descriptive Complexity of Subgraph Isomorphism Without Numerics (pp 308-322)
- Learning Supervised pagerank with gradient-based and gradient-free optimization methods. Advances in Neural Information Processing Systems (pp 4914-4922)
- An Optimization Framework for Propagation of Query-Document Features by Query Similarity Functions. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management
- Supervised Nested PageRank. Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management
- Fresh BrowseRank. Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval
- Introducing search behavior into browsing based models of page's importance. Proceedings of the 22nd International Conference on World Wide Web
- URL Redirection Accounting for Improving Link-Based Ranking Methods (pp 656-667)
- Recency-sensitive model of web page authority. Proceedings of the 21st ACM international conference on Information and knowledge management
- Empirical validation of the buckley-osthus model for the web host graph. Proceedings of the 21st ACM international conference on Information and knowledge management
- Randomly Twisted Hypercubes: Between Structure and Randomness. Random Structures & Algorithms, 66(1).
- Research group
-
Foundations of Computation research group
- Grants
-
Bootstrap percolation in random graphs, Royal Society, 03/2024 - 03/2026, £12,000, as PI