:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Verbitsky, Oleg, Zhukovskii, Maksim
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2310.05788
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Canonical labelling of sparse random graphs
by: Verbitsky, Oleg, et al.
Published: (2024)

What can be computed in average anonymous networks?
by: Rybicki, Joel, et al.
Published: (2026)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

On the Expressibility of the Reconstructional Color Refinement
by: Arvind, V., et al.
Published: (2024)

New bounds for the optimal density of covering single-insertion codes via the Turán density
by: Pikhurko, Oleg, et al.
Published: (2024)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

Combinatorial refinement on circulant graphs
by: Kluge, Laurence
Published: (2022)

First order distinguishability of sparse random graphs
by: Hershko, Tal, et al.
Published: (2024)

Gathering Information about a Graph by Counting Walks from a Single Vertex
by: Fuhlbrück, Frank, et al.
Published: (2024)

A very sharp threshold for first order logic distinguishability of random graphs
by: Benjamini, Itai, et al.
Published: (2022)

Quantum embedding of graphs for subgraph counting
by: Adhikari, Bibhas
Published: (2026)

Complexity classification of counting graph homomorphisms modulo a prime number
by: Bulatov, Andrei A., et al.
Published: (2021)

Non-linear Hopf manifolds are locally conformally Kahler
by: Ornea, Liviu, et al.
Published: (2022)

Quadratic differentials and random walks on the dual graph of a pants decomposition
by: Bordenave, Charles, et al.
Published: (2026)

Normal form of bimeromorphically contractible holomorphic Lagrangian submanifolds
by: Amerik, Ekaterina, et al.
Published: (2023)

Maximum chordal subgraphs of random graphs
by: Krivelevich, Michael, et al.
Published: (2023)

Non-isomorphic subgraphs in random graphs
by: Krivelevich, Michael, et al.
Published: (2025)

Canonical labelling of random regular graphs
by: Isaev, Mikhail, et al.
Published: (2026)

Reconstructing random graphs from distance queries
by: Krivelevich, Michael, et al.
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

First order complexity of finite random structures
by: Demin, Danila, et al.
Published: (2024)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

Do products of compact complex manifolds admit LCK metrics?
by: Ornea, Liviu, et al.
Published: (2022)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

On the maximum number of common neighbours in dense random regular graphs
by: Isaev, Mikhail, et al.
Published: (2023)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, et al.
Published: (2025)

The Lee--Gauduchon cone on complex manifolds
by: Ornea, Liviu, et al.
Published: (2024)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

On the approximability of graph visibility problems
by: Bilò, Davide, et al.
Published: (2024)

On the computational power of $C$-random strings
by: Milovanov, Alexey
Published: (2024)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)

Disjoint covering of bipartite graphs with $s$-clubs
by: Monti, Angelo, et al.
Published: (2024)

Quantum search by continuous-time quantum walk on t-designs
by: Lugão, Pedro H. G., et al.
Published: (2023)

The Borsuk number of a graph
by: Cáceres, José, et al.
Published: (2026)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

Elfs, transducers and quantum walks
by: Apers, Simon, et al.
Published: (2026)