zbMATH — the first resource for mathematics

Polynomial threshold functions and Boolean threshold circuits. (English) Zbl 1312.68089
Summary: We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains (as opposed to domains such as \(\{0, 1 \}^n\) or \(\{- 1, 1 \}^n\) that enforce multilinearity). A typical example of such a general Boolean domain, for the purpose of our results, is \(\{1, 2 \}^n\). We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest.
First we motivate the study of PTFs over the \(\{1, 2 \}^n\) domain by showing their close relation to depth two threshold circuits. In particular we show that PTFs of polynomial length and polynomial degree compute exactly the functions computed by polynomial size \(\mathsf{THR} \circ \mathsf{MAJ}\) circuits. We note that known lower bounds for \(\mathsf{THR} \circ \mathsf{MAJ}\) circuits extend to the likely strictly stronger model of PTFs (with no degree restriction). We also show that a “max-plus” version of PTFs is related to \(\mathsf{AC}^0 \circ \mathsf{THR}\) circuits.
We exploit this connection to gain a better understanding of threshold circuits. In particular, we show that (super-logarithmic) lower bounds for 3-player randomized communication protocols with unbounded error would yield (super-polynomial) size lower bounds for \(\mathsf{THR} \circ \mathsf{THR}\) circuits.
Finally, having thus motivated the model, we initiate structural studies of PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI
[1] Basu, S.; Bhatnagar, N.; Gopalan, P.; Lipton, R. J., Polynomials that sign represent parity and Descartes’ rule of signs, Comput. Complex., 17, 3, 377-406, (2008) · Zbl 1188.68150
[2] Beigel, R., The polynomial method in circuit complexity, (Proceedings of the Eighth Annual Structure in Complexity Theory Conference, (1993), IEEE Computer Society Press), 82-95
[3] Beigel, R., Perceptrons, PP, and the polynomial hierarchy, Comput. Complex., 4, 4, 339-349, (1994) · Zbl 0829.68059
[4] Bruck, J.; Smolensky, R., Polynomial threshold functions, \(\operatorname{AC}^0\) functions, and spectral norms, SIAM J. Comput., 21, 1, 33-42, (1992) · Zbl 0743.68063
[5] Buhrman, H.; Vereshchagin, N. K.; de Wolf, R., On computation and communication with small bias, (IEEE Conference on Computational Complexity, (2007)), 24-32
[6] Butkovič, P., MAX-linear systems: theory and algorithms, (2010), Springer · Zbl 1202.15032
[7] Chandra, A. K.; Furst, M. L.; Lipton, R. J., Multi-party protocols, (Proceedings of the 15th Annual ACM Symposium on Theory of Computing, (1983), ACM), 94-99
[8] Forster, J., A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65, 4, 612-625, (2002) · Zbl 1058.68058
[9] Forster, J.; Krause, M.; Lokam, S. V.; Mubarakzjanov, R.; Schmitt, N.; Simon, H.-U., Relations between communication complexity, linear arrangements, and computational complexity, (Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2245, (2001), Springer), 171-182 · Zbl 1052.68051
[10] Goldmann, M., On the power of a threshold gate at the top, Inf. Process. Lett., 63, 6, 287-293, (1997) · Zbl 1336.94095
[11] Goldmann, M.; Håstad, J.; Razborov, A. A., Majority gates vs. general weighted threshold gates, Comput. Complex., 2, 4, 277-300, (1992) · Zbl 0770.68054
[12] Hajnal, A.; Maass, W.; Pudlák, P.; Szegedy, M.; Turán, G., Threshold circuits of bounded depth, J. Comput. Syst. Sci., 46, 2, 129-154, (1993) · Zbl 0801.68052
[13] Hansen, K. A.; Miltersen, P. B., Some meet-in-the-middle circuit lower bounds, (29th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 3153, (2004), Springer), 334-345 · Zbl 1096.68062
[14] Hansen, K. A.; Podolskii, V. V., Exact threshold circuits, (Proceedings of the 25th Annual IEEE Conference on Computational Complexity, (2010), IEEE Computer Society), 270-279
[15] Hansen, K. A.; Podolskii, V. V., Polynomial threshold functions and Boolean threshold circuits, (38th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 8087, (2013), Springer), 516-527 · Zbl 1312.68088
[16] Håstad, J.; Goldmann, M., On the power of small-depth threshold circuits, Comput. Complex., 1, 113-129, (1991) · Zbl 0774.68060
[17] Klivans, A. R.; O’Donnell, R.; Servedio, R. A., Learning intersections and thresholds of halfspaces, J. Comput. Syst. Sci., 68, 4, 808-840, (2004) · Zbl 1074.68026
[18] Klivans, A. R.; Servedio, R. A., Learning DNF in time \(2^{\widetilde{O}(n^{1 / 3})}\), J. Comput. Syst. Sci., 68, 2, 303-318, (2004) · Zbl 1073.68036
[19] Krause, M.; Pudlák, P., On the computational power of depth-2 circuits with threshold and modulo gates, Theor. Comput. Sci., 174, 1-2, 137-156, (1997) · Zbl 0908.68110
[20] Krause, M.; Pudlák, P., Computing Boolean functions by polynomials and threshold circuits, Comput. Complex., 7, 4, 346-370, (1998) · Zbl 0936.94022
[21] Minsky, M.; Papert, S., Perceptrons: an introduction to computational geometry, (1969), MIT Press · Zbl 0197.43702
[22] Muroga, S., Threshold logic and its applications, (1971), John Wiley & Sons, Inc. · Zbl 0243.94014
[23] Muroga, S.; Toda, I.; Takasu, S., Theory of majority decision elements, J. Franklin Inst., 271, 376-418, (1961) · Zbl 0196.51705
[24] Nisan, N., The communication complexity of threshold gates, (Miklós, V. T.S. D.; Szönyi, T., Combinatorics, Paul Erdős is Eighty, Mathematical Studies 1, vol. 1, (1993), Bolyai Society), 301-315 · Zbl 0790.94028
[25] Paturi, R.; Simon, J., Probabilistic communication complexity, J. Comput. Syst. Sci., 33, 1, 106-123, (1986) · Zbl 0625.68029
[26] Razborov, A.; Wigderson, A., \(n^{\Omega(\log n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom, Inf. Process. Lett., 45, 6, 303-307, (1993) · Zbl 0783.68046
[27] Razborov, A. A.; Sherstov, A. A., The sign-rank of \(\operatorname{AC}^0\), SIAM J. Comput., 39, 5, 1833-1855, (2010) · Zbl 1211.68213
[28] Saks, M. E., Slicing the hypercube, (Walker, K., Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 187, (1993), Cambridge University Press), 211-256 · Zbl 0790.05062
[29] Sherstov, A. A., Communication lower bounds using dual polynomials, Bull. Eur. Assoc. Theor. Comput. Sci., 95, 59-93, (2008) · Zbl 1169.68438
[30] Sherstov, A. A., Separating \(\operatorname{AC}^0\) from depth-2 majority circuits, SIAM J. Comput., 38, 6, 2113-2129, (2009) · Zbl 1188.68149
[31] D. Speyer, B. Sturmfels, Tropical mathematics, ArXiv Mathematics e-prints, Aug. 2004.
[32] von zur Gathen, J.; Sieveking, M., A bound on the solutions of linear integer equalities and inequalities, Proc. Am. Math. Soc., 72, 1, 155-158, (1978) · Zbl 0397.90071
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.