Degree-uniform lower bound on the weights of polynomials with given sign function

Vladimir V. Podolskii

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 252-268.

Résumé

A Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is called the sign function of an integer polynomial $p$ of degree $d$ in $n$ variables if it is true that $f(x)=1$ if and only if $p(x)>0$. In this case the polynomial $p$ is called a threshold gate of degree $d$ for the function $f$. The weight of the threshold gate is the sum of the absolute values of the coefficients of $p$. For any $n$ and $d\le D\le\frac{\varepsilon n^{1/5}}{\log n}$ we construct a function $f$ such that there is a threshold gate of degree $d$ for $f$, but any threshold gate for $f$ of degree at most $D$ has weight $2^{(\delta n)^d/D^{4d}}$, where $\varepsilon>0$ and $\delta>0$ are some constants. In particular, if $D$ is constant, then any threshold gate of degree $D$ for our function has weight $2^{\Omega(n^d)}$. Previously, functions with these properties have been known only for $d=1$ (and arbitrary $D$) and for $D=d$. For constant $d$ our functions are computable by polynomial size DNFs. The best previous lower bound on the weights of threshold gates for such functions was $2^{\Omega(n)}$. Our results can also be translated to the case of functions $f\colon\{-1,1\}^n\to\{-1,1\}$.

Bibliographie

[1] Beigel R., “The polynomial method in circuit complexity”, Structure in complexity theory, Proc. Eighth Annu. Conf., San Diego, CA, 1993, IEEE Computer Soc. Press, Los Alamitos, CA, 1993, 82–95 | MR

[2] Beigel R., “Perceptrons, PP, and the polynomial hierarchy”, Comput. Complexity, 4:4 (1994), 339–349 | DOI | MR | Zbl

[3] Bruck J., “Harmonic analysis of polynomial threshold functions”, SIAM J. Discr. Math., 3:2 (1990), 168–177 | DOI | MR | Zbl

[4] Goldmann M., “On the power of a threshold gate at the top”, Inf. Process. Lett., 63:6 (1997), 287–293 | DOI | MR

[5] Hajnal A., Maass W., Pudlák P., Szegedy M., Turán G., “Threshold circuits of bounded depth”, J. Comput. and Syst. Sci., 46:2 (1993), 129–154 | DOI | MR

[6] Håstad J., “On the size of weights for threshold gates”, SIAM J. Discr. Math., 7:3 (1994), 484–492 | DOI | MR

[7] Klivans A.R., Servedio R.A., “Learning DNF in time $2^{\tilde O(n^{1/3})}$”, J. Comput. and Syst. Sci., 68:2 (2004), 303–318 | DOI | MR | Zbl

[8] Krause M., Pudlák P., “Computing Boolean functions by polynomials and threshold circuits”, Comput. Complexity, 7:4 (1998), 346–370 | DOI | MR | Zbl

[9] Minskii M., Peipert S., Perseptrony, Mir, M., 1971

[10] Muroga S., Threshold logic and its applications, Wiley–Intersci., New York, 1971 | MR | Zbl

[11] Myhill J., Kautz W.H., “On the size of weights required for linear-input switching functions”, IRE Trans. Electron. Comput., EC10:2 (1961), 288–290 | DOI | MR

[12] Podolskii V.V., “A uniform lower bound on weights of perceptrons”, Computer science—theory and applications, Proc. 3rd Intern. Symp. CSR 2008, Moscow (Russia), June 7–12, 2008, Lect. Notes Comput. Sci., 5010, Springer, Berlin, 2008, 261–272 | DOI | MR | Zbl

[13] Podolskii V.V., “Pertseptrony s bolshim vesom”, Probl. peredachi inform., 45:1 (2009), 51–59 | MR | Zbl

[14] Razborov A.A., “On small depth threshold circuits”, Algorithm theory, Proc. Third Scand. Workshop, Helsinki, July 8–10, 1992, Lect. Notes Comput. Sci., 621, Springer, Berlin, 1992, 42–52 | DOI | MR

[15] Saks M.E., “Slicing the hypercube”, Surveys in combinatorics, LMS Lect. Note Ser., 187, Cambridge Univ. Press, Cambridge, 1993, 211–255 | MR | Zbl

[16] Sherstov A.A., “Communication lower bounds using dual polynomials”, Bull. Eur. Assoc. Theor. Comput. Sci., 95 (2008), 59–93 | MR | Zbl