Paper Info
Title
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.
Year
DOI
Venue
1992
10.1145/129712.129758
STOC
Keywords
Field
DocType
preliminary version,constant factor,approximation theory,lower bound,approximating polynomial,symmetric boolean function,approximate symmetric boolean function,minimum degree,upper and lower bounds,boolean function
Boolean function,Discrete mathematics,Combinatorics,Polynomial,Upper and lower bounds,Approximation theory,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89791-511-9
47
3.04
References 
Authors
2
1
Name
Order
Citations
PageRank
Ramamohan Paturi1126092.20