Cover Image

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dikstein, Yotam, Dinur, Irit
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
by: Dikstein, Yotam, et al.
Published: (2024)

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

Swap cosystolic expansion
by: Dikstein, Yotam, et al.
Published: (2023)

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

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

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

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

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

Tensor rank and dimension expanders
by: Dvir, Zeev
Published: (2025)

High Rate Efficient Local List Decoding from HDX
by: Dikstein, Yotam, et al.
Published: (2026)

The geodesic cover problem for butterfly networks
by: Manuel, Paul, et al.
Published: (2022)

A criterion for Andrásfai--Erdős--Sós type theorems and applications
by: Hou, Jianfeng, et al.
Published: (2024)

Approximate cycle double cover
by: Ghanbari, Babak, et al.
Published: (2025)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Quasipolynomial bounds for the corners theorem
by: Jaber, Michael, et al.
Published: (2025)

Factorization norms and an inverse theorem for MaxCut
by: Balla, Igor, et al.
Published: (2025)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
by: Yang, Chao, et al.
Published: (2024)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

On Approximability of Satisfiable k-CSPs: IV
by: Bhangale, Amey, et al.
Published: (2023)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

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

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
by: Biswas, Ari, et al.
Published: (2025)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)