HARDNESS OF APPROXIMATING THE CLOSEST VECTOR PROBLEM WITH PRE-PROCESSING

Mikhail Alekhnovich; Guy Kindler; SUBHASH A.  KHOT; NISHEETH K. VISHNOI

首页> 外文期刊>Computational complexity >HARDNESS OF APPROXIMATING THE CLOSEST VECTOR PROBLEM WITH PRE-PROCESSING

【24h】

HARDNESS OF APPROXIMATING THE CLOSEST VECTOR PROBLEM WITH PRE-PROCESSING

机译：通过预处理来解决最近向量问题的难度

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We show that the pre-processing versions of the closest vector problem and the nearest codeword problem are NP-hard to approximate within any constant factor.

机译：我们表明，最接近的向量问题和最接近的码字问题的预处理版本在任何恒定因子内都是NP难近似的。

著录项

来源
《Computational complexity》 |2011年第4期|p.741-753|共13页
作者
Mikhail Alekhnovich; Guy Kindler; SUBHASH A. KHOT; NISHEETH K. VISHNOI;
展开▼
作者单位

Institute for Advanced Study, Princeton, NJ 08540, USA;

School of Computer Science and Engineering, The Hebrew University of Jerusalem, Ross Building, Givat Ram Campus, 91904 Jerusalem, Israel;

Computer Science Department, Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA;

Microsoft Research India, 19G/36 2nd Main Sadashivnagar, Bangalore 560080. India;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
lattices; codes; approximation; hardness; preprocessing;

机译：格子代码;近似;硬度;预处理;

相似文献

外文文献
中文文献
专利

1. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors [J] . O. Goldreich, D. Micciancio, S. Safra Information Processing Letters . 1999,第2期

机译：近似最短晶格矢量并不比近似最接近晶格矢量难
2. Approximating shortest lattice vectors is not harder than approximating closest lattice [J] . Oded Goldreich, Daniele Micciancio, Shmuel Safra, Electronic Colloquium on Computational Complexity . 1999,第131期

机译：逼近最短晶格向量并不比逼近最接近晶格难
3. Solving Closest Vector Instances Using an Approximate Shortest Independent Vectors Oracle [J] . Cheng-Liang Tian, Wei Wei, Dong-Dai Lin 计算机科学技术学报（英文版） . 2015,第006期

机译：使用近似最短的独立向量来求解最近的向量实例
4. Hardness of approximating the closest vector problem with pre-processing [C] . Alekhnovich M., Khot S.A., Kindler G., Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on . 2005

机译：用预处理近似最接近向量问题的难度
5. Algorithms For The Closest And Shortest Vector Problems On General Lattices [D] . Voulgaris, Panagiotis 2011

机译：一般格上最短和最短向量问题的算法
6. Broadband vectorial ultrathin optics with experimental efficiency up to 99 in the visible region via universal approximators [O] . F. Getman, M. Makarenko, A. Burguete-Lopez, 2021

机译：宽带矢量超光学通过通用近似器的可见区域具有高达99％的实验效率
7. Hardness of approximating the closest vector problem with pre-processing [O] . Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, 2005

机译：用预处理近似最接近向量问题的难度
8. Fast query-optimized kernel machine classification via incremental approximate nearest support vectors [R] . DeCoste, D., Mazzoni, D. 2003

机译：通过增量近似最近支持向量快速查询优化的内核机器分类

HARDNESS OF APPROXIMATING THE CLOSEST VECTOR PROBLEM WITH PRE-PROCESSING

摘要

著录项

相似文献

相关主题

期刊订阅