Cover Image

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Bshouty, Nader H.
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Isomorphism Testing of Rooted Trees in Linear Time
by: Lindeberg, Anna
Published: (2024)

Quantum Algorithms for Approximate Graph Isomorphism Testing
by: Kulkarni, Prateek P.
Published: (2026)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

Testing Isomorphism of Boolean Functions over Finite Abelian Groups
by: Datta, Swarnalipa, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
by: Blum, Avrim, et al.
Published: (2025)

Sublinear-query relative-error testing of halfspaces
by: Chen, Xi, et al.
Published: (2026)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

The Lens of Abelian Embeddings
by: Minzer, Dor
Published: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

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

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
by: Kahanamoku-Meyer, Gregory D., et al.
Published: (2024)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
by: Chattopadhyay, Arkadev, et al.
Published: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

The Ideal Membership Problem and Abelian Groups
by: Bulatov, Andrei A., et al.
Published: (2022)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
by: Berkholz, Christoph, et al.
Published: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
by: DeJesse, Nicholas, et al.
Published: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
by: He, Yumeng, et al.
Published: (2024)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
by: Kosoy, Vanessa, et al.
Published: (2016)

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
by: Khamis, Mahmoud Abo, et al.
Published: (2026)

Constructive Separations from Gate Elimination
by: Carmosino, Marco, et al.
Published: (2026)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

An Improved Construction of Variety-Evasive Subspace Families
by: Andrews, Robert, et al.
Published: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

On Exact Learning of $d$-Monotone Functions
by: Bshouty, Nader H.
Published: (2025)

A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing
by: Bshouty, Nader H.
Published: (2026)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
by: Chen, Yangjun
Published: (2023)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
by: Bhangale, Amey, et al.
Published: (2026)

A Reply to "On Salum's Algorithm for X3SAT"
by: Salum, Latif
Published: (2021)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
by: Lassota, Alexandra, et al.
Published: (2025)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
by: Laakkonen, Tuomas, et al.
Published: (2022)