Maksim Zhukovskii

Orcid: 0000-0001-8763-9533

Affiliations:
  • University of Sheffield, Department of Computer Science, UK
  • Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, Russia (former)


According to our database1, Maksim Zhukovskii authored at least 57 papers between 2011 and 2025.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2025
Randomly Twisted Hypercubes: Between Structure and Randomness.
Random Struct. Algorithms, January, 2025

Weak saturation in graphs: A combinatorial approach.
J. Comb. Theory B, 2025

On the maximum number of common neighbours in dense random regular graphs.
Eur. J. Comb., 2025

Canonical Labeling of Sparse Random Graphs.
Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024
Spectrum of FO Logic with Quantifier Depth 4 is Finite.
ACM Trans. Comput. Log., April, 2024

On vertex Ramsey graphs with forbidden subgraphs.
Discret. Math., March, 2024

Maximum Number of Symmetric Extensions in Random Graphs.
SIAM J. Discret. Math., 2024

On Isomorphism-Invariant Antistochastic Properties of Random Graphs.
SIAM J. Discret. Math., 2024

Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes.
SIAM J. Comput., 2024

Maximum chordal subgraphs of random graphs.
Comb. Probab. Comput., 2024

Functionality of Random Graphs.
CoRR, 2024

Canonical labelling of sparse random graphs.
CoRR, 2024

New bounds for the optimal density of covering single-insertion codes via the Turán density.
CoRR, 2024

Gathering Information about a Graph by Counting Walks from a Single Vertex.
CoRR, 2024

Canonization of a Random Circulant Graph by Counting Walks.
Proceedings of the WALCOM: Algorithms and Computation, 2024

First order distinguishability of sparse random graphs.
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

First order complexity of finite random structures.
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Tight Bounds on Adjacency Labels for Monotone Graph Classes.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023
Large cycles in generalized Johnson graphs.
J. Graph Theory, December, 2023

Weak saturation stability.
Eur. J. Comb., December, 2023

Cycle Saturation in Random Graphs.
SIAM J. Discret. Math., September, 2023

Tight asymptotics of clique-chromatic numbers of dense random graphs.
J. Graph Theory, July, 2023

The distribution of the maximum number of common neighbors in the random graph.
Eur. J. Comb., 2023

Tight concentration of star saturation number in random graphs.
Discret. Math., 2023

Reconstruction of colours.
CoRR, 2023

Small But Unwieldy.
CoRR, 2023

Canonization of a Random Graph by Two Matrix-Vector Multiplications.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022
EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs.
SIAM J. Discret. Math., September, 2022

Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth.
ACM Trans. Comput. Log., 2022

<i>γ</i>-variable first-order logic of uniform attachment random graphs.
Discret. Math., 2022

Large cycles in random generalized Johnson graphs.
Discret. Math., 2022

On the sizes of large subgraphs of the binomial random graph.
Discret. Math., 2022

Distribution of tree parameters by martingale approach.
Comb. Probab. Comput., 2022

A very sharp threshold for first order logic distinguishability of random graphs.
CoRR, 2022

On Anti-stochastic Properties of Unlabeled Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

2021
Maximum sparse induced subgraphs of the binomial random graph with given number of edges.
Discret. Math., 2021

Maximum induced forests in random graphs.
Discret. Appl. Math., 2021

2020
Logical laws for short existential monadic second-order sentences about graphs.
J. Math. Log., 2020

Existential monadic second order convergence law fails on sparse random graphs.
Eur. J. Comb., 2020

Zero-one laws for k-variable first-order logic of sparse random graphs.
Discret. Appl. Math., 2020

2019
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism.
ACM Trans. Comput. Log., 2019

The Descriptive Complexity of Subgraph Isomorphism Without Numerics.
Theory Comput. Syst., 2019

On the First-Order Complexity of Induced Subgraph Isomorphism.
Log. Methods Comput. Sci., 2019

Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false.
Ann. Pure Appl. Log., 2019

2018
Short Monadic Second Order Sentences about Sparse Random Graphs.
SIAM J. Discret. Math., 2018

First order sentences about random graphs: Small number of alternations.
Discret. Appl. Math., 2018

2017
Quantifier Alternation in First-Order Formulas with Infinite Spectra.
Probl. Inf. Transm., 2017

On the zero-one k-law extensions.
Eur. J. Comb., 2017

Around power law for PageRank components in Buckley-Osthus model of web graph.
CoRR, 2017

Monadic second-order properties of very sparse random graphs.
Ann. Pure Appl. Log., 2017

2016
Bounded quantifier depth spectra for random graphs.
Discret. Math., 2016

The Descriptive Complexity of Subgraph Isomorphism in the Absence of Order.
CoRR, 2016

Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

2013
Extension of the Zero-one k-law.
Electron. Notes Discret. Math., 2013

URL Redirection Accounting for Improving Link-Based Ranking Methods.
Proceedings of the Advances in Information Retrieval, 2013

2012
Zero-one k-law.
Discret. Math., 2012

2011
On a sequence of random distance graphs subject to the zero-one law.
Probl. Inf. Transm., 2011


  Loading...