Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JONAH BROWN-COHEN:
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

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




ISSN 1433-8092 | Imprint