Cover Image

Improved Explicit Near-Optimal Codes in the High-Noise Regimes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Xin, Mao, Songtao
Format:	Preprint
Published:	2024
Subjects:	Information Theory Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Unbounded Error Correcting Codes
by: Efremenko, Klim, et al.
Published: (2024)

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

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

Source Coding with Free Bits and the Multi-Way Number Partitioning Problem
by: Ahmadypour, Niloufar, et al.
Published: (2020)

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
by: Guo, Zeyu, et al.
Published: (2023)

Perturbation-Resilient Trades for Dynamic Service Balancing
by: Sima, Jin, et al.
Published: (2024)

Trellis codes with a good distance profile constructed from expander graphs
by: Zhu, Yubin, et al.
Published: (2026)

Robust Gray Codes Approaching the Optimal Rate
by: Con, Roni, et al.
Published: (2024)

Improved Approximation Algorithms for Index Coding
by: Chawin, Dror, et al.
Published: (2024)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
by: Guruswami, Venkatesan, et al.
Published: (2023)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

Construction of orientable sequences in $O(1)$-amortized time per bit
by: Gabric, Daniel, et al.
Published: (2024)

The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings
by: Hou, Jiaxin, et al.
Published: (2023)

On constrained intersection representations of graphs and digraphs
by: Cicalese, Ferdinando, et al.
Published: (2025)

Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
by: Bruno, Roberto, et al.
Published: (2025)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

A Method for Generating Connected Erdos-Renyi Random Graphs
by: Chinyaev, Boris
Published: (2025)

Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
by: Li, Xiaxin, et al.
Published: (2025)

Lightweight Near-Additive Spanners
by: Gitlitz, Yuval, et al.
Published: (2024)

Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
by: Hsieh, Jun-Ting, et al.
Published: (2026)

An Alternate Proof of Near-Optimal Light Spanners
by: Bodwin, Greg
Published: (2023)

Improved Decoding of Tanner Codes
by: Zhou, Zhaienhe, et al.
Published: (2025)

Capacity-Achieving Gray Codes
by: Guruswami, Venkatesan, et al.
Published: (2024)

Old and New Results on Alphabetic Codes
by: Bruno, Roberto, et al.
Published: (2025)

Towards Optimal Grammars for RNA Structures
by: Onokpasa, Evarista, et al.
Published: (2024)

Kernels for Storage Capacity and Dual Index Coding
by: Haviv, Ishay
Published: (2025)

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

Investigations on Algorithm Selection for Interval-Based Coding Methods
by: Strutz, Tilo, et al.
Published: (2024)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

Optimal Bounds for Distinct Quartics
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

An Additive Approximation Scheme for Generating Dyadic Codings for the Outputs of an LLM
by: Bar-Lev, Daniella, et al.
Published: (2026)

List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics
by: Peikert, Chris, et al.
Published: (2025)

Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
by: Brakensiek, Joshua, et al.
Published: (2025)

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
by: Rao, Shravas
Published: (2023)

Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
by: Nozaki, Yuta, et al.
Published: (2024)

Optimal Bounds for Open Addressing Without Reordering
by: Farach-Colton, Martin, et al.
Published: (2025)