  We propose a new conjecture on hardness of low-degree $2$-CSP's, and show
that new hardness of approximation results for Densest $k$-Subgraph and several
other problems, including a graph partitioning problem, and a variation of the
Graph Crossing Number problem, follow from this conjecture. The conjecture can
be viewed as occupying a middle ground between the $d$-to-$1$ conjecture, and
hardness results for $2$-CSP's that can be obtained via standard techniques,
such as Parallel Repetition combined with standard $2$-prover protocols for the
3SAT problem. We hope that this work will motivate further exploration of
hardness of $2$-CSP's in the regimes arising from the conjecture. We believe
that a positive resolution of the conjecture will provide a good starting point
for further hardness of approximation proofs.
  Another contribution of our work is proving that the problems that we
consider are roughly equivalent from the approximation perspective. Some of
these problems arose in previous work, from which it appeared that they may be
related to each other. We formalize this relationship in this work.
