Optimal inapproximability with universal factor graphs

DOI10.1145/3631119MaRDI QIDQ6922350zbMATH OpenFDO

Authors Per Austrin, Jonah Brown-Cohen, Johan Hastad

Publication date 1 October 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3631119

zbMATH Keywords

factor graphshardness of approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• (2+)-Sat is NP-hard
• A Parallel Repetition Theorem
• Algebraic approach to promise constraint satisfaction
• Approximation Resistance from Pairwise-Independent Subgroups
• Approximation resistance on satisfiable instances for predicates with few accepting inputs
• Balanced max 2-sat might not be the hardest
• Candidate one-way functions based on expander graphs
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Gadgets, Approximation, and Linear Programming
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• On the NP-hardness of MAX-Not-2
• On the usefulness of predicates
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Some optimal inapproximability results
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Two-query PCP with subconstant error
• Universal factor graphs
• Universal factor graphs for every NP-hard Boolean CSP

Cited in

(2)

• Designated-verifier SNARGs with one group element
• Optimal inapproximability of promise equations over finite groups

This page was built for publication: Optimal inapproximability with universal factor graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6922350)