Image de couverture de livre

Relaxed Local Correctability from Local Testing

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kumar, Vinayak M., Mon, Geoffrey
Format:	Preprint
Publié:	2023
Sujets:	Computational Complexity Information Theory
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
par: Grigorescu, Elena, et autres
Publié: (2025)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
par: Block, Alexander R., et autres
Publié: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
par: Blocki, Jeremiah, et autres
Publié: (2021)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
par: Alrabiah, Omar, et autres
Publié: (2024)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
par: Janzer, Oliver, et autres
Publié: (2024)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
par: Cheng, Kuan, et autres
Publié: (2026)

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

Advances in List Decoding of Polynomial Codes
par: Kumar, Mrinal, et autres
Publié: (2026)

Deterministic list decoding of Reed-Solomon codes
par: Chatterjee, Soham, et autres
Publié: (2025)

High Rate Multivariate Polynomial Evaluation Codes
par: Kopparty, Swastik, et autres
Publié: (2024)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
par: Goyal, Rohan, et autres
Publié: (2023)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
par: Goyal, Rohan, et autres
Publié: (2025)

An exposition of recent list-size bounds of FRS Codes
par: Garg, Abhibhav, et autres
Publié: (2025)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
par: Chen, Kean, et autres
Publié: (2025)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
par: Braverman, Mark, et autres
Publié: (2025)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
par: Chen, Zitan
Publié: (2023)

Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
par: Fawzi, Omar, et autres
Publié: (2023)

Oblivious Deletion Codes
par: Con, Roni, et autres
Publié: (2025)

Space-bounded online Kolmogorov complexity is additive
par: Bauwens, Bruno, et autres
Publié: (2025)

Decoding Balanced Linear Codes With Preprocessing
par: Bogdanov, Andrej, et autres
Publié: (2025)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
par: Goyal, Rohan, et autres
Publié: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
par: Drucker, Andrew, et autres
Publié: (2024)

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
par: Li, Songsong, et autres
Publié: (2025)

Improved PIR Schemes using Matching Vectors and Derivatives
par: Ghasemi, Fatemeh, et autres
Publié: (2024)

Explicit Constant-Alphabet Subspace Design Codes
par: Goyal, Rohan, et autres
Publié: (2026)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
par: Ming, Gao
Publié: (2022)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
par: Doron, Dean, et autres
Publié: (2024)

Kolmogorov-Loveland betting strategies lose the Betting game on open sets
par: Petrović, Tomislav
Publié: (2024)

Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
par: Bauwens, Bruno, et autres
Publié: (2025)

Assembly Theory Reduced to Shannon Entropy and Rendered Redundant by Naive Statistical Algorithms
par: Ozelim, Luan, et autres
Publié: (2024)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
par: Jeronimo, Fernando Granha, et autres
Publié: (2026)

The Optimization of Random Tree Codes for Limited Computational Resources
par: Bacinoglu, B. Tan
Publié: (2025)

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
par: Moradi, Mohsen, et autres
Publié: (2024)

Half-duplex communication complexity with adversary can be less than the classical communication complexity
par: Dektiarev, Mikhail, et autres
Publié: (2024)

Tight Quantum Time-Space Tradeoffs for Permutation Inversion
par: Akshima, et autres
Publié: (2025)

Explicit Codes approaching Generalized Singleton Bound using Expanders
par: Jeronimo, Fernando Granha, et autres
Publié: (2025)

Strong XOR Lemma for Information Complexity
par: Sawettamalya, Pachara, et autres
Publié: (2024)

Some Thoughts on Symbolic Transfer Entropy
par: Jin, Dian
Publié: (2024)

Improved List Size for Folded Reed-Solomon Codes
par: Srivastava, Shashank
Publié: (2024)

Recovering polynomials over finite fields from noisy character values
par: Kopparty, Swastik
Publié: (2026)