More Web Proxy on the site http://driver.im/

research-article

Polynomial threshold functions and Boolean threshold circuits

Authors:

Kristoffer Arnsfelt Hansen,

Vladimir V. PodolskiiAuthors Info & Claims

Information and Computation, Volume 240, Issue C

Pages 56 - 73

https://doi.org/10.1016/j.ic.2014.09.008

Published: 01 February 2015 Publication History

Abstract

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 THR MAJ circuits. We note that known lower bounds for THR 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 AC 0 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 THR 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.

References

[1]

S. Basu, N. Bhatnagar, P. Gopalan, R.J. Lipton, Polynomials that sign represent parity and Descartes' rule of signs, Comput. Complex., 17 (2008) 377-406.

Digital Library

[2]

R. Beigel, The polynomial method in circuit complexity, in: Proceedings of the Eighth Annual Structure in Complexity Theory Conference, IEEE Computer Society Press, 1993, pp. 82-95.

[3]

R. Beigel, Perceptrons, PP, and the polynomial hierarchy, Comput. Complex., 4 (1994) 339-349.

Digital Library

[4]

J. Bruck, R. Smolensky, Polynomial threshold functions, AC 0 functions, and spectral norms, SIAM J. Comput., 21 (1992) 33-42.

Digital Library

[5]

H. Buhrman, N.K. Vereshchagin, R. de Wolf, On computation and communication with small bias, in: IEEE Conference on Computational Complexity, 2007, pp. 24-32.

[6]

P. Butkovič, Max-Linear Systems: Theory and Algorithms, Springer, 2010.

[7]

A.K. Chandra, M.L. Furst, R.J. Lipton, Multi-party protocols, in: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, ACM, 1983, pp. 94-99.

[8]

J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity, J. Comput. Syst. Sci., 65 (2002) 612-625.

Digital Library

[9]

J. Forster, M. Krause, S.V. Lokam, R. Mubarakzjanov, N. Schmitt, H.-U. Simon, Relations between communication complexity, linear arrangements, and computational complexity, in: Lecture Notes in Computer Science, vol. 2245, Springer, 2001, pp. 171-182.

[10]

M. Goldmann, On the power of a threshold gate at the top, Inf. Process. Lett., 63 (1997) 287-293.

Digital Library

[11]

M. Goldmann, J. Håstad, A.A. Razborov, Majority gates vs. general weighted threshold gates, Comput. Complex., 2 (1992) 277-300.

[12]

A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, G. Turán, Threshold circuits of bounded depth, J. Comput. Syst. Sci., 46 (1993) 129-154.

Digital Library

[13]

K.A. Hansen, P.B. Miltersen, Some meet-in-the-middle circuit lower bounds, in: Lecture Notes in Computer Science, vol. 3153, Springer, 2004, pp. 334-345.

[14]

K.A. Hansen, V.V. Podolskii, Exact threshold circuits, in: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, IEEE Computer Society, 2010, pp. 270-279.

Digital Library

[15]

K.A. Hansen, V.V. Podolskii, Polynomial threshold functions and boolean threshold circuits, in: Lecture Notes in Computer Science, vol. 8087, Springer, 2013, pp. 516-527.

[16]

J. Håstad, M. Goldmann, On the power of small-depth threshold circuits, Comput. Complex., 1 (1991) 113-129.

[17]

A.R. Klivans, R. O'Donnell, R.A. Servedio, Learning intersections and thresholds of halfspaces, J. Comput. Syst. Sci., 68 (2004) 808-840.

Digital Library

[18]

A.R. Klivans, R.A. Servedio, Learning DNF in time 2 O ¿ ( n 1 / 3 ), J. Comput. Syst. Sci., 68 (2004) 303-318.

Digital Library

[19]

M. Krause, P. Pudlák, On the computational power of depth-2 circuits with threshold and modulo gates, Theor. Comput. Sci., 174 (1997) 137-156.

Digital Library

[20]

M. Krause, P. Pudlák, Computing boolean functions by polynomials and threshold circuits, Comput. Complex., 7 (1998) 346-370.

Digital Library

[21]

M. Minsky, S. Papert, Perceptrons: An Introduction to Computational Geometry, MIT Press, 1969.

Digital Library

[22]

S. Muroga, Threshold Logic and Its Applications, John Wiley & Sons, Inc., 1971.

[23]

S. Muroga, I. Toda, S. Takasu, Theory of majority decision elements, J. Franklin Inst., 271 (1961) 376-418.

[24]

N. Nisan, The communication complexity of threshold gates, in: Mathematical Studies 1, vol. 1, Bolyai Society, 1993, pp. 301-315.

[25]

R. Paturi, J. Simon, Probabilistic communication complexity, J. Comput. Syst. Sci., 33 (1986) 106-123.

Digital Library

[26]

A. Razborov, A. Wigderson, n ¿ ( log ¿ n ) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom, Inf. Process. Lett., 45 (1993) 303-307.

[27]

A.A. Razborov, A.A. Sherstov, The sign-rank of AC 0, SIAM J. Comput., 39 (2010) 1833-1855.

Digital Library

[28]

M.E. Saks, Slicing the hypercube, in: London Mathematical Society Lecture Note Series, vol. 187, Cambridge University Press, 1993, pp. 211-256.

[29]

A.A. Sherstov, Communication lower bounds using dual polynomials, Bull. Eur. Assoc. Theor. Comput. Sci., 95 (2008) 59-93.

[30]

A.A. Sherstov, Separating AC 0 from depth-2 majority circuits, SIAM J. Comput., 38 (2009) 2113-2129.

Digital Library

[31]

D. Speyer, B. Sturmfels, Tropical mathematics, ArXiv Mathematics e-prints, Aug. 2004.

[32]

J. von zur Gathen, M. Sieveking, A bound on the solutions of linear integer equalities and inequalities, Proc. Am. Math. Soc., 72 (1978) 155-158.

Cited By

Sato TInoue K(2023)Differentiable learning of matricized DNFs and its application to Boolean networksMachine Language10.1007/s10994-023-06346-5112:8(2821-2843)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1007/s10994-023-06346-5
Bajpai SKrishan VKush DLimaye NSrinivasan S(2022)A #SAT Algorithm for Small Constant-Depth Circuits with PTF gatesAlgorithmica10.1007/s00453-021-00915-784:4(1132-1162)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s00453-021-00915-7
Chen LWilliams RAceto L(2019)Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximityProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.19(1-43)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.19

Polynomial threshold functions and Boolean threshold circuits
1. Theory of computation
  1. Computational complexity and cryptography

Recommendations

Extremal properties of polynomial threshold functions

In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following:*Almost every Boolean function has PTF degree at most n2+O(nlogn). Together with results of Anthony ...
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower ...
Hardness results for agnostically learning low-degree polynomial threshold functions
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 240, Issue C

February 2015

131 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sato TInoue K(2023)Differentiable learning of matricized DNFs and its application to Boolean networksMachine Language10.1007/s10994-023-06346-5112:8(2821-2843)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1007/s10994-023-06346-5
Bajpai SKrishan VKush DLimaye NSrinivasan S(2022)A #SAT Algorithm for Small Constant-Depth Circuits with PTF gatesAlgorithmica10.1007/s00453-021-00915-784:4(1132-1162)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s00453-021-00915-7
Chen LWilliams RAceto L(2019)Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximityProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.19(1-43)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.19

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents