| 講演名 | 2010-12-03 素体上多項式に対する計算困難な関数 , 河内 亮周, 田中 秀宗, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文で,我々は素体上多項式に対する新たな困難線増幅を提案する.すなわち,ある関数が任意の低次多項式で近似することがやや困難であるとき,その関数の複数個の和は,低次多項式で近似することが非常に難しいことを我々は示した.この結果は,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 |
| 資料番号 | COMP2010-39 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2010/11/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 素体上多項式に対する計算困難な関数 |
| サブタイトル（和） | |
| タイトル（英） | Hard Functions for Low-degree Polynomials over Prime Fields(Extended Abstract) |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 低次多項式 / low-degree polynomial |
| キーワード(2)（和/英） | 困難性増幅 / hardness amplification |
| キーワード(3)（和/英） | Gowersノルム / Gowers norm |
| 第 1 著者 氏名（和/英） | / Andrej BOGDANOV |
| 第 1 著者 所属（和/英） | 香港中文大学 Department of Computer Science and Engineering, the Chinese University of Hong Kong |
| 第 2 著者 氏名（和/英） | 河内 亮周 / Akinori KAWACHI |
| 第 2 著者 所属（和/英） | 東京工業大学 Department of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 田中 秀宗 / Hidetoki TANAKA |
| 第 3 著者 所属（和/英） | 東京工業大学 Department of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 発表年月日 | 2010-12-03 |
| 資料番号 | COMP2010-39 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 325 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |