We study approximation hardness and satisfiability of bounded
occurrence uniform instances of SAT. Among other things, we prove
the inapproximability for SAT instances in which every clause has
exactly 3 literals and each variable occurs exactly 4 times,
and display an explicit ... more >>>

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>