ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

On the degree of boolean functions as real polynomials (1994)

Nisan, Noam ; Szegedy, Mario

Springer

Computational complexity 4 (1994), S. 301-313

add to mindlist on the mindlist

Details

ISSN: 1420-8954

Keywords: Approximation ; block sensitivity ; Boolean functions ; Fourier degree ; 68Q05 ; 68Q99

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science

Notes: Abstract Every Boolean function may be represented as a real polynomial. In this paper, we characterize the degree of this polynomial in terms of certain combinatorial properties of the Boolean function. Our first result is a tight lower bound of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables. Our second result states that for every Boolean functionf, the following measures are all polynomially related: o The decision tree complexity off. o The degree of the polynomial representingf. o The smallest degree of a polynomialapproximating f in theL max norm.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01263419

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit