Document Open Access Logo

The Quest for Strong Inapproximability Results with Perfect Completeness

Authors Joshua Brakensiek, Venkatesan Guruswami

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.4.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Author Details

Joshua Brakensiek
Venkatesan Guruswami

Cite As Get BibTex

Joshua Brakensiek and Venkatesan Guruswami. The Quest for Strong Inapproximability Results with Perfect Completeness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.4

Abstract

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP.  This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the UGC. For the important case when the input CSP instance admits a satisfying assignment, it therefore remains wide open to understand how well it can be approximated.

This work is motivated by the pursuit of a better understanding of the inapproximability of perfectly satisfiable instances of CSPs. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover which we call "V label cover."  Assuming a conjecture concerning the inapproximability of V label cover on perfectly satisfiable instances, we prove the following implications:

* There is an absolute constant c0 such that for k >= 3, given a satisfiable instance of Boolean k-CSP, it is hard to find an assignment satisfying more than c0 k^2/2^k fraction of the constraints.

* Given a k-uniform hypergraph, k >= 2, for all epsilon > 0, it is hard to tell if it is q-strongly colorable or has no independent set with an epsilon fraction of vertices, where q = ceiling[k + sqrt(k) - 0.5].

* Given a k-uniform hypergraph, k >= 3, for all epsilon > 0, it is hard to tell if it is (k-1)-rainbow colorable or has no independent set with an epsilon fraction of vertices.

We further supplement the above results with a proof that an ``almost Unique'' version of Label Cover can be approximated within a constant factor on satisfiable instances.

Subject Classification

