| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-12-03 10:30 素体上多項式に対する計算困難な関数 Andrej Bogdanov（香港中文大）・○河内亮周・田中秀宗（東工大）  COMP2010-39 |
|
| 抄録 | （和） | 本論文で，我々は素体上多項式に対する新たな困難線増幅を提案する．すなわち，ある関数が任意の低次多項式で近似することがやや困難であるとき，その関数の複数個の和は，低次多項式で近似することが非常に難しいことを我々は示した．この結果は，Viola と Wigderson によって示された，二元体上の多項式に対する XOR 補題の一般化である．本研究における我々の主な貢献は，素体上の Gowers ノルムを解析したことである．この解析中で，我々は素体上の多項式に対する一般化低次数テストである，Gowers テストについて論じた．これはAlon，Kaufman，Krivelevich，Litsyn，Ron らによって与えられた二元体上の低次数テストの，自然な一般化となっている．この Gowers テストは素体上の Gowers ノルムを解析するための新しいテクニックである．この議論を用いて，我々は素体上の低次多項式に対する剰余関数の難しさも示した． |
| （英） | In this paper, we present a new hardness amplification for low-degree polynomials over prime fields, namely, we prove that if some function is mildly hard to approximate by any low-degree polynomials then the sum of independent copies of the function is very hard to approximate by them. This result generalizes the XOR lemma for low-degree polynomials over the binary field given by Viola and Wigderson. The main technical contribution is the analysis of the Gowers norm over prime fields. For the analysis, we discuss a generalized low-degree test, which we call the Gowers test, for polynomials over prime fields, which is a natural generalization of that over the binary field given by Alon, Kaufman, Krivelevich, Litsyn and Ron. This Gowers test provides a new technique to analyze the Gowers norm over prime fields. By using our argument, we also prove the hardness of modulo functions for low-degree polynomials over prime fields. This article is a technical report without peer-review, and the full version will be published elsewhere. | |
| キーワード | （和） | 低次多項式 / 困難性増幅 / Gowers ノルム / / / / / |
| （英） | low-degree polynomial / hardness amplification / Gowers norm / / / / / | |
| 文献情報 | 信学技報, vol. 110, no. 325, COMP2010-39, pp. 1-6, 2010年12月. | |
| 資料番号 | COMP2010-39 | |
| 発行日 | 2010-11-26 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2010-39 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-12-03 - 2010-12-03 |
| 開催地（和） | 九州工業大学 Kyutechプラザ |
| 開催地（英） | Kyutech Plaza, Kyushu Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-12-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 素体上多項式に対する計算困難な関数 |
| サブタイトル（和） | |
| タイトル（英） | Hard Functions for Low-degree Polynomials over Prime Fields (Extended Abstract) |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 低次多項式 / low-degree polynomial |
| キーワード(2)（和/英） | 困難性増幅 / hardness amplification |
| キーワード(3)（和/英） | Gowers ノルム / Gowers norm |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | Andrej Bogdanov / Andrej Bogdanov / Andrej Bogdanov |
| 第1著者 所属（和/英） | 香港中文大学 (略称： 香港中文大) the Chinese University of Hong Kong (略称： Chinese Univ. of Hong Kong) |
| 第2著者 氏名（和/英/ヨミ） | 河内 亮周 / Akinori Kawachi / カワチ アキノリ |
| 第2著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech.) |
| 第3著者 氏名（和/英/ヨミ） | 田中 秀宗 / Hidetoki Tanaka / タナカ ヒデトキ |
| 第3著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech.) |
| 講演者 | 第2著者 |
| 発表日時 | 2010-12-03 10:30:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2010-39 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.325 |
| ページ範囲 | pp.1-6 |
| ページ数 | 6 |
| 発行日 | 2010-11-26 (COMP) |
[研究会発表申込システムのトップページに戻る]