文献

J-GLOBAL ID：201702277002234162   整理番号：17A1774664

CVPの定量的困難性について【Powered by NICT】

On the Quantitative Hardness of CVP

著者 (3件)： Bennett Huck ,  Golovnev Alexander ,  Stephens-Davidowitz Noah
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： FOCS  ページ： 13-24  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 奇数整数p≧1(および∞)に対して,≧0は強い指数時間仮説(SETH)が失敗しない限りランクn格子上のlpノルム(CVP_p)における最近接ベクトル問題が一定の2(1 ≧)n時間で解くことができないことを示した。は,この結果を拡張p≧1のほとんどすべての値に,整数を含まない。CVP_2(すなわち,EuclidノルムにおけるCVP)の重要な特殊な場合の定量的時間計算量,2′{n+O(n)}-時間アルゴリズムが知られているを沈降に近いtantalizinglyものである。特に,筆者らの結果は,n→∞で2に近づくことを任意のp(n)≠2に適用した。もSVP_∞の類似SETH硬度結果を示した;いわゆるギャップETH仮定の下でいくつかの定数倍の範囲内でCVP_pの近似の困難さと他の硬度は,1≦pのCVP_pとCVPP_p結果Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： ベクトル ,  アルゴリズム ,  *ノルム
準シソーラス用語： 時間計算量 , 【Automatic Indexing@JST】

分類 (4件)： 分析機器  (CC02020S) ,  電極過程  (CB07040U) ,  計算理論  (JB02000A) ,  ビタミンC  (EB07040W)

タイトルに関連する用語 (3件)： CVP ,  定量 ,  困難性