TY - GEN

T1 - Restrictions of nondegenerate Boolean functions and degree lower bounds over different rings

AU - Lee, Chia Jung

AU - Lokam, Satyanarayana V.

AU - Tsai, Shi-Chun

AU - Yang, Ming Chuan

N1 - Publisher Copyright:
© 2015 IEEE.

PY - 2015/9/28

Y1 - 2015/9/28

N2 - A Boolean function f : {0, 1}n → {0, 1} is called nondegenerate if f depends on all its n variables. We show that, for any nondegenerate function f, there exists a variable xi such that at least one of the restrictions fxi=0 or fxi=1 must depend on all the remaining n - 1 variables. We also consider lower bounds on the degrees of polynomials representing a Boolean function over different rings. Let dq(f) be the degree of the (unique) polynomial over the ring ℤq exactly representing f. For distinct primes pi let m = Πri=1 peii. Then, we show that any nondegenerate symmetric Boolean function f must have m · dp1e1(f)⋯dprer(f) > n. We use the existence of nondegenerate subfunctions to prove degree lower bounds on random functions. Specifically, we show that m · dp1e1(f)⋯dprer(f) > lg n - 1 holds for almost all f when f is chosen uniformly at random from all n-variate Boolean functions. Our proof uses the second moment method to show that a random f must almost always contain a nondegenerate symmetric subfunction on at least lg n - 1 variables. It follows that an n-variate nondegenerate symmetric Boolean function can have degree o(√n) over at most one finite field and that almost all f can have degree o(√lg n) over at most one finite field.

AB - A Boolean function f : {0, 1}n → {0, 1} is called nondegenerate if f depends on all its n variables. We show that, for any nondegenerate function f, there exists a variable xi such that at least one of the restrictions fxi=0 or fxi=1 must depend on all the remaining n - 1 variables. We also consider lower bounds on the degrees of polynomials representing a Boolean function over different rings. Let dq(f) be the degree of the (unique) polynomial over the ring ℤq exactly representing f. For distinct primes pi let m = Πri=1 peii. Then, we show that any nondegenerate symmetric Boolean function f must have m · dp1e1(f)⋯dprer(f) > n. We use the existence of nondegenerate subfunctions to prove degree lower bounds on random functions. Specifically, we show that m · dp1e1(f)⋯dprer(f) > lg n - 1 holds for almost all f when f is chosen uniformly at random from all n-variate Boolean functions. Our proof uses the second moment method to show that a random f must almost always contain a nondegenerate symmetric subfunction on at least lg n - 1 variables. It follows that an n-variate nondegenerate symmetric Boolean function can have degree o(√n) over at most one finite field and that almost all f can have degree o(√lg n) over at most one finite field.

UR - http://www.scopus.com/inward/record.url?scp=84969779583&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2015.7282505

DO - 10.1109/ISIT.2015.7282505

M3 - Conference contribution

AN - SCOPUS:84969779583

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 501

EP - 505

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -