tlooto
Sign up
Open AccessMathematicsComputer Science

On the degree of boolean functions as real polynomials

N. Nisan, M. Szegedy

1992.7.1COMPUTATIONAL COMPLEXITY

DOI: 10.1007/bf01263419

tlooto Summary

A tight lower bound is found of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables on the level of real polynomial.

Abstract

Abstract is not available.

Citation format

NISAN, N.; SZEGEDY, M. On the degree of boolean functions as real polynomials. COMPUTATIONAL COMPLEXITY, 1992, 4: 301–313.