License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.58
URN: urn:nbn:de:0030-drops-94620
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9462/
Go to the corresponding LIPIcs Volume Portal

Viderman, Michael

Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness

pdf-format:
LIPIcs-APPROX-RANDOM-2018-58.pdf (0.5 MB)

Abstract

An error-correcting code C subseteq F^n is called (q,epsilon)-strong locally testable code (LTC) if there exists a tester that makes at most q queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords x not in C with probability at least epsilon * delta(x,C), where delta(x,C) denotes the relative Hamming distance between the word x and the code C. The parameter q is called the query complexity and the parameter epsilon is called soundness.
Goldreich and Sudan (J.ACM 2006) asked about the existence of strong LTCs with constant query complexity, constant relative distance, constant soundness and inverse polylogarithmic rate. They also asked about the explicit constructions of these codes.
Strong LTCs with the required range of parameters were obtained recently in the works of Viderman (CCC 2013, FOCS 2013) based on the papers of Meir (SICOMP 2009) and Dinur (J.ACM 2007). However, the construction of these codes was probabilistic.
In this work we show that codes presented in the works of Dinur (J.ACM 2007) and Ben-Sasson and Sudan (SICOMP 2005) provide the explicit construction of strong LTCs with the above range of parameters. Previously, such codes were proven to be weak LTCs. Using the results of Viderman (CCC 2013, FOCS 2013) we prove that such codes are, in fact, strong LTCs.

BibTeX - Entry

@InProceedings{viderman:LIPIcs:2018:9462,
  author =	{Michael Viderman},
  title =	{{Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9462},
  URN =		{urn:nbn:de:0030-drops-94620},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.58},
  annote =	{Keywords: Error-Correcting Codes, Tensor Products, Locally Testable Codes}
}

Keywords: Error-Correcting Codes, Tensor Products, Locally Testable Codes
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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