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