Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.100
URN: urn:nbn:de:0030-drops-125070
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12507/
Sun, Xiaoming ; Sun, Yuan ; Wang, Jiaheng ; Wu, Kewen ; Xia, Zhiyu ; Zheng, Yufan
On the Degree of Boolean Functions as Polynomials over ℤ_m
| pdf-format: |
|
Abstract
Polynomial representations of Boolean functions over various rings such as ℤ and ℤ_m have been studied since Minsky and Papert (1969). From then on, they have been employed in a large variety of areas including communication complexity, circuit complexity, learning theory, coding theory and so on. For any integer m ≥ 2, each Boolean function has a unique multilinear polynomial representation over ring ℤ_m. The degree of such polynomial is called modulo-m degree, denoted as deg_m(⋅).In this paper, we investigate the lower bound of modulo-m degree of Boolean functions. When m = p^k (k ≥ 1) for some prime p, we give a tight lower bound deg_m(f) ≥ k(p-1) for any non-degenerate function f:{0,1}ⁿ → {0,1}, provided that n is sufficient large. When m contains two different prime factors p and q, we give a nearly optimal lower bound for any symmetric function f:{0,1}ⁿ → {0,1} that deg_m(f) ≥ n/{2+1/(p-1)+1/(q-1)}.
BibTeX - Entry
@InProceedings{sun_et_al:LIPIcs:2020:12507,
author = {Xiaoming Sun and Yuan Sun and Jiaheng Wang and Kewen Wu and Zhiyu Xia and Yufan Zheng},
title = {{On the Degree of Boolean Functions as Polynomials over ℤ_m}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {100:1--100:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12507},
URN = {urn:nbn:de:0030-drops-125070},
doi = {10.4230/LIPIcs.ICALP.2020.100},
annote = {Keywords: Boolean function, polynomial, modular degree, Ramsey theory}
}
| Keywords: | Boolean function, polynomial, modular degree, Ramsey theory | |
| Seminar: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 29.06.2020 |
