IEICE TRANSACTIONS on Information
Estimating the Gowers Norm of Modulo Functions over Prime Fields
Summary :
We show a technique for estimating an upper bound of the Gowers norm of modulo functions over prime fields, which reduces the estimation to the greatest common divisor of some periodic sequences. This estimation provides inapproximability of the modulo functions by low-degree polynomials over prime fields, which is a generalization of Viola and Wigderson's result in the case of the binary field.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.3 pp.755-762
- Publication Date
- 2012/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.755
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Akinori KAWACHI, Hidetoki TANAKA, Osamu WATANABE, "Estimating the Gowers Norm of Modulo Functions over Prime Fields" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 3, pp. 755-762, March 2012, doi: 10.1587/transinf.E95.D.755.
Abstract: We show a technique for estimating an upper bound of the Gowers norm of modulo functions over prime fields, which reduces the estimation to the greatest common divisor of some periodic sequences. This estimation provides inapproximability of the modulo functions by low-degree polynomials over prime fields, which is a generalization of Viola and Wigderson's result in the case of the binary field.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.755/_p
Copy
@ARTICLE{e95-d_3_755,
author={Akinori KAWACHI, Hidetoki TANAKA, Osamu WATANABE, },
journal={IEICE TRANSACTIONS on Information},
title={Estimating the Gowers Norm of Modulo Functions over Prime Fields},
year={2012},
volume={E95-D},
number={3},
pages={755-762},
abstract={We show a technique for estimating an upper bound of the Gowers norm of modulo functions over prime fields, which reduces the estimation to the greatest common divisor of some periodic sequences. This estimation provides inapproximability of the modulo functions by low-degree polynomials over prime fields, which is a generalization of Viola and Wigderson's result in the case of the binary field.},
keywords={},
doi={10.1587/transinf.E95.D.755},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Estimating the Gowers Norm of Modulo Functions over Prime Fields
T2 - IEICE TRANSACTIONS on Information
SP - 755
EP - 762
AU - Akinori KAWACHI
AU - Hidetoki TANAKA
AU - Osamu WATANABE
PY - 2012
DO - 10.1587/transinf.E95.D.755
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2012
AB - We show a technique for estimating an upper bound of the Gowers norm of modulo functions over prime fields, which reduces the estimation to the greatest common divisor of some periodic sequences. This estimation provides inapproximability of the modulo functions by low-degree polynomials over prime fields, which is a generalization of Viola and Wigderson's result in the case of the binary field.
ER -
English
