Cover Image

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grochow, Joshua A., Levet, Michael
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms Computational Complexity Logic in Computer Science Group Theory 20-08, 68Q17, 68Q19, 68Q25, 20A15 F.2.2; I.1.2; F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Group Order Logic
by: Dahan, Anatole
Published: (2025)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
by: Grochow, Joshua A., et al.
Published: (2023)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
by: Bannach, Max, et al.
Published: (2025)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

Quantum Search without Global Diffusion
by: Burke, John, et al.
Published: (2026)

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

$XX^{t}$ Can Be Faster
by: Rybin, Dmitry, et al.
Published: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

On the complexity of epimorphism testing with virtually abelian targets
by: Elder, Murray, et al.
Published: (2025)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)