A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length

V. V. Podolskii ; A. A. Sherstov

Matematičeskie zametki, Tome 87 (2010) no. 6, pp. 885-899.

Résumé

A Boolean function $f\colon\{-1,+1\}^n\to\{-1,+1\}$ is called the sign function of an integer-valued polynomial $p(x)$ if $f(x)=\operatorname{sgn}(p(x))$ for all $x\in\{-1,+1\}^n$. In this case, the polynomial $p(x)$ is called a perceptron for the Boolean function $f$. The weight of a perceptron is the sum of absolute values of the coefficients of $p$. We prove that, for a given function, a small change in the degree of a perceptron can strongly affect the value of the required weight. More precisely, for each $d=1,2,\dots,n-1$, we explicitly construct a function $f\colon\{-1,+1\}^n\to\{-1,+1\}$ that requires a weight of the form $\exp\{\Theta(n)\}$ when it is represented by a degree $d$ perceptron, and that can be represented by a degree $d+1$ perceptron with weight equal to only $O(n^2)$. The lower bound $\exp\{\Theta(n)\}$ for the degree $d$ also holds for the size of the depth 2 Boolean circuit with a majority function at the top and arbitrary gates of input degree $d$ at the bottom. This gap in the weight values is exponentially larger than those that have been previously found. A similar result is proved for the perceptron length, i.e., for the number of monomials contained in it.

Détail

Keywords: Boolean function, integer-valued polynomial, sign function, Boolean circuit, complexity theory, exponential gap.
Mots-clés : perceptron, discrete Fourier transform

Bibliographie

[1] R. Beigel, “The polynomial method in circuit complexity”, Proceedings of the Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993), IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 82–95 | MR

[2] M. E. Saks, “Slicing the hypercube”, Surveys in Combinatorics, 1993 (Keele), London Math. Soc. Lecture Note Ser., 187, Cambridge Univ. Press, Cambridge, 1993, 211–255 | MR | Zbl

[3] H. Buhrman, R. de Wolf, “Complexity measures and decision tree complexity: a survey”, Theoret. Comput. Sci., 288:1 (2002), 21–43 | DOI | MR | Zbl

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

[5] M. Minskii, S. Peipert, Perseptrony, Mir, M., 1971 | Zbl

[6] R. Paturi, M. E. Saks, “Approximating threshold circuits by rational functions”, Inform. and Comput., 112:2 (1994), 257–272 | DOI | MR | Zbl

[7] K.-Y. Siu, V. P. Roychowdhury, T. Kailath, “Rational approximation techniques for analysis of neural networks”, IEEE Trans. Inform. Theory, 40:2 (1994), 455–466 | DOI | MR | Zbl

[8] J. Aspnes, R. Beigel, M. Furst, S. Rudich, “The expressive power of voting polynomials”, Combinatorica, 14:2 (1994), 135–148 | DOI | MR | Zbl

[9] R. Beigel, N. Reingold, D. Spielman, “PP is closed under intersection”, J. Comput. System Sci., 50:2 (1995), 191–202 | DOI | MR | Zbl

[10] M. Krause, P. Pudlák, “On the computational power of depth-2 circuits with threshold and modulo gates”, Theoret. Comput. Sci., 174:1–2 (1997), 137–156 | DOI | MR | Zbl

[11] A. A. Sherstov, “Separating AC$^0$ from depth-2 majority circuits”, STOC'07 – Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, NY, 2007, 294–301 | MR | Zbl

[12] A. A. Sherstov, “The pattern matrix method for lower bounds on quantum communication”, STOC'08 – Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, New York, NY, 2008, 85–94 | Zbl

[13] A. A. Sherstov, “The unbounded-error communication complexity of symmetric functions”, Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), IEEE Comput. Soc. Press, 2008, 384–393 | DOI

[14] A. A. Razborov, A. A. Sherstov, “The sign-rank of $\mathrm{AC}^0$”, Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), IEEE Comput. Soc. Press, 2008, 57–66 | DOI

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

[16] R. O'Donnell, R. A. Servedio, “New degree bounds for polynomial threshold functions”, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, New York, NY, 2003, 325–334 | MR

[17] A. R. Klivans, A. A. Sherstov, “Unconditional lower bounds for learning intersections of halfspaces”, Mach. Learn., 69:2–3 (2007), 97–114 | DOI

[18] J. C. Jackson, The Harmonic Sieve: A Novel Application of Fourier Analysis to Machine Learning Theory and Practice, PhD thesis, Carnegie Mellon Univ., Pittsburgh, PA, 1995

[19] A. R. Klivans, R. O'Donnell, R. A. Servedio, “Learning intersections and thresholds of halfspaces”, J. Comput. System Sci., 68:4 (2004), 808–840 | DOI | MR | Zbl

[20] A. R. Klivans, R. A. Servedio, “Toward attribute efficient learning of decision lists and parities”, J. Mach. Learn. Res., 7 (2006), 587–602 | MR

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

[22] N. K. Vereshchagin, “Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP”, Third Israel Symposium on the Theory of Computing and Systems (Tel Aviv, 1995), IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 46–51 | MR

[23] H. Buhrman, N. K. Vereshchagin, R. de Wolf, “On computation and communication with small bias”, Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC), IEEE Comput. Soc. Press, 2007, 24–32 | DOI

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

[25] K.-Y. Siu, J. Bruck, “On the power of threshold circuits with small weights”, SIAM J. Discrete Math., 4:3 (1991), 423–435 | DOI | MR | Zbl

[26] J. Bruck, R. Smolensky, “Polynomial threshold functions, AC$^0$ functions, and spectral norms”, SIAM J. Comput., 21:1 (1992.), 33–42 | DOI | MR | Zbl

[27] M. Goldmann, J. Håstad, A. A. Razborov, “Majority gates vs. general weighted threshold gates”, Comput. Complexity, 2:4 (1992), 277–300 | DOI | MR | Zbl

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

[29] M. Krause, “On the computational power of Boolean decision lists”, Comput. Complexity, 14:4 (2005), 362–375 | DOI | MR | Zbl

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

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

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

[33] V. V. Podolskii, “A uniform lower bound on weights of perceptrons”, Computer Science – Theory and Applications, Lecture Notes in Comput. Sci., 5010, Springer-Verlag, Berlin, 2008, 261–272 | MR | Zbl

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

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