Cover Image

Canonization of a random graph by two matrix-vector multiplications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Verbitsky, Oleg, Zhukovskii, Maksim
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

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

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

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

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)

Partial and weighted matrix multiplication
by: Vrana, Péter
Published: (2024)

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

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

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

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

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

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)

Quantum advantage from random geometrically-two-local Hamiltonian dynamics
by: Quek, Yihui
Published: (2025)

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

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

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

Barriers for rectangular matrix multiplication
by: Christandl, Matthias, et al.
Published: (2020)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, 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)

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

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

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

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

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

Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)

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

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

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

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

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

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Proportionally dense subgraphs of maximum size in degree-constrained graphs
by: Baghirova, Narmina, et al.
Published: (2024)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

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

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

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Fast interpolation and multiplication of unbalanced polynomials
by: Giorgi, Pascal, et al.
Published: (2024)