检索结果-内蒙古大学图书馆

The Projection Games Conjecture and the hardness of approximation of super-SAT and related problems

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 186-201页

作者： Mukhopadhyay, Priyanka Univ Waterloo Inst Quantum Comp 200 Univ Ave West Waterloo ON N2L 3G1 Canada Univ Waterloo Dept Combinator & Optimizat 200 Univ Ave West Waterloo ON N2L 3G1 Canada

The Super-SAT (SSAT) problem was introduced in [1,2] to prove the NP-hardness of approximation of two popular lattice problems -Shortest Vector problem and Closest Vector problem. SSAT is conjectured to be NP-hard to approximate to within a factor of n(c) (c is positive constant, n is the size of the SSAT instance). In this paper we prove this conjecture assuming the Projection Games Conjecture (PGC) [3]. This implies hardness of approximation of these lattice problems within polynomial factors, assuming PGC. We also reduce SSAT to the nearest codeword problem and Learning Halfspace problem [4]. This proves that both these problems are NP-hard to approximate within a factor of N-c'/ log log n (c' is positive constant, N is the size of the instances of the respective problems). Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Projection Games Conjecture Inapproximability Shortest Vector problem Closest Vector problem Learning Halfspace problem nearest codeword problem

来源：评论

学校读者我要写书评

暂无评论

2^log1-ε ⁿ Hardness for the Closest Vector problem with Preprocessing 12

2log1-ε n Hardness for the Clo...

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Khot, Subhash A. Popat, Preyas Vishnoi, Nisheeth K. NYU New York NY 10003 USA Microsoft Res Bangalore Karnataka India

ISBN: (纸本)9781450312455

We prove that for an arbitrarily small constant epsilon > 0;assuming NP not subset of DTIME(2(logO(1/epsilon) n)), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2(log1-epsilon n) : This improves upon the previous hardness factor of (log n)delta for some delta > 0 due to [AKKV05].

关键词： Lattices Closest Vector problem nearest codeword problem Hardness of Approximation PCP

来源：评论

学校读者我要写书评

暂无评论

Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization problems

Linear Time Approximation Schemes for the Gale-Berlekamp Gam...

引用

41st Annual ACM Symposium on Theory of Computing

作者： Karpinski, Marek Schudy, Warren Univ Bonn Dept Comp Sci D-5300 Bonn Germany

ISBN: (纸本)9781605586137

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it. to a wider class of dense fragile minimization problems including the nearest codeword problem (NCP) and Unique Games problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. As another application of our method we give the first. linear time approximation schemes for correlation clustering with a fixed number of Clusters and its hierarchical generalization. Our results depend on a new technique for dealing with small objective function values of optimization problems and could be of independent interest.

关键词： Approximation Algorithms Correlation and Hierarchical Clustering Dense Instances Gale-Berlekamp Game Linear Time Approximation Schemes Minimum Constraint Satisfaction nearest codeword problem

来源：评论

学校读者我要写书评

暂无评论

The inapproximability of lattice and coding problems with preprocessing

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2004年第1期69卷 45-67页

作者： Feige, U Micciancio, D Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Weizmann Inst Sci IL-76100 Rehovot Israel

We prove that the closest vector problem with preprocessing (CVPP) is NP-hardto approximate within any factor less than (5/3)~(1/2). More specifically, we show that thereexists a reduction from an NP-hard problem to the approximate closest vector problem such that thelattice depends only on the size of the original problem, and the specific instance is encodedsolely in the target vector. It follows that there are lattices for which the closest vector problemcannot be approximated within factors γ<(5/3)~(1/2) in polynomial time, no matter how the latticeis represented, unless NP is equal to P (or NP is contained in P/poly, in case of nonuniformsequences of lattices). The result easily extends to any l_p norm, for p≥ 1, showing that CVPP inthe l_p norm is hard to approximate within any factor γ < p (5/3)~(1/p). As an intermediate step,we establish analogous results for the nearest codeword problem with preprocessing (NCPP), provingthat for any finite field GF(q), NCPP over GF(q) is NP-hard to approximate within any factor lessthan 5/3.

关键词： point lattices coding theory closest vector problem nearest codeword problem preprocessing computational complexity NP-hardness approximation problems

来源：评论

学校读者我要写书评

暂无评论

The inapproximability of lattice and coding problems with preprocessing

The inapproximability of lattice and coding problems with pr...

引用

17th IEEE Annual Conference on Computational Complexity

作者： Feige, U Micciancio, D Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Weizmann Inst Sci IL-76100 Rehovot Israel

ISBN: (纸本)0769514685

We prove that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate within any factor less than √5/3. More specifically, we show that there exists a reduction from an NP-hard problem to the approximate closest vector problem such that the lattice depends only on the size of the original problem, and the specific instance is encoded solely in the target vector. It follows that there are lattices for which the closest vector problem cannot be approximated within factors γ<√5/3 in polynomial time, no matter how the lattice is represented, unless NP is equal to P (or NP is contained in P/poly, in case of nonuniform sequences of lattices). The result easily extends to any ℓ_p norm, for p≥1, showing that CVPP in the ℓ_p norm is hard to approximate within any factor γnearest codeword problem with preprocessing (NCPP), proving that for any finite field GF(q),NCPP over GF(q) is NP-hard to approximate within any factor less than 5/3. © 2004 Published by Elsevier Inc.

关键词： point lattices coding theory closest vector problem nearest codeword problem preprocessing computational complexity NP-hardness approximation problems

来源：评论

学校读者我要写书评

暂无评论

Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

引用

RANDOM STRUCTURES & ALGORITHMS 2003年第1期23卷 73-91页

作者： Bazgan, C de la Vega, WF Karpinski, M Univ Paris 11 CNRS LRI F-91405 Orsay France Univ Paris 09 LAMSADE F-75775 Paris France Univ Bonn Dept Comp Sci D-53117 Bonn Germany

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT-formulas, and linear equations mod 2, Ek-LIN2, do have PTASs for any k. The MIN-Ek-LIN2 problems are equivalent to the k-ary versions of the nearest codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k-uniform hypergraphs which could be of independent interest. (C) 2003 Wiley Periodicals, Inc.

关键词： approximation algorithms approximation ratios polynomial time approximation schemes minimum constraint satisfaction nearest codeword problem dense instances hypergraph sampling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：