| Presentation | 2010-12-03 Hard Functions for Low-degree Polynomials over Prime Fields(Extended Abstract) Andrej BOGDANOV, Akinori KAWACHI, Hidetoki TANAKA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | low-degree polynomial / hardness amplification / Gowers norm |
| Paper # | COMP2010-39 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/11/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Hard Functions for Low-degree Polynomials over Prime Fields(Extended Abstract) |
| Sub Title (in English) | |
| Keyword(1) | low-degree polynomial |
| Keyword(2) | hardness amplification |
| Keyword(3) | Gowers norm |
| 1st Author's Name | Andrej BOGDANOV |
| 1st Author's Affiliation | Department of Computer Science and Engineering, the Chinese University of Hong Kong() |
| 2nd Author's Name | Akinori KAWACHI |
| 2nd Author's Affiliation | Department of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| 3rd Author's Name | Hidetoki TANAKA |
| 3rd Author's Affiliation | Department of Mathematical and Computing Sciences, Tokyo Institute of Technology |
| Date | 2010-12-03 |
| Paper # | COMP2010-39 |
| Volume (vol) | vol.110 |
| Number (no) | 325 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |