2 Search Results for "Yankovitz, Tal"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.44
LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation

Authors: Gil Cohen and Tal Yankovitz

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a procedure that can amplify inverse-polynomial distances, exponentially extending the regime of distances that can be amplified by AEL. However, the improved procedure only works for LDC and assuming rate 1-1/(poly log n). In this work we devise a distance amplification procedure for LCC with inverse-polynomial distances even for vanishing rate 1/(poly log log n). For LDC, we obtain a more modest improvement and require rate 1-1/(poly log log n). Thus, the tables have turned and it is now LCC that can be better amplified. Our key idea for accomplishing this, deviating from prior work, is to tailor the distance amplification procedure to the code at hand. Our second result concerns the relation between linear LDC and LCC. We prove the existence of linear LDC that are not LCC, qualitatively extending a separation by Kaufman and Viderman (RANDOM 2010).
Cite as

Gil Cohen and Tal Yankovitz. LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.44,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{44:1--44:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.44},
  URN =		{urn:nbn:de:0030-drops-163858},
  doi =		{10.4230/LIPIcs.ICALP.2022.44},
  annote =	{Keywords: Locally Correctable Codes, Locally Decodable Codes, Distance Amplifications}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.1
Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC

Authors: Gil Cohen and Tal Yankovitz

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The main contribution of this work is a rate amplification procedure for LCC. Our procedure converts any q-query linear LCC, having rate ρ and, say, constant distance to an asymptotically good LCC with q^poly(1/ρ) queries. Our second contribution is a distance amplification procedure for LDC that converts any linear LDC with distance δ and, say, constant rate to an asymptotically good LDC. The query complexity only suffers a multiplicative overhead that is roughly equal to the query complexity of a length 1/δ asymptotically good LDC. This improves upon the poly(1/δ) overhead obtained by the AEL distance amplification procedure [Alon and Luby, 1996; Alon et al., 1995]. Our work establishes that the construction of asymptotically good LDC and LCC is reduced, with a minor overhead in query complexity, to the problem of constructing a vanishing rate linear LCC and a (rapidly) vanishing distance linear LDC, respectively.
Cite as

Gil Cohen and Tal Yankovitz. Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 1:1-1:57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2021.1,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{1:1--1:57},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.1},
  URN =		{urn:nbn:de:0030-drops-142750},
  doi =		{10.4230/LIPIcs.CCC.2021.1},
  annote =	{Keywords: Locally decodable codes, Locally correctable codes}
}
  • Refine by Author
  • 2 Cohen, Gil
  • 2 Yankovitz, Tal

  • Refine by Classification
  • 2 Theory of computation → Error-correcting codes

  • Refine by Keyword
  • 1 Distance Amplifications
  • 1 Locally Correctable Codes
  • 1 Locally Decodable Codes
  • 1 Locally correctable codes
  • 1 Locally decodable codes

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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 Imprint Privacy Contact