Representing symmetric boolean functions with polynomial over composite moduli

Shi-Chun Tsai, Ming Chuan Yang

Research output: Contribution to journalArticlepeer-review

Abstract

Polynomial degree is an important measure for studying the computational complexity of Boolean function. A polynomial PZm[x] is a generalized representation of f over Zm if x, y(0, 1)n; f(x)f(y)P(x)≢P(y)(mod m). Denote the minimum degree as degm ge(f), and degm sym ge(f) if the minimum is taken from symmetric polynomials. In this paper we prove new lower bounds for the symmetric Boolean functions that depend on n variables. First, let m1 and m2 be relatively prime numbers and have s and t distinct prime factors respectively. Then we have m1m2 (degm sym 1 , ge (f ))s (degm sym 2 , ge (f ))t n. A polynomial QZm[x] is a one-sided representation of f over Zm if x(0, 1)n; f(x)=0Q(x)0(mod m). Denote the minimum degree among these Q as degm os(f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of m1m2 (degm sym 1 , ge (f ))s (degm sym 2 , ge (f ))t n and m1m2 (degm sym 1 , ge (f ))s (degm sym 2 , ge (f ))t n is true.

Original languageEnglish
Pages (from-to)193-203
Number of pages11
JournalJournal of Information Science and Engineering
Volume34
Issue number1
DOIs
StatePublished - 1 Jan 2018

Keywords

  • ACC[m] circuits
  • Binomial coefficient
  • Boolean function complexity
  • Degree lower bound
  • Mobius inversion
  • Modulo degree complexity
  • Multivariate polynomial
  • Polynomial method

Fingerprint Dive into the research topics of 'Representing symmetric boolean functions with polynomial over composite moduli'. Together they form a unique fingerprint.

Cite this