Imagen de Portada

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Dikstein, Yotam, Dinur, Irit, Lubotzky, Alexander
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Combinatorics Group Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
por: Dikstein, Yotam, et al.
Publicado: (2023)

Non-commutative error correcting codes and proper subgroup testing
por: Chapman, Michael, et al.
Publicado: (2024)

Boolean functions on high-dimensional expanders
por: Dikstein, Yotam, et al.
Publicado: (2018)

Conditional Non-Soficity of p-adic Deligne Extensions: on a Theorem of Gohla and Thom
por: Chapman, Michael, et al.
Publicado: (2024)

Coboundary and cosystolic expansion without dependence on dimension or degree
por: Dikstein, Yotam, et al.
Publicado: (2023)

Chernoff Bounds and Reverse Hypercontractivity on HDX
por: Dikstein, Yotam, et al.
Publicado: (2024)

Swap cosystolic expansion
por: Dikstein, Yotam, et al.
Publicado: (2023)

HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem
por: Shen, Hanwen, et al.
Publicado: (2025)

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

Sparse juntas on the biased hypercube
por: Dinur, Irit, et al.
Publicado: (2017)

Sparse High Dimensional Expanders via Local Lifts
por: Yaacov, Inbar Ben, et al.
Publicado: (2024)

The Aldous--Lyons Conjecture I: Subgroup Tests
por: Bowen, Lewis, et al.
Publicado: (2024)

Coboundary expansion of coset complexes
por: Kaufman, Tali, et al.
Publicado: (2024)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
por: Collins, Nathaniel A., et al.
Publicado: (2024)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
por: Dinur, Itai, et al.
Publicado: (2021)

Geometric Combinatorics of Polynomials II: Polynomials and Cell Structures
por: Dougherty, Michael, et al.
Publicado: (2024)

Testability in group theory
por: Becker, Oren, et al.
Publicado: (2022)

Testability of relations between permutations
por: Becker, Oren, et al.
Publicado: (2020)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
por: Dinur, Irit, et al.
Publicado: (2024)

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime
por: Mittal, Tushant, et al.
Publicado: (2024)

Low-Degree Polynomials Are Good Extractors
por: Alrabiah, Omar, et al.
Publicado: (2024)

Some properties of Higman-Thompson monoids and digital circuits
por: Birget, J. C.
Publicado: (2024)

Complexity of some algorithmic problems in groups: a survey
por: Shpilrain, Vladimir
Publicado: (2024)

The complexity of knapsack problems in wreath products
por: Figelius, Michael, et al.
Publicado: (2020)

Orbit-blocking words in free groups
por: Koch-Hyde, Lucy, et al.
Publicado: (2025)

On the complexity of the word problem of the R. Thompson group V
por: Birget, J. C.
Publicado: (2022)

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

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
por: Alrabiah, Omar, et al.
Publicado: (2024)

Efficient Compression in Semigroups
por: Thumm, Alexander, et al.
Publicado: (2026)

Remembering Mark Sapir
por: Birget, Jean-Camille, et al.
Publicado: (2024)

Membership and Conjugacy in Inverse Semigroups
por: Fleischer, Lukas, et al.
Publicado: (2025)

Punctured Low-Bias Codes Behave Like Random Linear Codes
por: Guruswami, Venkatesan, et al.
Publicado: (2021)

On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
por: Johnson, Dan, et al.
Publicado: (2025)

Upper Bounds on the Chromatic Index of Linear Hypergraphs
por: Murff, Thomas, et al.
Publicado: (2025)

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

Avoshifts
por: Salo, Ville
Publicado: (2024)

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

On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
por: Nosan, Klara, et al.
Publicado: (2021)

Obstruction theory and the complexity of counting group homomorphisms
por: Samperton, Eric, et al.
Publicado: (2026)

Distortion element in the automorphism group of a full shift
por: Callard, Antonin, et al.
Publicado: (2022)