LIPIcs.APPROX-RANDOM.2019.9.pdf
- Filesize: 0.59 MB
- 16 pages
Document
Improved 3LIN Hardness via Linear Label Cover
Authors
Prahladh Harsha 
,
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-17
File
Document Identifiers
Author Details
Cite As Get BibTex
Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari. Improved 3LIN Hardness via Linear Label Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.9
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- probabilistically checkable proofs
- PCP
- composition
- 3LIN
- low soundness error
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, May 1998. (Preliminary version in 33rd FOCS, 1992). URL: https://doi.org/10.1145/278298.278306.
- Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45(1):70-122, January 1998. (Preliminary version in 33rd FOCS, 1992). URL: https://doi.org/10.1145/273865.273901.
- Irit Dinur and Prahladh Harsha. Composition of low-error 2-query PCPs using decodable PCPs. SIAM J. Comput., 42(6):2452-2486, 2013. (Preliminary version in 51st FOCS, 2009). URL: https://doi.org/10.1137/100788161.
- Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proc. 46th ACM Symp. on Theory of Computing (STOC), pages 624-633, 2014. URL: https://doi.org/10.1145/2591796.2591884.
- Oded Goldreich. A Sample of Samplers: A Computational Perspective on Sampling. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, volume 6650 of LNCS, pages 302-332. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_24.
- Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, July 2001. (Preliminary version in 29th STOC, 1997). URL: https://doi.org/10.1145/502090.502098.
- Johan Håstad and Srinivasan Venkatesh. On the advantage over a random assignment. Random Structures Algorithms, 25(2):117-149, 2004. (Preliminary version in 34th STOC, 2002). URL: https://doi.org/10.1002/rsa.20031.
- Subhash Khot. Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. In Proc. 42nd IEEE Symp. on Foundations of Comp. Science (FOCS), pages 600-609, 2001. URL: https://doi.org/10.1109/SFCS.2001.959936.
- Subhash Khot. Inapproximability Results for Computational Problems on Lattices. In Phong Q. Nguyen and Brigitte Vallée, editors, The LLL Algorithm - Survey and Applications, Information Security and Cryptography, pages 453-473. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-02295-1_14.
- Subhash Khot and Assaf Naor. Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies. SIAM J. Comput., 38(4):1448-1463, 2008. (Preliminary version in 48th FOCS, 2007). URL: https://doi.org/10.1137/070691140.
- Dana Moshkovitz. The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. Theory Comput., 11:221-235, 2015. (Preliminary version in 15th APPROX, 2012). URL: https://doi.org/10.4086/toc.2015.v011a007.
- Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM, 57(5), 2010. (Preliminary version in 49th FOCS, 2008). URL: https://doi.org/10.1145/1754399.1754402.
- Ran Raz. A Parallel Repetition Theorem. SIAM J. Comput., 27(3):763-803, June 1998. (Preliminary version in 27th STOC, 1995). URL: https://doi.org/10.1137/S0097539795280895.