## Optimal Inapproximability with Universal Factor Graphs

by Per Austrin, Jonah Brown-Cohen, and Johan Hastad

#### Oded's comments

This natural notion of a *universal factor graph*
was suggested by Feige and Jozeph,
who showed non-optimal inapproximation results for Max-3SAT and other CSPs.
(I am not sure I like the term `factor' and would prefer use `instance-graph';
also, I regret that I forgot to call attention to their work at the time.)
Anyhow, this work shows that many of the most popular optimal inapproximability
results for CSPs, extend to the case of universal factor graphs.

#### The original abstract

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 remains 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:

- Optimal inapproximability for Max-3-Lin.
- Approximation resistance for predicates supporting pairwise independent
subgroups.
- Hardness of the ``$(2+\epsilon)$-SAT'' problem and other Promise CSPs.

The main technical tool used to establish these results is a new way of
folding the long code which we call ``functional folding''.
See ECCC TR19-151.

Back to
list of Oded's choices.