Imagen de Portada

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Blocki, Jeremiah, Cheng, Kuan, Grigorescu, Elena, Li, Xin, Zheng, Yu, Zhu, Minshen
Formato:	Preprint
Publicado:	2021
Materias:	Information Theory Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Amortized Locally Decodable Codes for Insertions and Deletions
por: Blocki, Jeremiah, et al.
Publicado: (2025)

Amortized Locally Decodable Codes
por: Blocki, Jeremiah, et al.
Publicado: (2025)

On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
por: Cheng, Kuan, et al.
Publicado: (2023)

Oblivious Deletion Codes
por: Con, Roni, et al.
Publicado: (2025)

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

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

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

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

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

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

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

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

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

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

Insertion Correcting Capability for Quantum Deletion-Correcting Codes
por: Nakamura, Ken, et al.
Publicado: (2026)

Two-Insertion/Deletion/Substitution Correcting Codes
por: Pi, Yuhang, et al.
Publicado: (2024)

Function-Correcting Codes for Insertion-Deletion Channel
por: Singh, Anamika, et al.
Publicado: (2025)

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

Decoding Algorithm to Composite Errors Consisting of Deletions and Insertions for Quantum Deletion-Correcting Codes Based on Quantum Reed-Solomon Codes
por: Sasaki, Koki, et al.
Publicado: (2026)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
por: Braverman, Mark, et al.
Publicado: (2025)

Improved Decoding of Tanner Codes
por: Zhou, Zhaienhe, et al.
Publicado: (2025)

Decoding Algorithm Correcting Single-Insertion Plus Single-Deletion for Non-binary Quantum Codes
por: Nakamura, Ken, et al.
Publicado: (2024)

Improved Johnson-type Bounds for Insertion-Deletion Codes
por: Yang, Yulin
Publicado: (2026)

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

Efficient Decoding of Insertion and Deletion Errors for Helberg Codes
por: Segrest, Anthony, et al.
Publicado: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
por: Lowe, Angus, et al.
Publicado: (2022)

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

Optimal Two-Dimensional Reed--Solomon Codes Correcting Insertions and Deletions
por: Con, Roni, et al.
Publicado: (2023)

Decoding Insertions/Deletions via List Recovery
por: Banerjee, Anisha, et al.
Publicado: (2025)

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

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

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

Exponential speedups in fault-tolerant processing of quantum experiments
por: Kannan, Ishaan, et al.
Publicado: (2026)

Multiset Deletion-Correcting Codes: Bounds and Constructions
por: Kreindel, Avraham, et al.
Publicado: (2026)

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

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

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
por: Ko, Young Kun
Publicado: (2026)

The Optimization of Random Tree Codes for Limited Computational Resources
por: Bacinoglu, B. Tan
Publicado: (2025)

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