DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.38

Optimal Inapproximability of Promise Equations over Finite Groups

Authors: Silvia Butti, Alberto Larrauri, and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

A celebrated result of Håstad established that, for any constant ε > 0, it is NP-hard to find an assignment satisfying a (1/|G|+ε)-fraction of the constraints of a given 3-LIN instance over an Abelian group G even if one is promised that an assignment satisfying a (1-ε)-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.

Cite as

Silvia Butti, Alberto Larrauri, and Stanislav Živný. Optimal Inapproximability of Promise Equations over Finite Groups. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{butti_et_al:LIPIcs.ICALP.2025.38,
  author =	{Butti, Silvia and Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Optimal Inapproximability of Promise Equations over Finite Groups}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.38},
  URN =		{urn:nbn:de:0030-drops-234150},
  doi =		{10.4230/LIPIcs.ICALP.2025.38},
  annote =	{Keywords: promise constraint satisfaction, approximation, linear equations}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2024.146

Solving Promise Equations over Monoids and Groups

Authors: Alberto Larrauri and Stanislav Živný

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.

Cite as

Alberto Larrauri and Stanislav Živný. Solving Promise Equations over Monoids and Groups. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 146:1-146:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{larrauri_et_al:LIPIcs.ICALP.2024.146,
  author =	{Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Solving Promise Equations over Monoids and Groups}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{146:1--146:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.146},
  URN =		{urn:nbn:de:0030-drops-202893},
  doi =		{10.4230/LIPIcs.ICALP.2024.146},
  annote =	{Keywords: constraint satisfaction, promise constraint satisfaction, equations, minions}
}

Search Results

Documents authored by Larrauri, Alberto

Optimal Inapproximability of Promise Equations over Finite Groups

Abstract

Cite as

Solving Promise Equations over Monoids and Groups

Abstract

Cite as

Thanks for your feedback!

Could not send message