Cover Image

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mittal, Tushant, Roy, Sourya
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Discrete Mathematics Group Theory Representation Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pseudorandomness of Expander Walks via Fourier Analysis on Groups
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
by: Dwivedi, Prateek, et al.
Published: (2026)

Ordering groups and the Identity Problem
by: Bodart, Corentin, et al.
Published: (2024)

The Identity Problem in the special affine group of $\mathbb{Z}^2$
by: Dong, Ruiwen
Published: (2023)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

On Word Representations and Embeddings in Complex Matrices
by: Bell, Paul C., et al.
Published: (2026)

Explicit Lossless Vertex Expanders
by: Hsieh, Jun-Ting, et al.
Published: (2025)

Tensor decomposition beyond uniqueness, with an application to the minrank problem
by: Koiran, Pascal, et al.
Published: (2025)

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

On Linear Representation, Complexity and Inversion of maps over finite fields
by: Anantharaman, Ramachandran, et al.
Published: (2020)

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
by: Bhandari, Siddharth, et al.
Published: (2021)

The Rate-Immediacy Barrier in Explicit Tree Code Constructions
by: Cohen, Gil, et al.
Published: (2025)

Coboundary expansion inside Chevalley coset complex HDXs
by: O'Donnell, Ryan, et al.
Published: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

A Group Theoretic Construction of Batch Codes
by: Thomas, Eldho K.
Published: (2025)

Reconfiguring Graph Homomorphisms on the Sphere
by: Lee, Jae-Baek, et al.
Published: (2018)

An Eventown Result for Permutations
by: Lindzey, Nathan
Published: (2026)

Hamilton decompositions of the directed 3-torus: a return-map and odometer view
by: Park, SangHyun
Published: (2026)

Transitive Sets of Mutually Orthogonal Latin Squares
by: Keita, Amadou, et al.
Published: (2026)

Ergodic properties of concurrent systems
by: Abbes, Samy, et al.
Published: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy
by: Gribanov, Dmitry, et al.
Published: (2025)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
by: Jeronimo, Fernando Granha, et al.
Published: (2022)

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
by: Bangachev, Kiril, et al.
Published: (2024)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
by: Tsui, Darin, et al.
Published: (2025)

Sylow theorems for supergroups
by: Serganova, Vera, et al.
Published: (2024)

Massless Representations in Conformal Space and Their de Sitter Restrictions
by: Gazeau, Jean-Pierre, et al.
Published: (2026)

Realizability of Subgroups by Subshifts of Finite Type
by: Bitar, Nicolás
Published: (2024)

Graph-theoretical estimates of the diameters of the Rubik's Cube groups
by: Hirata, So
Published: (2024)

Weakly and Strongly Aperiodic Subshifts of Finite Type on Baumslag-Solitar Groups
by: Esnay, Solène J., et al.
Published: (2020)

Period-rigidity of one-relator groups
by: Esnay, Solène J., et al.
Published: (2025)

A two-player version of the assignment problem
by: Galliot, Florian, et al.
Published: (2026)

A Faster Isomorphism Test for Graphs of Small Degree
by: Grohe, Martin, et al.
Published: (2018)

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
by: Onah, Chinonso, et al.
Published: (2026)

Membership problems in nilpotent groups
by: Bodart, Corentin
Published: (2024)

Bounded Generation of Submonoids of Heisenberg Groups
by: Shafrir, Doron
Published: (2024)

On finite extensions of lamplighter groups
by: Bodart, Corentin
Published: (2025)

Graph subshifts
by: Arrighi, Pablo, et al.
Published: (2023)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)