Imagen de Portada

Canonization of a random circulant graph by counting walks

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Verbitsky, Oleg, Zhukovskii, Maksim
Formato:	Preprint
Publicado:	2023
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

Combinatorial refinement on circulant graphs
por: Kluge, Laurence
Publicado: (2022)

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

Quantum embedding of graphs for subgraph counting
por: Adhikari, Bibhas
Publicado: (2026)

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

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

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

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

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

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

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

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

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

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

Revisiting Tree Canonization using polynomials
por: Arvind, V., et al.
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

Approximately counting maximal independent set is equivalent to #SAT
por: Zhang, Hao, et al.
Publicado: (2024)

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

Sensitivity and Hamming graphs
por: Asensio, Sara, et al.
Publicado: (2025)

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

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

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

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

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

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