2 Search Results for "Jalan, Akhil"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.43
Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio

Authors: Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this paper, we show that random Gabidulin codes of block length n and rate R achieve the (average-radius) list decoding capacity of radius 1-R-ε in the rank metric with an order-optimal column-to-row ratio of O(ε). This extends the recent work of Guo, Xing, Yuan, and Zhang (FOCS 2024), improving their column-to-row ratio from O(ε/n) to O(ε). For completeness, we also establish a matching lower bound on the column-to-row ratio for capacity-achieving Gabidulin codes in the rank metric. Our proof techniques build on the work of Guo and Zhang (FOCS 2023), who showed that randomly punctured Reed-Solomon codes over fields of quadratic size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020) in the Hamming metric. The proof of our lower bound follows the method of Alrabiah, Guruswami, and Li (SODA 2024) for codes in the Hamming metric.
Cite as

Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang. Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2025.43,
  author =	{Guo, Zeyu and Xing, Chaoping and Yuan, Chen and Zhang, Zihan},
  title =	{{Gabidulin Codes Achieve List Decoding Capacity with an Order-Optimal Column-To-Row Ratio}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{43:1--43:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.43},
  URN =		{urn:nbn:de:0030-drops-244095},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.43},
  annote =	{Keywords: coding theory, error-correcting codes, Gabidulin codes, rank-metric codes}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.24
Near-Optimal Cayley Expanders for Abelian Groups

Authors: Akhil Jalan and Dana Moshkovitz

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We give an efficient deterministic algorithm that outputs an expanding generating set for any finite abelian group. The size of the generating set is close to the randomized construction of Alon and Roichman [Alon and Roichman, 1994], improving upon various deterministic constructions in both the dependence on the dimension and the spectral gap. By obtaining optimal dependence on the dimension we resolve a conjecture of Azar, Motwani, and Naor [Azar et al., 1998] in the affirmative. Our technique is an extension of the bias amplification technique of Ta-Shma [Ta-Shma, 2017], who used random walks on expanders to obtain expanding generating sets over the additive group of 𝔽₂ⁿ. As a consequence, we obtain (i) randomness-efficient constructions of almost k-wise independent variables, (ii) a faster deterministic algorithm for the Remote Point Problem, (iii) randomness-efficient low-degree tests, and (iv) randomness-efficient verification of matrix multiplication.
Cite as

Akhil Jalan and Dana Moshkovitz. Near-Optimal Cayley Expanders for Abelian Groups. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jalan_et_al:LIPIcs.FSTTCS.2021.24,
  author =	{Jalan, Akhil and Moshkovitz, Dana},
  title =	{{Near-Optimal Cayley Expanders for Abelian Groups}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.24},
  URN =		{urn:nbn:de:0030-drops-155359},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.24},
  annote =	{Keywords: Cayley graphs, Expander walks, Epsilon-biased sets, Derandomization}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021

  • Refine by Author
  • 1 Guo, Zeyu
  • 1 Jalan, Akhil
  • 1 Moshkovitz, Dana
  • 1 Xing, Chaoping
  • 1 Yuan, Chen
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Coding theory
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Cayley graphs
  • 1 Derandomization
  • 1 Epsilon-biased sets
  • 1 Expander walks
  • 1 Gabidulin codes
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact