It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.


See Jan Krajicek, "A note on SAT algorithms and proof complexity", 2012 I am not sure if we have any result for random unsat instances (how do you define a random unsat instance?).

Only top voted, non community-wiki answers of a minimum length are eligible