Image de couverture de livre

Tight bounds for stream decodable error-correcting codes

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Gupta, Meghal, Guruswami, Venkatesan, Singhal, Mihir
Format:	Preprint
Publié:	2024
Sujets:	Information Theory Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Capacity-Achieving Gray Codes
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Optimal quantile estimation: beyond the comparison model
par: Gupta, Meghal, et autres
Publié: (2024)

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
par: Alrabiah, Omar, et autres
Publié: (2023)

Redundancy Is All You Need (for CSP Sparsification)
par: Brakensiek, Joshua, et autres
Publié: (2024)

Tight Bounds for Sparsifying Random CSPs
par: Brakensiek, Joshua, et autres
Publié: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Deletion-correcting codes for an adversarial nanopore channel
par: Xie, Huiling, et autres
Publié: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Semirandom Planted Clique via 1-norm Isometry Property
par: Guruswami, Venkatesan, et autres
Publié: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
par: Guruswami, Venkatesan, et autres
Publié: (2024)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
par: Cohen, Edith, et autres
Publié: (2024)

Error Correction for Message Streams
par: Gupta, Meghal, et autres
Publié: (2023)

Worst-case optimal adaptive alphabetic prefix-free coding
par: Gagie, Travis
Publié: (2021)

Interactive Coding with Unbounded Noise
par: Fargion, Eden, et autres
Publié: (2024)

More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more
par: Ghentiyala, Surendra, et autres
Publié: (2024)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
par: Gu, Yuzhou, et autres
Publié: (2025)

Scheduling Problems with Constrained Rejections
par: Davies, Sami, et autres
Publié: (2025)

Hardness of Learning Boolean Functions from Label Proportions
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
par: Cohen, Edith, et autres
Publié: (2025)

Locally computing edge orientations
par: Mitrović, Slobodan, et autres
Publié: (2025)

Trellis codes with a good distance profile constructed from expander graphs
par: Zhu, Yubin, et autres
Publié: (2026)

Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation
par: Gupta, Shivam, et autres
Publié: (2023)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
par: Mitrović, Slobodan, et autres
Publié: (2026)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
par: Guruswami, Venkatesan, et autres
Publié: (2025)

A probabilistic analysis on general probabilistic scheduling problems
par: Suruga, Daiki
Publié: (2024)

Key Compression Limits for $k$-Minimum Value Sketches
par: Dickens, Charlie, et autres
Publié: (2024)

Robust Gray Codes Approaching the Optimal Rate
par: Con, Roni, et autres
Publié: (2024)

Investigations on Algorithm Selection for Interval-Based Coding Methods
par: Strutz, Tilo, et autres
Publié: (2024)

Graph Reconstruction from Noisy Random Subgraphs
par: McGregor, Andrew, et autres
Publié: (2024)

Continuous Optimization for Decoding Errors
par: Srivastava, Shashank
Publié: (2024)

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
par: Rivkin, Joey, et autres
Publié: (2024)

Towards Optimal Grammars for RNA Structures
par: Onokpasa, Evarista, et autres
Publié: (2024)

Scheduling Multi-Server Jobs is Not Easy
par: Vaze, Rahul
Publié: (2024)

Improved Approximation Algorithms for Index Coding
par: Chawin, Dror, et autres
Publié: (2024)

Hardness and Approximability of Dimension Reduction on the Probability Simplex
par: Bruno, Roberto
Publié: (2024)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
par: Bruno, Roberto, et autres
Publié: (2024)

Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication
par: Ly, Hoang, et autres
Publié: (2025)

Preprocessing Uncertain Data into Supersequences for Sorting and Gaps
par: Löffler, Maarten, et autres
Publié: (2026)

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
par: Pettie, Seth, et autres
Publié: (2020)