Document Open Access Logo

Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs

Authors Amey Bhangale, Aleksa Stanković

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.21.pdf
  • Filesize: 0.8 MB
  • 21 pages

Document Identifiers

Author Details

Amey Bhangale
  • University of California, Riverside, CA, USA
Aleksa Stanković
  • Department of Mathematics, KTH Royal Institute of Technology, Sweden

Funding

  • Stanković, Aleksa: Research supported by the Approximability and Proof Complexity project funded by the Knut and Alice Wallenberg Foundation.

Cite As Get BibTex

Amey Bhangale and Aleksa Stanković. Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.21

Abstract

Factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely defined by its factor graph and the list of predicates. We show inapproximability of Max-3-LIN over non-abelian groups (both in the perfect completeness case and in the imperfect completeness case), with the same inapproximability factor as in the general case, even when the factor graph is fixed. 
Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x⋅ y⋅ z = g, where x,y,z are the variables and g is a group element. We use representation theory and Fourier analysis over non-abelian groups to analyze the reductions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Universal factor graphs
  • linear equations
  • non-abelian groups
  • hardness of approximation

Metrics

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

Related Versions

References

  1. Aleksa Stankovic Amey Bhangale. Max-3-lin over non-abelian groups with universal factor graphs, 2021. URL: http://arxiv.org/abs/2111.09256.
  2. 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. URL: https://doi.org/10.1145/278298.278306.
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, January 1998. URL: https://doi.org/10.1145/273865.273901.
  4. Per Austrin, Jonah Brown-Cohen, and Johan Håstad. Optimal inapproximability with universal factor graphs. In Proc. 51st Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 434-453, 2021. URL: https://doi.org/10.1137/1.9781611976465.27.
  5. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-sat is NP-hard. SIAM Journal on Computing, 46(5):1554-1573, 2017. URL: https://doi.org/10.1137/15M1006507.
  6. Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-lin over non-abelian groups. In Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1615-1628, 2021. URL: https://doi.org/10.1145/3406325.3451003.
  7. Jakub Bulín, Andrei A. Krokhin, and Jakub Oprsal. Algebraic approach to promise constraint satisfaction. In Proc. 51st ACM Symp. on Theory of Computing (STOC), pages 602-613, 2019. URL: https://doi.org/10.1145/3313276.3316300.
  8. Siu On Chan. Approximation resistance from pairwise-independent subgroups. J. ACM, 63(3):27:1-27:32, 2016. URL: https://doi.org/10.1145/2873054.
  9. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. URL: https://doi.org/10.1145/1236457.1236459.
  10. Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups. Theor. Comput. Sci., 312(1):17-45, 2004. URL: https://doi.org/10.1016/S0304-3975(03)00401-8.
  11. Uriel Feige. Relations between average case complexity and approximation complexity. In Proc. 34th Annual ACM Symposium on Theory of Computing (STOC), pages 534-543, 2002. URL: https://doi.org/10.1145/509907.509985.
  12. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268-292, March 1996. URL: https://doi.org/10.1145/226643.226652.
  13. Uriel Feige and Shlomo Jozeph. Universal factor graphs. In Proc. 39th International Colloq. of Automata, Languages and Programming (ICALP), Part I, volume 7391 of LNCS, pages 339-350. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_29.
  14. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: https://doi.org/10.1145/502090.502098.
  15. Shlomo Jozeph. Universal factor graphs for every NP-hard boolean csp. In Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX/RANDOM), volume 28 of LIPIcs, pages 274-283, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.274.
  16. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any csp. In Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 132-145, 2017. URL: https://doi.org/10.1145/3055399.3055485.
  17. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM Journal on Computing, 40(6):1871-1891, 2011. URL: https://doi.org/10.1137/080734042.
  18. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. URL: https://doi.org/10.1137/S0097539795280895.
  19. Jean-Pierre Serre. Linear representations of finite groups. Springer, 1977. URL: https://doi.org/10.1007/978-1-4684-9458-7_1.
  20. Audrey Terras. Fourier Analysis on Finite Groups and Applications. London Mathematical Society Student Texts. Cambridge University Press, 1999. URL: https://doi.org/10.1017/CBO9780511626265.
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