kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimal Inapproximability with Universal Factor Graphs
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
Google DeepMind, 6 Handyside St, London NIC 4UZ, England.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Algebra, Combinatorics and Topology.ORCID iD: 0000-0002-5379-345X
2025 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 21, no 3, p. 1-39, article id 32Article in journal (Refereed) Published
Abstract [en]

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: (1) Optimal inapproximability for Max-3-Lin and Max-3-Sat (H & aring;stad, J. ACM 2001). (2) Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). (3) Hardness of the "(2 + epsilon)-Sat" problem and other Promise CSPs (Austrin et al., SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call "functional folding".

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2025. Vol. 21, no 3, p. 1-39, article id 32
Keywords [en]
hardness of approximation, factor graphs
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-373079DOI: 10.1145/3631119ISI: 001543243600003Scopus ID: 2-s2.0-105012362068OAI: oai:DiVA.org:kth-373079DiVA, id: diva2:2015063
Note

QC 20251120

Available from: 2025-11-20 Created: 2025-11-20 Last updated: 2025-11-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Austrin, PerHåstad, Johan

Search in DiVA

By author/editor
Austrin, PerHåstad, Johan
By organisation
Theoretical Computer Science, TCSAlgebra, Combinatorics and Topology
In the same journal
ACM Transactions on Algorithms
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 29 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf