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.2019.9
URN: urn:nbn:de:0030-drops-112245
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11224/
Go to the corresponding LIPIcs Volume Portal

Harsha, Prahladh ; Khot, Subhash ; Lee, Euiwoong ; Thiruvenkatachari, Devanathan

Improved 3LIN Hardness via Linear Label Cover

pdf-format:
LIPIcs-APPROX-RANDOM-2019-9.pdf (0.6 MB)

Abstract

We prove that for every constant c and epsilon = (log n)^{-c}, there is no polynomial time algorithm that when given an instance of 3-LIN with n variables where an (1 - epsilon)-fraction of the clauses are satisfiable, finds an assignment that satisfies atleast (1/2 + epsilon)-fraction of clauses unless NP subseteq BPP. The previous best hardness using a polynomial time reduction achieves epsilon = (log log n)^{-c}, which is obtained by the Label Cover hardness of Moshkovitz and Raz [J. ACM, 57(5), 2010] followed by the reduction from Label Cover to 3-LIN of Håstad [J. ACM, 48(4):798 - 859, 2001].
Our main idea is to prove a hardness result for Label Cover similar to Moshkovitz and Raz where each projection has a linear structure. This linear structure of Label Cover allows us to use Hadamard codes instead of long codes, making the reduction more efficient. For the hardness of Linear Label Cover, we follow the work of Dinur and Harsha [SIAM J. Comput., 42(6):2452 - 2486, 2013] that simplified the construction of Moshkovitz and Raz, and observe that running their reduction from a hardness of the problem LIN (of unbounded arity) instead of the more standard problem of solving quadratic equations ensures the linearity of the resultant Label Cover.

BibTeX - Entry

@InProceedings{harsha_et_al:LIPIcs:2019:11224,
  author =	{Prahladh Harsha and Subhash Khot and Euiwoong Lee and Devanathan Thiruvenkatachari},
  title =	{{Improved 3LIN Hardness via Linear Label Cover}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11224},
  URN =		{urn:nbn:de:0030-drops-112245},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.9},
  annote =	{Keywords: probabilistically checkable proofs, PCP, composition, 3LIN, low soundness error}
}

Keywords: probabilistically checkable proofs, PCP, composition, 3LIN, low soundness error
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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