Keywords
  • inapproximability
  • hardness of approximation
  • dictatorship testing
  • constraint satisfaction
  • hypergraph coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Venkat Anantharam, Amin Gohari, Sudeep Kamath, and Chandra Nair. On Maximal Correlation, Hypercontractivity, and the Data Processing Inequality studied by Erkip and Cover. arXiv:1304.6133 [cs, math], April 2013. arXiv: 1304.6133. URL: http://arxiv.org/abs/1304.6133.
  2. Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. computational complexity, 18(2):249-271, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0272-6.
  3. N. Bansal and S. Khot. Optimal Long Code Test with One Free Bit. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 453-462, October 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.23.
  4. Nikhil Bansal and Subhash Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In 37th International Colloquium on Automata, Languages and Programming, pages 250-261, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_22.
  5. Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Approximate hypergraph coloring under low-discrepancy and related promises. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 152-174. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.152.
  6. Joshua Brakensiek and Venkatesan Guruswami. New Hardness Results for Graph and Hypergraph Colorings. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.14.
  7. Joshua Brakensiek and Venkatesan Guruswami. The quest for strong inapproximability results with perfect completenes. Electronic Colloquium on Computational Complexity (ECCC), 24(80), 2017. URL: https://eccc.weizmann.ac.il/report/2017/080/.
  8. Jonah Brown-Cohen and Prasad Raghavendra. Combinatorial optimization algorithms via polymorphisms. CoRR, abs/1501.01598, 2015. URL: http://arxiv.org/abs/1501.01598.
  9. Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC'13, pages 447-456, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2488608.2488665.
  10. Siu On Chan. Approximation resistance from pairwise-independent subgroups. J. ACM, 63(3):27, 2016. URL: http://dx.doi.org/10.1145/2873054.
  11. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms, 5(3), 2009. URL: http://dx.doi.org/10.1145/1541885.1541893.
  12. Ernie Croot, Vsevolod Lev, and Peter Pach. Progression-free sets in Z_4ⁿ are exponentially small. arXiv:1605.01506 [math], May 2016. arXiv: 1605.01506. URL: http://arxiv.org/abs/1605.01506.
  13. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM Journal on Computing, 39(3):843-873, 2009. URL: http://dx.doi.org/10.1137/07068062X.
  14. Irit Dinur, Oded Regev, and Clifford D. Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5):519-535, 2005. Google Scholar
  15. Jordan S. Ellenberg and Dion Gijswijt. On large subsets of F_qⁿ with no three-term arithmetic progression. arXiv:1605.09223 [math], May 2016. arXiv: 1605.09223. URL: http://arxiv.org/abs/1605.09223.
  16. Lars Engebretsen. The nonapproximability of non-boolean predicates. SIAM J. Discrete Math., 18(1):114-129, 2004. URL: http://dx.doi.org/10.1137/S0895480100380458.
  17. Lars Engebretsen and Jonas Holmerin. More efficient queries in pcps for NP and improved approximation hardness of maximum CSP. Random Struct. Algorithms, 33(4):497-514, 2008. URL: http://dx.doi.org/10.1002/rsa.20226.
  18. Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput., 41(6):1558-1590, 2012. URL: http://dx.doi.org/10.1137/120865094.
  19. Hans Gebelein. Das statistische Problem der Korrelation als Variations- und Eigenwertproblem und sein Zusammenhang mit der Ausgleichsrechnung. ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, 21(6):364-379, January 1941. URL: http://dx.doi.org/10.1002/zamm.19410210604.
  20. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878-914, 2011. Google Scholar
  21. Venkatesan Guruswami, Johan Håstad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31(6):1663-1686, 2002. Google Scholar
  22. Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discrete Math., 18(1):30-40, 2004. Google Scholar
  23. Venkatesan Guruswami and Euiwoong Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. Combinatorica, 2015. Accepted. Google Scholar
  24. Venkatesan Guruswami and Euiwoong Lee. Nearly optimal NP-hardness of unique coverage. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1724-1730, 2016. Google Scholar
  25. Venkatesan Guruswami and Prasad Raghavendra. Constraint satisfaction over a non-boolean domain: Approximation algorithms and Unique-Games hardness. In Proceedings of the 11th International Workshop on Approximation, Randomization and Combinatorial Optimization (APPROX), pages 77-90, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85363-3_7.
  26. Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu. Bypassing UGC from some optimal geometric inapproximability results. ACM Trans. Algorithms, 12(1):6, 2016. Google Scholar
  27. Venkatesan Guruswami and Ali Kemal Sinop. Improved inapproximability results for maximum k-colorable subgraph. Theory of Computing, 9:413-435, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a011.
  28. Gustav Hast. Approximating max k-CSP - outperforming a random assignment with almost a linear factor. In 32nd International Colloquium on Automata, Languages and Programming, pages 956-968, 2005. Google Scholar
  29. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: http://dx.doi.org/10.1145/502090.502098.
  30. Johan Håstad and Subhash Khot. Query Efficient PCPs with Perfect Completeness. Theory of Computing, 1:119-148, September 2005. URL: http://dx.doi.org/10.4086/toc.2005.v001a007.
  31. H. O. Hirschfeld. A Connection between Correlation and Contingency. Mathematical Proceedings of the Cambridge Philosophical Society, 31(4):520-524, October 1935. URL: http://dx.doi.org/10.1017/S0305004100013517.
  32. Sangxia Huang. Approximation resistance on satisfiable instances for predicates strictly dominating parity. Electronic Colloquium on Computational Complexity (ECCC), 19:40, 2012. URL: https://eccc.weizmann.ac.il/report/2012/040/.
  33. Sangxia Huang. Approximation resistance on satisfiable instances for sparse predicates. Theory of Computing, 10:359-388, 2014. URL: http://dx.doi.org/10.4086/toc.2014.v010a014.
  34. Sangxia Huang. 2^(log N)^1/10-o(1) hardness for hypergraph coloring. Technical report, Electronic Colloquium on Computational Complexity (ECCC), 2015. URL: https://eccc.weizmann.ac.il/report/2015/062/.
  35. Johan Håstad. On the np-hardness of max-not-2. SIAM Journal on Computing, 43(1):179-193, 2014. URL: http://dx.doi.org/10.1137/120882718.
  36. Gil Kalai. A Fourier-theoretic perspective on the Condorcet paradox and arrow’s theorem. Advances in Applied Mathematics, 29(3):412-426, 2002. URL: http://dx.doi.org/10.1016/S0196-8858(02)00023-4.
  37. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. Combinatorica, 20(3):393-415, 2000. Google Scholar
  38. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 767-775, 2002. Google Scholar
  39. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM Journal on Computing, 37(1):319-357, 2007. URL: http://dx.doi.org/10.1137/S0097539705447372.
  40. Subhash Khot, Dor Minzer, and Muli Safra. On Independent Sets, 2-to-2 Games and Grassmann Graphs. Technical Report 124, Electrontic Colloquium on Computational Complexity (ECCC), August 2016. URL: https://eccc.weizmann.ac.il/report/2016/124/.
  41. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.019.
  42. Subhash Khot and Rishi Saket. Hardness of coloring 2-colorable 12-uniform hypergraphs with ith 2^(log n)^Ω(1) colors. In 55th IEEE Annual Symposium on Foundations of Computer Science, pages 206-215, 2014. Google Scholar
  43. Subhash Khot and Rishi Saket. Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1607-1625, 2014. Google Scholar
  44. Euiwoong Lee. Hardness of graph pricing through generalized max-dicut. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 391-399, 2015. URL: http://dx.doi.org/10.1145/2746539.2746549.
  45. Euiwoong Lee. Improved hardness for cut, interdiction, and firefighter problems. CoRR, abs/1607.05133, 2016. URL: http://arxiv.org/abs/1607.05133.
  46. Konstantin Makarychev and Yury Makarychev. Approximation Algorithm for Non-Boolean Max-k-CSP. Theory of Computing, 10:341-358, October 2014. URL: http://dx.doi.org/10.4086/toc.2014.v010a013.
  47. Colin McDiarmid. A random recolouring method for graphs and hypergraphs. Combinatorics, Probability and Computing, 2:363-365, 9 1993. URL: http://dx.doi.org/10.1017/S0963548300000730.
  48. Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19(6):1713-1756, 2010. URL: http://dx.doi.org/10.1007/s00039-010-0047-x.
  49. Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Ann. of Math. (2), 171(1):295-341, 2010. URL: http://dx.doi.org/10.4007/annals.2010.171.295.
  50. Ryan O'Donnell. Some topics in analysis of boolean functions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 569-578, 2008. URL: http://dx.doi.org/10.1145/1374376.1374458.
  51. Ryan O'Donnell and Yi Wu. Conditional hardness for satisfiable 3-CSPs. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC'09, pages 493-502, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1536414.1536482.
  52. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 245-254, 2008. Google Scholar
  53. Prasad Raghavendra. Approximating NP-hard problems: Efficient algorithms and their limits. PhD thesis, University of Washington, 2009. Google Scholar
  54. A. Rényi. On measures of dependence. Acta Mathematica Academiae Scientiarum Hungarica, 10(3-4):441-451, September 1959. URL: http://dx.doi.org/10.1007/BF02024507.
  55. S. Sachdeva and R. Saket. Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. In 2013 IEEE Conference on Computational Complexity, pages 219-229, June 2013. URL: http://dx.doi.org/10.1109/CCC.2013.30.
  56. A. Samorodnitsky and L. Trevisan. Gowers Uniformity, Influence of Variables, and PCPs. SIAM Journal on Computing, 39(1):323-360, January 2009. URL: http://dx.doi.org/10.1137/070681612.
  57. Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 191-199, 2000. URL: http://dx.doi.org/10.1145/335305.335329.
  58. Madhu Sudan and Luca Trevisan. Probabilistically checkable proofs with low amortized query complexity. In 39th Annual Symposium on Foundations of Computer Science, pages 18-27, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743425.
  59. Suguru Tamaki and Yuichi Yoshida. A query efficient non-adaptive long code test with perfect completeness. In Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 738-751, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-642-15369-3_55.
  60. Luca Trevisan. Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72-88, 1998. URL: http://dx.doi.org/10.1007/PL00009209.
  61. Luca Trevisan. Approximating satisfiable satisfiability problems. Algorithmica, 28(1):145-172, 2000. URL: http://dx.doi.org/10.1007/s004530010035.
  62. Girish Varma. Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. arXiv:1408.0262 [cs], August 2014. arXiv: 1408.0262. URL: http://arxiv.org/abs/1408.0262.
  63. Cenny Wenner. Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theory of Computing, 9(23):703-757, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a023.
  64. H. Witsenhausen. On Sequences of Pairs of Dependent Random Variables. SIAM Journal on Applied Mathematics, 28(1):100-113, January 1975. URL: http://dx.doi.org/10.1137/0128010.
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 About DROPS Imprint Privacy Contact