38 citations · 74 across the 45 of their papers we have counts for
6 papers · 1 filter
Short monadic second order sentences about sparse random graphs
Andrey Kupavskii, Maksim Zhukovskii
In this paper, we study zero-one laws for the Erdős--Rényi random graph model in the case when for . For a given class of logical sentences…
On infinite spectra of first order properties of random graphs
M. E. Zhukovskii
In this paper, we study spectra of first order properties of Erdos-Renyi random graph. We proved that minimal quantifier depth of a formula with an infinite spectrum is either 4 or…
Monadic second-order properties of very sparse random graphs
L. B. Ostrovsky, M. E. Zhukovskii
We study asymptotical probabilities of first order and monadic second order properties of Erdos-Renyi random graph G(n,n^{-a}). The random graph obeys FO (MSO) zero-one k-law if fo…
The Descriptive Complexity of Subgraph Isomorphism without Numerics
Oleg Verbitsky, Maksim Zhukovskii
Let be a connected graph with vertices. The existence of a subgraph isomorphic to can be defined in first-order logic with quantifier depth no better than , si…
Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods
Lev Bogolubsky, Pavel Dvurechensky, Alexander Gasnikov +5
In this paper, we consider a non-convex loss-minimization problem of learning Supervised PageRank models, which can account for some properties not considered by classical approach…
Universal Zero-One --Law
Aleksandr Matushkin
In this paper the limit probabilities of first-order properties are studied. The random graph {\it obeys Zero-One -Law} if for each first-order property with quantifier…