TY - GEN
T1 - Improved 3LIN hardness via linear label cover
AU - Harsha, Prahladh
AU - Khot, Subhash
AU - Lee, Euiwoong
AU - Thiruvenkatachari, Devanathan
N1 - Funding Information:
Prahladh Harsha: Supported in part by the DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467 (while the author was visiting Rutgers University and DIMACS) and the Swarnajayanti Fellowship. Subhash Khot: Supported by the NSF Award CCF-1422159, the Simons Collaboration on Algorithms and Geometry and the Simons Investigator Award. Euiwoong Lee: Supported in part by the Simons Collaboration on Algorithms and Geometry. Devanathan Thiruvenkatachari: Supported by same sources as Subhash Khot.
Funding Information:
Funding Prahladh Harsha: Supported in part by the DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467 (while the author was visiting Rutgers University and DIMACS) and the Swarnajayanti Fellowship. Subhash Khot: Supported by the NSF Award CCF-1422159, the Simons Collaboration on Algorithms and Geometry and the Simons Investigator Award. Euiwoong Lee: Supported in part by the Simons Collaboration on Algorithms and Geometry. Devanathan Thiruvenkatachari: Supported by same sources as Subhash Khot.
Publisher Copyright:
© Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari.
PY - 2019/9
Y1 - 2019/9
N2 - We prove that for every constant c and ε = (log n)−c, there is no polynomial time algorithm that when given an instance of 3-LIN with n variables where an (1 − ε)-fraction of the clauses are satisfiable, finds an assignment that satisfies atleast (1/2 + ε)-fraction of clauses unless NP ⊆ BPP. The previous best hardness using a polynomial time reduction achieves ε = (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.
AB - We prove that for every constant c and ε = (log n)−c, there is no polynomial time algorithm that when given an instance of 3-LIN with n variables where an (1 − ε)-fraction of the clauses are satisfiable, finds an assignment that satisfies atleast (1/2 + ε)-fraction of clauses unless NP ⊆ BPP. The previous best hardness using a polynomial time reduction achieves ε = (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.
KW - 3LIN
KW - Composition
KW - Low soundness error
KW - PCP
KW - Probabilistically checkable proofs
UR - http://www.scopus.com/inward/record.url?scp=85072851289&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85072851289&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2019.9
DO - 10.4230/LIPIcs.APPROX-RANDOM.2019.9
M3 - Conference contribution
AN - SCOPUS:85072851289
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
A2 - Achlioptas, Dimitris
A2 - Vegh, Laszlo A.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
Y2 - 20 September 2019 through 22 September 2019
ER -