抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ewcommand NPNPwcommand GapSVPWeは,(近似的,決定的)最短ベクトル問題がランダム化低減の下でNP困難であるという簡単な証明を与える。特に,任意のp≧1および任意の一定のγ<2 ̄1/pに対して,l_pノルム(γ-GapSVP_p)におけるγ近似問題は,NP⊆RPがなければRPではそうではないことを示した。著者らの証明は,Ajtai(STOC1998)が先駆するアプローチに従い,局所的に緻密な格子を用いてγ-GapSVP_pの硬度を示すため,Micciancio(FOCS 1998とSICOMP 2000)によって強化された。著者らは,適切なパラメータを持つReed-Solomon符号に「Construction A」を適用することにより,そのような格子を単純に構築し,Craig格子の文脈で最初に使用された基本議論により,それらの局所密度を証明した。p<∞のGapSVP_pに対する全ての既知のNP-硬度の結果,著者らの減少はランダム性を用いる。確かに,決定論的減少によるNP-硬度を証明することは周知の未解決問題である。この目的のために,著者らはさらに,著者らの減少を乱すための潜在的方向と関連する課題について議論する。特に,局所密度構築の密接な決定論的アナログが,GuruswamiとRudra(STOC 2005とIEEE Trans.Inf)の最先端の明示的なReed-Solomonリスト復号下限で改善することを示した。2006年。独立した関心の関連する寄与として,著者らはまた,Minkowskiの境界のO(√logn)因子内の距離に対して,n次元”Construction A Reed-Solomon格子”(著者らの硬度証明で用いられたものとは異なるパラメータを有する)の復号化のための多項式時間アルゴリズムを与えた。これは,MookとPeikert(IEEE Trans.Inf)により,Minkowskiの境界近傍の復号化の最良の既知の距離に漸近的に整合する。理論2022は,その作業がいくらか単純な構築と解析に関して構築する。【JST・京大機械翻訳】
