Image de couverture de livre

Isomorphism Testing of Rooted Trees in Linear Time

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Lindeberg, Anna
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Testing Isomorphism of Graphs in Polynomial Time
par: Xue, Rui
Publié: (2023)

Quantum Algorithms for Approximate Graph Isomorphism Testing
par: Kulkarni, Prateek P.
Publié: (2026)

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction
par: Bshouty, Nader H.
Publié: (2025)

Simulating Time With Square-Root Space
par: Williams, R. Ryan
Publié: (2025)

Biased Linearity Testing in the 1% Regime
par: Khot, Subhash, et autres
Publié: (2025)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
par: Berkholz, Christoph, et autres
Publié: (2024)

Dynamic Planar Graph Isomorphism is in DynFO
par: Datta, Samir, et autres
Publié: (2026)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
par: Datta, Swarnalipa, et autres
Publié: (2023)

On Optimal Testing of Linearity
par: Arora, Vipul, et autres
Publié: (2024)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
par: Mondada, Luca, et autres
Publié: (2023)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
par: Gibor, Daniel
Publié: (2025)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
par: Gryaznov, Svyatoslav, et autres
Publié: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
par: Roberson, David E., et autres
Publié: (2023)

Parity Tests with Ties
par: Kupfer, Ron
Publié: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
par: Li, Tiange, et autres
Publié: (2026)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
par: Erhardt, Alexander, et autres
Publié: (2025)

New Direct Sum Tests
par: Westover, Alek, et autres
Publié: (2024)

Local Correction of Linear Functions over the Boolean Cube
par: Amireddy, Prashanth, et autres
Publié: (2024)

Linear Planar 3-SAT and Its Applications in Planning
par: Desbois, Victorien, et autres
Publié: (2025)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
par: Arvind, V., et autres
Publié: (2022)

Low-Degree Testing Over Grids
par: Amireddy, Prashanth, et autres
Publié: (2023)

On Matrix Multiplication and Polynomial Identity Testing
par: Andrews, Robert
Publié: (2022)

Quasi-Linear Size PCPs with Small Soundness from HDX
par: Bafna, Mitali, et autres
Publié: (2024)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
par: Ketkov, Sergey S., et autres
Publié: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
par: Sajith, Thejas Radhika
Publié: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
par: Ramya, C., et autres
Publié: (2025)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
par: Yamakami, Tomoyuki
Publié: (2017)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
par: Bhangale, Amey, et autres
Publié: (2026)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
par: Mukhopadhyay, Partha, et autres
Publié: (2025)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
par: Bhattacharjee, Sutanay, et autres
Publié: (2026)

Characterizing Direct Product Testing via Coboundary Expansion
par: Bafna, Mitali, et autres
Publié: (2023)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
par: Grigorescu, Elena, et autres
Publié: (2025)

Nearly-Linear Time Seeded Extractors with Short Seeds
par: Doron, Dean, et autres
Publié: (2024)

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
par: Lassota, Alexandra, et autres
Publié: (2026)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
par: Shpilka, Amir, et autres
Publié: (2026)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
par: Andrews, Robert, et autres
Publié: (2024)

The Root Theorem of Context Engineering
par: Schick, Borja Odriozola
Publié: (2026)

Termination of Real Linear Loops
par: Neumann, Eike, et autres
Publié: (2026)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
par: Arvind, V., et autres
Publié: (2023)

Trading Determinism for Time: The k-Reach Problem
par: Bhadra, Ronak, et autres
Publié: (2024)