DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.12

Unbalanced Expanders from Multiplicity Codes

Authors: Itay Kalev and Amnon Ta-Shma

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

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.

Cite as

Itay Kalev and Amnon Ta-Shma. Unbalanced Expanders from Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.12},
  URN =		{urn:nbn:de:0030-drops-171346},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.12},
  annote =	{Keywords: Condensers, Multiplicity codes, Differential equations}
}

Search Results

Documents authored by Kalev, Itay

Unbalanced Expanders from Multiplicity Codes

Abstract

Cite as

Thanks for your feedback!

Could not send message