M. Zhukovskii

activity

20132023

most citedLearning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods

38 citations · 74 across the 45 of their papers we have counts for

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2023

Canonization of a random graph by two matrix-vector multiplications

Oleg Verbitsky, Maksim Zhukovskii

We show that a canonical labeling of a random $n$ -vertex graph can be obtained by assigning to each vertex $x$ the triple $(w_{1} (x), w_{2} (x), w_{3} (x))$ , where $w_{k} (x)$ is the number of…

cs.CC2018

Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism

Oleg Verbitsky, Maksim Zhukovskii

Let $v (F)$ denote the number of vertices in a fixed connected pattern graph $F$ . We show an infinite family of patterns $F$ such that the existence of a subgraph isomorphic to $F$ …

cs.CC2017★ 3 cited

On the First-Order Complexity of Induced Subgraph Isomorphism

Oleg Verbitsky, Maksim Zhukovskii

Given a graph $F$ , let $I (F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W [F]$ denote the minimum $k$ such that $I (F)$ is definable in $k$ -variable first-or…

cs.CC2016

The Descriptive Complexity of Subgraph Isomorphism without Numerics

Oleg Verbitsky, Maksim Zhukovskii

Let $F$ be a connected graph with $ℓ$ vertices. The existence of a subgraph isomorphic to $F$ can be defined in first-order logic with quantifier depth no better than $ℓ$ , si…