On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

ABSTRACT

In this paper, we provide matching (up to a constant factor) upper and lower bounds on the degree of polynomials that represent symmetric boolean functions with an error 1/3. Let &Ggr;(f)=min{|2k–n+1|:fk ≠ fk+ 1 and 0 ≤ k ≤ n – 1} where fi is the value of f on inputs with exactly i 1's. We prove that the minimum degree over all the approximating polynomials of f is &THgr;((n(n-&Ggr;(f))).5). We apply the techniques and tools from approximation theory to derive this result.

REFERENCES

• 1: Ivanov, K. (1983). On a new characteristic of functions. II Direct and Converse theorems for best algebraic approximation in C{-1,1} and Lp{-1, 1}, Pliska, 5, 151-63.
• 2: Minsky, M. and Papert, S.A. (1969), "Perceptrons", MIT Press, Cambridge, Massachusetts.
• 3: Nisan, N. and Szegedy, M. (1991). On the Degree of Boolean Functions as Real Polynomials, in preparation.
• 4: Petrushev, P.P. and Popov, V.A. (1987)..Rational Approximation of Real Functions, Cambridge University Press.
• 5: Rivlin, T.j. (1990). Chebyshev Polynomials, John Wiley and Sons Co., 2nd Edition.
• 6: Razborov, A.A. (1986), Lower Bounds on the Size of Bounded Depth Networks over a Complete Basis with Logical Addition, Mathematische Zametki 37 pp. 887-00 (in Russian). English Translation inMathematical Notes of the Academy of Sciences of the USSR 37, pp. 485- 509.
• 7: R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
• 8: Szegedy, M. (1989), "Algebraic Method in Lower Bounds for Computational Models with Limited Communication", Ph.D. Dissertation, University of Chicago.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Performance, Theory