Document Open Access Logo

Unbalanced Expanders from Multiplicity Codes

Authors Itay Kalev, Amnon Ta-Shma

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.12.pdf
  • Filesize: 0.72 MB
  • 14 pages

Document Identifiers

Author Details

Itay Kalev
  • Department of Computer Science, Tel Aviv University, Israel
Amnon Ta-Shma
  • Department of Computer Science, Tel Aviv University, Israel

Funding

  • Kalev, Itay: Supported by Len Blavatnik and the Blavatnik Family foundation and by the Israel Science Foundation grant number 952/18.
  • Ta-Shma, Amnon: Supported by the Israel Science Foundation grant number 952/18.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.12

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Condensers
  • Multiplicity codes
  • Differential equations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nir Aviv and Amnon Ta-Shma. On the entropy loss and gap of condensers. ACM Trans. Comput. Theory, 11(3):15:1-15:14, 2019. URL: https://doi.org/10.1145/3317691.
  2. Aharon Gavriel Beged-Dov. Lower and upper bounds for the number of lattice points in a simplex. SIAM Journal on Applied Mathematics, 22(1):106-108, 1972. URL: https://doi.org/10.1137/0122012.
  3. Yevgeniy Dodis, Krzysztof Pietrzak, and Daniel Wichs. Key derivation without entropy waste. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 93-110. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_6.
  4. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. SIAM J. Comput., 42(6):2305-2328, 2013. URL: https://doi.org/10.1137/100783704.
  5. Sebastian Falkensteiner, Yi Zhang, and Thieu N. Vo. On existence and uniqueness of formal power series solutions of algebraic ordinary differential equations. Mediterranean Journal of Mathematics, 19(2):74, February 2022. URL: https://doi.org/10.1007/s00009-022-01984-w.
  6. Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Comb., 28(4):415-440, 2008. URL: https://doi.org/10.1007/s00493-008-2259-3.
  7. Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. J. ACM, 56(4):20:1-20:34, 2009. URL: https://doi.org/10.1145/1538902.1538904.
  8. Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of reed-solomon codes. IEEE Trans. Inf. Theory, 59(6):3257-3268, 2013. URL: https://doi.org/10.1109/TIT.2013.2246813.
  9. Swastik Kopparty. List-decoding multiplicity codes. Theory Comput., 11:149-182, 2015. URL: https://doi.org/10.4086/toc.2015.v011a005.
  10. Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. J. ACM, 61(5):28:1-28:20, 2014. URL: https://doi.org/10.1145/2629416.
  11. Maksim Amiryanovich Limonov. Generalized separants of differential polynomials. Moscow University Mathematics Bulletin, 70(6):248-252, 2015. URL: https://doi.org/10.3103/S0027132215060029.
  12. Farzad Parvaresh and Alexander Vardy. Correcting errors beyond the guruswami-sudan radius in polynomial time. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 285-294. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.29.
  13. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discret. Math., 13(1):2-24, 2000. URL: https://doi.org/10.1137/S0895480197329508.
  14. Joseph Fels Ritt. Differential algebra, volume 33. American Mathematical Soc., 1950. Google Scholar
  15. Amnon Ta-Shma and Christopher Umans. Better condensers and new extractors from parvaresh-vardy codes. In Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012, pages 309-315. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/CCC.2012.25.
  16. Amnon Ta-Shma, Christopher Umans, and David Zuckerman. Lossless condensers, unbalanced expanders, and extractors. Comb., 27(2):213-240, 2007. URL: https://doi.org/10.1007/s00493-007-0053-2.
  17. Amnon Ta-Shma and David Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50(12):3015-3025, 2004. URL: https://doi.org/10.1109/TIT.2004.838377.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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