Cover Image

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Prolubnikov, Alexander
Format:	Preprint
Published:	2015
Subjects:	Discrete Mathematics F.2.1; G.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

Graph traversals associated with iterative methods for solving systems of linear equations
by: Prolubnikov, A. V.
Published: (2024)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
by: Pavlov, Gorgi
Published: (2026)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

A Permutation Avoidance Game with Reverse Replies and Monotone Traps
by: Ulfarsson, Henning
Published: (2026)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Natural Measures on Polyominoes Induced by the Abelian Sandpile Model
by: Sportiello, Andrea
Published: (2024)

A first efficient algorithm for enumerating all the extreme points of a bisubmodular polyhedron
by: Matsui, Yasuko, et al.
Published: (2024)

Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices
by: Gillman, David, et al.
Published: (2026)

Optimal covering of rectangular grid graphs with tours of constrained length
by: Bereg, Sergey, et al.
Published: (2025)

RTD-Conjecture and Concept Classes Induced by Graphs
by: Simon, Hans U.
Published: (2025)

On the Complexity of Problems on Graphs Defined on Groups
by: Das, Bireswar, et al.
Published: (2025)

Morphic Sequences: Complexity and Decidability
by: Henry, Raphael
Published: (2024)

Robot Positioning Using Torus Packing for Multisets
by: Chen, Chung Shue, et al.
Published: (2024)

Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
by: Cai, Jin-Yi, et al.
Published: (2025)

Extending Wormald's Differential Equation Method to One-sided Bounds
by: Bennett, Patrick, et al.
Published: (2023)

New Results on Edge-coloring and Total-coloring of Split Graphs
by: Couto, Fernanda, et al.
Published: (2023)

A simple algorithm for checking equivalence of counting functions on free monoids
by: Kiyashko, Petr, et al.
Published: (2024)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Topology-Based Reconstruction Prevention for Decentralised Learning
by: Dekker, Florine W., et al.
Published: (2023)

Dyck Paths Enumerated by the Q-bonacci Numbers
by: Barcucci, Elena, et al.
Published: (2024)

On The Roots of Independence Polynomial: Quantifying The Gap
by: Prakash, Om, et al.
Published: (2025)

A Bijection between Stacked Directed Polyominoes and Motzkin Paths with Alternative Catastrophes
by: Schager, Florian, et al.
Published: (2024)

Binary Words Containing Few Abelian Squares
by: Fazekas, Szilard Zsolt, et al.
Published: (2026)

The Converse of the Real Orthogonal Holant Theorem
by: Young, Ben
Published: (2024)

Quantitative Edge Eigenvector Universality for Random Regular Graphs: Berry-Esseen Bounds with Explicit Constants
by: Nagel, Leonhard
Published: (2025)

On the Orthogonality of Generalized Pattern Sequences
by: Li, Shuo
Published: (2024)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
by: Anand, Emile
Published: (2025)

Enumeration of Polyominoes up to Size N=59
by: Shirakawa, Toshihiro
Published: (2025)

Efficient Uniform Sampling of Surjections via their Profiles
by: Carayol, Arnaud, et al.
Published: (2026)

Fair Division Among Couples and Small Groups
by: Gölz, Paul, et al.
Published: (2025)

Constructions, bounds, and algorithms for peaceable queens
by: Clinch, Katie, et al.
Published: (2024)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
by: Shalaby, Ahmed, et al.
Published: (2024)

Incremental computation of the set of period sets
by: Rivals, Eric
Published: (2024)

Two approaches to low-parametric SimRank computation
by: Berezin, Egor P., et al.
Published: (2026)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

Almost optimum $\ell$-covering of $\mathbb{Z}_n$
by: Shi, Ke, et al.
Published: (2022)

Construction of Minkowski Sums by Cellular Automata
by: Tahay, Pierre-Adrien
Published: (2024)