kth.sePublikationer KTH
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimal Inapproximability with Universal Factor Graphs
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Teoretisk datalogi, TCS.ORCID-id: 0000-0001-8217-0158
Google DeepMind, 6 Handyside St, London NIC 4UZ, England.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Algebra, kombinatorik och topologi.ORCID-id: 0000-0002-5379-345X
2025 (Engelska)Ingår i: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 21, nr 3, s. 1-39, artikel-id 32Artikel i tidskrift (Refereegranskat) 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".

Ort, förlag, år, upplaga, sidor
Association for Computing Machinery (ACM) , 2025. Vol. 21, nr 3, s. 1-39, artikel-id 32
Nyckelord [en]
hardness of approximation, factor graphs
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-373079DOI: 10.1145/3631119ISI: 001543243600003Scopus ID: 2-s2.0-105012362068OAI: oai:DiVA.org:kth-373079DiVA, id: diva2:2015063
Anmärkning

QC 20251120

Tillgänglig från: 2025-11-20 Skapad: 2025-11-20 Senast uppdaterad: 2025-11-20Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Austrin, PerHåstad, Johan

Sök vidare i DiVA

Av författaren/redaktören
Austrin, PerHåstad, Johan
Av organisationen
Teoretisk datalogi, TCSAlgebra, kombinatorik och topologi
I samma tidskrift
ACM Transactions on Algorithms
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 29 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf