素体上多項式に対する計算困難な関数
スポンサーリンク
概要
- 論文の詳細を見る
本論文で,我々は素体上多項式に対する新たな困難線増幅を提案する.すなわち,ある関数が任意の低次多項式で近似することがやや困難であるとき,その関数の複数個の和は,低次多項式で近似することが非常に難しいことを我々は示した.この結果は,ViolaとWigdersonによって示された,二元体上の多項式に対するXOR補題の一般化である.本研究における我々の主な貢献は,素体上のGowersノルムを解析したことである.この解析中で,我々は素体上の多項式に対する一般化低次数テストである,Gowersテストについて論じた.これはAlon, Kaufman, Krivelevich, Litsyn, Ronらによって与えられた二元体上の低次数テストの,自然な一般化となっている.このGowersテストは素体上のGowersノルムを解析するための新しいテクニックである.この議論を用いて,我々は素体上の低次多項式に対する余剰関数の難しさも示した.
- 社団法人電子情報通信学会の論文
- 2010-11-26
著者
-
河内 亮周
Department of Mathematical and Computing Sciences, Tokyo Institute of Technology
-
河内 亮周
東京工業大学数理・計算科学専攻
-
河内 亮周
東京工業大学
-
BOGDANOV Andrej
香港中文大学
-
田中 秀宗
東京工業大学
関連論文
- 計算量理論における乱数(学生/教養のページ)
- Linuxディストリビューションの最適構成
- 量子計算における整数格子問題へのアプローチ(量子情報処理論文)
- NP困難問題における最悪時困難性からの平均時困難性証明への試み
- 頑健な量子状態復号とルジャンドル列の疑似乱数性
- D-1-5 量子有限オートマトンの類似性判定アルゴリズム(D-1. コンピュテーション)
- Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)
- オラクル同定問題に対する頑健な量子アルゴリズム
- ビンとボールのゲームにおける2ビン選択モデルの一般化
- 探索問題における一般的な量子オラクルの質問回数について
- A-1 3関数に対する量子クロー探索アルゴリズム(計算量・量子計算,A.アルゴリズム・基礎)
- 占有問題に対する量子アルゴリズム
- 伸長係数2のコンパクトラウティングアルゴリズム (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- Linuxディストリビューションの最適構成
- A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key(Theory of Computer Science and Its Applications)
- Multi-Bit Cryptosystems based on Lattice Problems : Extended Abstract(New Trends in Theory of Computation and Algorithm)
- Geometric Characterization of Quantum Oracle Identification(New Trends in Theory of Computation and Algorithm)
- 任意の量子一方向性関数に対するハードコア述語の一般的構成法
- Quantum Biased Oracles (特集:量子計算と量子情報)
- 定数ラウンドで復元可能な合理的秘密分散
- 計算論的安全性に基づく量子暗号
- 任意の量子一方向性関数に対するハードコア述語の一般的構成法
- 素体上多項式に対する計算困難な関数
- Gowers一様性による剰余関数と多項式の相関の評価 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- Quantum Sampling for Balanced Allocations(Foundations of Computer Science)
- Complexity-Theoretical Quantum List Decoding and Applications to Quamtum Hardcore Functions (計算理論とアルゴリズムの新展開 RIMS研究集会報告集)
- Rational Secret Sharing for Non-Simultaneous Channels (情報理論)
- GPU を用いた簡潔 trie の並列探索 (アルゴリズムと計算理論の新展開)
- リスト復号の質問計算量
- 非同時通信路における合理的秘密分散(情報セキュリティ)
- NP-解探索における質問計算量について
- A Fourier analytic approach to list-decoding for sparse random linear codes (New Trends in Theoretical Computer Science)
- Query Complexity of Witness Finding (コンピュテーション)
- NP-解探索における質問計算量について(一般)
- 計算複雑さへの招待(2) : アルゴリズムから攻める計算複雑さの下界証明(【特別企画】「計算限界解明」チュートリアル講演第2回)
- Quantum-Advised Algorithms for Biased Oracles (コンピュテーション)
- 非同時通信路における合理的秘密分散