Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs
复制标题
在 2 色超图中寻找独立集和可满足 CSP 的难度
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Rishi Saket
中科院分区：
文献类型：
--
作者：
Rishi Saket
这项工作重新审视了Hastad [1]，Guruswami等人[2]，Holmerin [3]和Guruswami [4]在2色4-均匀的超图中，我们提供了更简单，更有效的PCP验证器，以证明以下改进的硬度结果：假设NP⊈dime（no（log og log n））对于N-Vertex 2色4-均匀的超图，算法可以找到一组独立的N/（log n）C顶点，对于某些常数C> 0。 1个可令人满意的max -e3（log n）c sat sat sat sat sat sat sat sat sat sat> 0的子句的比例1，对于任何固定的k≥4，都没有多项式时间算法可以找到分区分开（1--1--1- 2-k + 1） + 1/（log n）c的分数对于某个常数c> 0，可满足的最大ek-set拆分实例的k-set。我们独立设置在2色4-均匀的4-均匀超图中的硬度因子比Guruswami Et的先前结果的指数改进Al。[2]和Holmerin [3]。在[1]，[3]和[4]中提供的边界。除了傅立叶分析中的标准技术外，对于第一个提到的结果，我们使用Markov链的混合估计值，基于Mossel等人[5]的一般产品空间的均匀反向超收缩率。 [6]。
This work revisits the PCP Verifiers used in the works of Hastad [1], Guruswami et al. [2], Holmerin [3] and Guruswami [4] for satisfiable MAX-E3-SAT and MAX-EkSET-SPLITTING, and independent set in 2-colorable 4-uniform hypergraphs. We provide simpler and more efficient PCP Verifiers to prove the following improved hardness results: Assuming that NP ⊈ DTIME(NO(log log N)), . There is no polynomial time algorithm that, given an n-vertex 2-colorable 4-uniform hypergraph, finds an independent set of n/(log n)c vertices, for some constant c > 0. . There is no polynomial time algorithm that satisfies 7/8 + 1 fraction of the clauses of a satisfiable MAX-E3(log n)c SAT instance of size n, for some constant c > 0. For any fixed k ≥ 4, there is no polynomial time algorithm that finds a partition splitting (1 - 2-k+1) + 1/(log n)c fraction of the k-sets of a satisfiable MAX-Ek-SET-SPLITTING instance of size n, for some constant c > 0. Our hardness factor for independent set in 2-colorable 4-uniform hypergraphs is an exponential improvement over the previous results of Guruswami et al. [2] and Holmerin [3]. Similarly, our inapproximability of (log n)-c beyond the random assignment threshold for MAX-E3-SAT and MAX-Ek-SETSPLITTING is an exponential improvement over the previous bounds proved in [1], [3] and [4]. The PCP Verifiers used in our results avoid the use of a variable bias parameter used in previous works, which leads to the improved hardness thresholds in addition to simplifying the analysis substantially. Apart from standard techniques from Fourier Analysis, for the first mentioned result we use a mixing estimate of Markov Chains based on uniform reverse hypercontractivity over general product spaces from the work of Mossel et al. [5], [6].