×

Degree-uniform lower bound on the weights of polynomials with given sign function. (English. Russian original) Zbl 1358.94116

Proc. Steklov Inst. Math. 274, 231-246 (2011); translation from Tr. Mat. Inst. Steklova 274, 252-268 (2011).
Summary: A Boolean function \(f: \{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 \leq D \leq \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: \{-1, 1\}^{n} \to \{-1, 1\}\).

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Beigel, ”The Polynomial Method in Circuit Complexity,” in Structure in Complexity Theory: Proc. Eighth Annu. Conf., San Diego, CA, 1993 (IEEE Computer Soc. Press, Los Alamitos, CA, 1993), pp. 82–95.
[2] R. Beigel, ”Perceptrons, PP, and the Polynomial Hierarchy,” Comput. Complexity 4(4), 339–349 (1994). · Zbl 0829.68059 · doi:10.1007/BF01263422
[3] J. Bruck, ”Harmonic Analysis of Polynomial Threshold Functions,” SIAM J. Discrete Math. 3(2), 168–177 (1990). · Zbl 0695.94022 · doi:10.1137/0403015
[4] M. Goldmann, ”On the Power of a Threshold Gate at the Top,” Inf. Process. Lett. 63(6), 287–293 (1997). · Zbl 1336.94095 · doi:10.1016/S0020-0190(97)00141-5
[5] A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán, ”Threshold Circuits of Bounded Depth,” J. Comput. Syst. Sci. 46(2), 129–154 (1993). · Zbl 0801.68052 · doi:10.1016/0022-0000(93)90001-D
[6] J. Håstad, ”On the Size of Weights for Threshold Gates,” SIAM J. Discrete Math. 7(3), 484–492 (1994). · Zbl 0811.68100 · doi:10.1137/S0895480192235878
[7] A. R. Klivans and R. A. Servedio, ”Learning DNF in Time \(2^{\tilde O(n^{1/3} )} \) ,” J. Comput. Syst. Sci. 68(2), 303–318 (2004). · Zbl 1073.68036 · doi:10.1016/j.jcss.2003.07.007
[8] M. Krause and P. Pudlák, ”Computing Boolean Functions by Polynomials and Threshold Circuits,” Comput. Complexity 7(4), 346–370 (1998). · Zbl 0936.94022 · doi:10.1007/s000370050015
[9] M. L. Minsky and S. A. Papert, Perceptrons: An Introduction to Computational Geometry (MIT Press, Cambridge, MA, 1968). · Zbl 0197.43702
[10] S. Muroga, Threshold Logic and Its Applications (Wiley-Intersci., New York, 1971). · Zbl 0243.94014
[11] J. Myhill and W. H. Kautz, ”On the Size of Weights Required for Linear-Input Switching Functions,” IRE Trans. Electron. Comput. EC10(2), 288–290 (1961). · doi:10.1109/TEC.1961.5219204
[12] V. V. Podolskii, ”A Uniform Lower Bound on Weights of Perceptrons,” in Computer Science-Theory and Applications: Proc. 3rd Int. Symp. CSR 2008, Moscow, Russia, June 7–12, 2008 (Springer, Berlin, 2008), Lect. Notes Comput. Sci. 5010, pp. 261–272. · Zbl 1142.94400
[13] V. V. Podolskii, ”Perceptrons of Large Weight,” Probl. Peredachi Inf. 45(1), 51–59 (2009) [Probl. Inf. Transm. 45, 46–53 (2009)]. · Zbl 1171.68585
[14] A. A. Razborov, ”On Small Depth Threshold Circuits,” in Algorithm Theory: Proc. Third Scand. Workshop, Helsinki, July 8–10, 1992 (Springer, Berlin, 1992), Lect. Notes Comput. Sci. 621, pp. 42–52.
[15] M. E. Saks, ”Slicing the Hypercube,” in Surveys in Combinatorics (Cambridge Univ. Press, Cambridge, 1993), LMS Lect. Note Ser. 187, pp. 211–255. · Zbl 0790.05062
[16] A. A. Sherstov, ”Communication Lower Bounds Using Dual Polynomials,” Bull. Eur. Assoc. Theor. Comput. Sci. 95, 59–93 (2008). · Zbl 1169.68438
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.