2026-07-26T02:16:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12507 2024-03-06T10:50:19Z ddc:004 open_access

On the Degree of Boolean Functions as Polynomials over ℤ_m Sun, Xiaoming Sun, Yuan Wang, Jiaheng Wu, Kewen Xia, Zhiyu Zheng, Yufan Boolean function polynomial modular degree Ramsey theory 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)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaoming Sun and Yuan Sun and Jiaheng Wang and Kewen Wu and Zhiyu Xia and Yufan Zheng 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.100 urn:nbn:de:0030-drops-125070 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.100 eng https://creativecommons.org/licenses/by/3.0/legalcode