Document Open Access Logo

On the Degree of Boolean Functions as Polynomials over ℤ_m

Authors Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.100.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Xiaoming Sun
  • Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
Yuan Sun
  • Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
Jiaheng Wang
  • School of Electronics Engineering and Computer Science, Peking University, Beijing, China
Kewen Wu
  • School of Electronics Engineering and Computer Science, Peking University, Beijing, China
Zhiyu Xia
  • Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
Yufan Zheng
  • Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China

Funding

This work was supported in part by the National Natural Science Foundation of China Grants No. 61832003, 61761136014, the 973 Program of China Grant No. 2016YFB1000201, the Strategic Priority Research Program of Chinese Academy of Sciences Grant No. XDB28000000, and K. C. Wong Education Foundation.

Acknowledgements

We thank Noga Alon and Xiaoxu Guo for pointing us to relevant references [Noga Alon and Richard Beigel, 2001; Fine and Wilf, 1965]. We also appreciate anonymous reviewers' careful feedback and constructive advice.

Cite As Get BibTex

Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, and Yufan Zheng. On the Degree of Boolean Functions as Polynomials over ℤ_m. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.100

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)}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Boolean function
  • polynomial
  • modular degree
  • Ramsey theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon and Richard Beigel. Lower bounds for approximations by low degree polynomials over ℤ_m. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 184-187. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/CCC.2001.933885.
  2. Roger C Baker, Glyn Harman, and János Pintz. The difference between consecutive primes, ii. Proceedings of the London Mathematical Society, 83(3):532-562, 2001. Google Scholar
  3. David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing boolean functions as polynomials modulo composite numbers. Computational Complexity, 4:367-382, 1994. URL: https://doi.org/10.1007/BF01263424.
  4. Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 120-130. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/CCC.2001.933879.
  5. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  6. John Chiarelli, Pooya Hatami, and Michael E. Saks. An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function. Combinatorica, 40(1):237-244, 2020. URL: https://doi.org/10.1007/s00493-019-4136-7.
  7. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM J. Comput., 41(6):1694-1703, 2012. URL: https://doi.org/10.1137/090772721.
  8. P. Erdős and R. Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London Mathematical Society, s3-2(1):417-439, 1952. Google Scholar
  9. Nathan J Fine and Herbert S Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109-114, 1965. Google Scholar
  10. Parikshit Gopalan. Computing with polynomials over composites. PhD thesis, Georgia Institute of Technology, 2006. Google Scholar
  11. Parikshit Gopalan. Constructing ramsey graphs from boolean function representations. Combinatorica, 34(2):173-206, 2014. URL: https://doi.org/10.1007/s00493-014-2367-1.
  12. Parikshit Gopalan, Shachar Lovett, and Amir Shpilka. On the complexity of boolean functions in different characteristics. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 173-183. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/CCC.2009.14.
  13. Vince Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica, 20(1):71-86, 2000. URL: https://doi.org/10.1007/s004930070032.
  14. Vince Grolmusz. Constructing set systems with prescribed intersection sizes. J. Algorithms, 44(2):321-337, 2002. URL: https://doi.org/10.1016/S0196-6774(02)00204-3.
  15. D. J. Katz. p-adic valuation of weights in abelian codes over ℤ_p^d. IEEE Trans. Inf. Theory, 51(1):281-305, 2005. URL: https://doi.org/10.1109/TIT.2004.839495.
  16. Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2^õ(n^1/3). J. Comput. Syst. Sci., 68(2):303-318, 2004. URL: https://doi.org/10.1016/j.jcss.2003.07.007.
  17. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331-1348, 1993. URL: https://doi.org/10.1137/0222080.
  18. Chia-Jung Lee, Satyanarayana V. Lokam, Shi-Chun Tsai, and Ming-Chuan Yang. Restrictions of nondegenerate boolean functions and degree lower bounds over different rings. In IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, June 14-19, 2015, pages 501-505. IEEE, 2015. URL: https://doi.org/10.1109/ISIT.2015.7282505.
  19. Qian Li and Xiaoming Sun. On the modulo degree complexity of boolean functions. Theor. Comput. Sci., 818:32-40, 2020. URL: https://doi.org/10.1016/j.tcs.2018.04.049.
  20. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. J. ACM, 40(3):607-620, 1993. URL: https://doi.org/10.1145/174130.174138.
  21. Xiaoyu Liu. An equivalence of ward’s bound and its application. Des. Codes Cryptogr., 58(1):1-9, 2011. URL: https://doi.org/10.1007/s10623-010-9380-1.
  22. Kurt Mahler. An interpolation series for continuous functions of a p-adic variable. J. reine angew. Math, 199:23-34, 1958. Google Scholar
  23. Marvin Minsky and Seymour Papert. An introduction to computational geometry. Cambridge tiass., HIT, 1969. Google Scholar
  24. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  25. Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning juntas. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 206-212. ACM, 2003. URL: https://doi.org/10.1145/780542.780574.
  26. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. URL: https://doi.org/10.1007/BF01263419.
  27. Alexander A Razborov. Lower bounds for the size of circuits of bounded depth with basis ∧,⊕. Math. notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  28. Alexander A Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003. Google Scholar
  29. Alexander A. Sherstov. Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59-93, 2008. Google Scholar
  30. Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput., 41(5):1122-1165, 2012. URL: https://doi.org/10.1137/110842661.
  31. Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5):444-460, 2009. URL: http://www.rintonpress.com/xxqic9/qic-9-56/0444-0460.pdf.
  32. Hans Ulrich Simon. A tight Ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions. Information and Control, 55(1-3):102-106, 1982. URL: https://doi.org/10.1016/S0019-9958(82)90477-6.
  33. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77-82. ACM, 1987. URL: https://doi.org/10.1145/28395.28404.
  34. Joachim von zur Gathen and James R. Roche. Polynomials with two values. Combinatorica, 17(3):345-362, 1997. URL: https://doi.org/10.1007/BF01215917.
  35. Jake Wellens. A tighter bound on the number of relevant variables in a bounded degree boolean function. CoRR, abs/1903.08214, 2019. URL: http://arxiv.org/abs/1903.08214.
  36. Richard M. Wilson. A lemma on polynomials modulo p^m and applications to coding theory. Discrete Mathematics, 306(23):3154-3165, 2006. URL: https://doi.org/10.1016/j.disc.2004.10.030.
  37. Bahattin Yildiz. Weights modulo p^e of linear codes over rings. Des. Codes Cryptogr., 43(2-3):147-165, 2007. URL: https://doi.org/10.1007/s10623-007-9076-3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact