Assuming 3-SAT formulas are hard to refute
on average, Feige showed some approximation hardness
results for several problems like min bisection, dense
$k$-subgraph, max bipartite clique and the 2-catalog segmentation
problem. We show a similar result for
max bipartite clique, but under the assumption, 4-SAT formulas
are hard to refute on average. As falsity of the 4-SAT
assumption implies falsity of the 3-SAT assumption it seems that
our assumption is weaker than that of Feige.