License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.12
URN: urn:nbn:de:0030-drops-171346
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17134/
Go to the corresponding LIPIcs Volume Portal

Kalev, Itay ; Ta-Shma, Amnon

Unbalanced Expanders from Multiplicity Codes

pdf-format:
LIPIcs-APPROX12.pdf (0.7 MB)

Abstract

In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a basic building block in many constructions, and, in particular, is behind the state of the art extractor constructions.
We give an alternative construction that is based on Multiplicity codes. While the bottom-line result is similar to the GUV result, the analysis is very different. In GUV (and Parvaresh-Vardy codes) the polynomial ring is closed to a finite field, and every polynomial is associated with related elements in the finite field. In our construction a polynomial from the polynomial ring is associated with its iterated derivatives. Our analysis boils down to solving a differential equation over a finite field, and uses previous techniques, introduced by Kopparty (in [Swastik Kopparty, 2015]) for the list-decoding setting. We also observe that these (and more general) questions were studied in differential algebra, and we use the terminology and result developed there.
We believe these techniques have the potential of getting better constructions and solving the current bottlenecks in the area.

BibTeX - Entry

@InProceedings{kalev_et_al:LIPIcs.APPROX/RANDOM.2022.12,
  author =	{Kalev, Itay and Ta-Shma, Amnon},
  title =	{{Unbalanced Expanders from Multiplicity Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17134},
  URN =		{urn:nbn:de:0030-drops-171346},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.12},
  annote =	{Keywords: Condensers, Multiplicity codes, Differential equations}
}

Keywords: Condensers, Multiplicity codes, Differential equations
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI