標題: | Representing Symmetric Boolean Functions with Polynomial over Composite Moduli |
作者: | Tsai, Shi-Chun Yang, Mng-Chuan 資訊工程學系 Department of Computer Science |
關鍵字: | degree lower bound;polynomial method;Boolean function complexity;ACC(0)[m] circuits;modulo degree complexity;multivariate polynomial;Mobius inversion;binomial coefficient |
公開日期: | 1-一月-2018 |
摘要: | Polynomial degree is an important measure for studying the computational complexity of Boolean function. A polynomial P is an element of Z(m)[x] is a generalized representation off over Z(m) if for all x, y is an element of{0, 1}(n); f(x)not equal f(y)double right arrow P(x)not equal P(y)(mod m). Denote the minimum degree as deg(m)(ge)(f), and deg(m)(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 m(1) and m(2) be relatively prime numbers and have s and t distinct prime factors respectively. Then we have m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(f))(t)> n. A polynomial Q is an element of Z(m)[x] is a one-sided representation off over Z(m) if for all xe {0, 1}(n); f(x)=0 double left right arrow Q(x) 0(mod m). Denote the minimum degree among these Q as deg(m)(os) (f). Note that Q(x) can be non-symmetric. Then with the same conditions as above, at least one of m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(f))(t)> n and m(1)m(2) (deg(m1)(sym,ge)(f))(s) (deg(m2)(sym1,ge)(-f))(t)> n is true. |
URI: | http://dx.doi.org/10.6688/JISE.2018.34.1.12 http://hdl.handle.net/11536/144421 |
ISSN: | 1016-2364 |
DOI: | 10.6688/JISE.2018.34.1.12 |
期刊: | JOURNAL OF INFORMATION SCIENCE AND ENGINEERING |
Volume: | 34 |
起始頁: | 193 |
結束頁: | 203 |
顯示於類別: | 期刊論文 |