Cover Image

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Alrabiah, Omar, Guruswami, Venkatesan
Format:	Preprint
Published:	2024
Subjects:	Information Theory Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
by: Goyal, Rohan, et al.
Published: (2025)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
by: First, Uriya A., et al.
Published: (2024)

Explicit Constant-Alphabet Subspace Design Codes
by: Goyal, Rohan, et al.
Published: (2026)

Classification of Non-redundancy of Boolean Predicates of Arity 4
by: Brakensiek, Joshua, et al.
Published: (2026)

Maximal Recoverability: A Nexus of Coding Theory
by: Brakensiek, Joshua, et al.
Published: (2026)

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

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

Generic Reed-Solomon Codes Achieve List-decoding Capacity
by: Brakensiek, Joshua, et al.
Published: (2022)

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

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

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

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

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

A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble
by: Guruswami, Venkatesan, et al.
Published: (2023)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
by: Cheng, Kuan, et al.
Published: (2026)

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)

Explicit optimal-length locally repairable codes of distance 5
by: Beemer, Allison, et al.
Published: (2018)

Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
by: Goldberg, Guy, et al.
Published: (2025)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
by: Goldenberg, Elazar, et al.
Published: (2024)

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

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

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

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
by: Guruswami, Venkatesan, et al.
Published: (2025)

Secret Sharing on Superconcentrator
by: Li, Yuan
Published: (2023)

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

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

Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
by: Fawzi, Omar, et al.
Published: (2023)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

Explicit Codes approaching Generalized Singleton Bound using Expanders
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

Quantum LDPC Codes of Almost Linear Distance via Homological Products
by: Golowich, Louis, et al.
Published: (2024)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
by: Doron, Dean, et al.
Published: (2024)

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
by: Moradi, Mohsen, et al.
Published: (2024)

Tight Quantum Time-Space Tradeoffs for Permutation Inversion
by: Akshima, et al.
Published: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
by: Drucker, Andrew, et al.
Published: (2024)

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

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)