Cover Image

High Rate Efficient Local List Decoding from HDX

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dikstein, Yotam, Hopkins, Max, Impagliazzo, Russell, Pitassi, Toniann
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Hypercontractivity on HDX II: Symmetrization and q-Norms
by: Hopkins, Max
Published: (2024)

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

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

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

The Greedy Coin Change Problem
by: Gupta, Shreya, et al.
Published: (2024)

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

KRW Composition Theorems via Lifting
by: de Rezende, Susanna F., et al.
Published: (2020)

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

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

Testing Juntas and Junta Subclasses with Relative Error
by: Chen, Xi, et al.
Published: (2025)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Advances in List Decoding of Polynomial Codes
by: Kumar, Mrinal, et al.
Published: (2026)

A Simple Sub-Polynomial Degree Coboundary Expander
by: Hopkins, Max, et al.
Published: (2026)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

LDPC Codes Achieve List Decoding Capacity
by: Mosheiff, Jonathan, et al.
Published: (2019)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
by: Grigorescu, Elena, et al.
Published: (2025)

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

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Approximate Replicability in Learning
by: Hopkins, Max, et al.
Published: (2025)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
by: Block, Alexander R., et al.
Published: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
by: Blocki, Jeremiah, et al.
Published: (2021)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
by: Srivastava, Shashank, et al.
Published: (2025)

High Rate Multivariate Polynomial Evaluation Codes
by: Kopparty, Swastik, et al.
Published: (2024)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
by: Janzer, Oliver, et al.
Published: (2024)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
by: Doron, Dean, et al.
Published: (2024)

Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity
by: Gama, Simone Ingrid Monteiro, et al.
Published: (2025)

Fully-Fluctuating Participation in Sleepy Consensus
by: Efron, Yuval, et al.
Published: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

Improved List Size for Folded Reed-Solomon Codes
by: Srivastava, Shashank
Published: (2024)

On the Complexity of Decoded Quantum Interferometry
by: Marwaha, Kunal, et al.
Published: (2025)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

Locally Sampleable Uniform Symmetric Distributions
by: Kane, Daniel M., et al.
Published: (2024)

Spectral Lower Bounds for Local Search
by: Brânzei, Simina, et al.
Published: (2024)

Decoding Balanced Linear Codes With Preprocessing
by: Bogdanov, Andrej, et al.
Published: (2025)

Relaxed Local Correctability from Local Testing
by: Kumar, Vinayak M., et al.
Published: (2023)