论文标题
关于低度2-CSP硬度的新猜想，对浓缩$ k $ -subgraph和其他问题的硬度有影响
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest $k$-Subgraph and Other Problems
论文作者
论文摘要
我们提出了一个关于低度$ 2 $ -CSP的硬度的新猜想，并表明近似结果的新硬度是最密集的$ k $ -subgraph和其他几个问题，包括图形分配问题以及图形交叉数量问题的变化，鉴于此猜想。猜想可以看作是在$ d $ - 至$ 1 $的猜想之间占据中间立场，并且可以通过标准技术获得$ 2 $ -CSP的硬度结果，例如平行重复以及3Sat问题的标准$ 2 $ -Prover协议。我们希望这项工作能够激发猜想引起的政权中$ 2 $ -CSP的硬度的进一步探索。我们认为，对猜想的积极分辨率将为进一步的近似证明硬度提供良好的起点。 我们工作的另一个贡献证明，从近似角度来看，我们认为的问题大致相当。这些问题中有一些在以前的工作中出现，似乎它们可能彼此相关。我们在这项工作中对这种关系进行正式关系。
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.
