On XOR Lemma for Polynomial Threshold Weight and Length

摘要

Let f : {-1,1}~n → {-1,1} be a Boolean function. We say that a multilinear polynomial p sign-represents f if f(x) = sgn(p(x)) for all x ∈ {-1,1}~n. In this paper, we consider the length and weight of polynomials sign-representing Boolean functions of the form f ⊕ f ⊕…⊕ f where each f is on a disjoint set of variables. Obviously, if p sign-represents f, then p(x)p(y) sign-represents f(x) ⊕ f(y). We give a constructive proof that there is a shorter polynomial when f is AND on n variables for every n ≥ 3. In addition, we introduce a parameter v_f~* of a Boolean function and show that the k-th root of the minimum weight of a polynomial sign-representing f ⊕f ⊕•••⊕f (k times) converges between v_f~* and (v_f~*)~2 as k goes to infinity.