All reports by Author Jonah Brown-Cohen:

__
TR19-151
| 5th November 2019
__

Per Austrin, Jonah Brown-Cohen, Johan Hastad#### Optimal Inapproximability with Universal Factor Graphs

Per Austrin, Jonah Brown-Cohen, Johan Hastad

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 ... more >>>