Cover Image

Improved Approximation Algorithms for Index Coding

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chawin, Dror, Haviv, Ishay
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Kernelization for Orthogonality Dimension
by: Haviv, Ishay, et al.
Published: (2024)

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
by: Haviv, Ishay
Published: (2022)

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

A Fixed-Parameter Algorithm for the Kneser Problem
by: Haviv, Ishay
Published: (2022)

Testing Intersectingness of Uniform Families
by: Haviv, Ishay, et al.
Published: (2024)

Kernelization for $H$-Coloring
by: Berkman, Yael, et al.
Published: (2025)

Nearly Orthogonal Sets over Finite Fields
by: Chawin, Dror, et al.
Published: (2024)

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

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)

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

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

Improved Explicit Near-Optimal Codes in the High-Noise Regimes
by: Li, Xin, et al.
Published: (2024)

Hardness and Approximability of Dimension Reduction on the Probability Simplex
by: Bruno, Roberto
Published: (2024)

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

Approximate Message Passing for Quantum State Tomography
by: Siekierski, Noah, 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)

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

On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
by: Wang, Ziao, et al.
Published: (2022)

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)

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
by: Wang, Ziao, et al.
Published: (2023)

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)

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

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

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

Fast One-Pass Sparse Approximation of the Top Eigenvectors of Huge Approximately Low-Rank Matrices? Yes, $MAM^*$!
by: Boahen, Edem, et al.
Published: (2025)

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
by: Guo, Zeyu, 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)

Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry
by: Chee, Yeow Meng, et al.
Published: (2023)

Entropy Coding of Unordered Data Structures
by: Kunze, Julius, et al.
Published: (2024)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
by: Al-okaily, Anas
Published: (2024)

A probabilistic analysis on general probabilistic scheduling problems
by: Suruga, Daiki
Published: (2024)

Key Compression Limits for $k$-Minimum Value Sketches
by: Dickens, Charlie, et al.
Published: (2024)

Graph Reconstruction from Noisy Random Subgraphs
by: McGregor, Andrew, et al.
Published: (2024)

More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more
by: Ghentiyala, Surendra, et al.
Published: (2024)

Continuous Optimization for Decoding Errors
by: Srivastava, Shashank
Published: (2024)