Weights of exact threshold functions

L. Babai ; K. A. Hansen ; V. V. Podolskii ; Xiaoming Sun

Izvestiya. Mathematics , Tome 85 (2021) no. 6, pp. 1039-1059.

Résumé

We consider Boolean exact threshold functions defined by linear equations and, more generally, polynomials of degree $d$. We give upper and lower bounds on the maximum magnitude (absolute value) of the coefficients required to represent such functions. These bounds are very close. In the linear case in particular they are almost matching. This quantity is the same as the maximum magnitude of the integer coefficients of linear equations required to express every possible intersection of a hyperplane in $\mathbb R^n$ and the Boolean cube $\{0,1\}^n$ or, in the general case, intersections of hypersurfaces of degree $d$ in $\mathbb R^n$ and $\{0,1\}^n$. In the process we construct new families of ill-conditioned matrices. We further stratify the problem (in the linear case) in terms of the dimension $k$ of the affine subspace spanned by the solutions and give upper and lower bounds in this case as well. There is a substantial gap between these bounds, a challenge for future work.

Détail

Keywords: computational complexity, Boolean functions, threshold functions, polynomial threshold functions
Mots-clés : anti-Hadamard matrices.

Bibliographie

[1] M. Agrawal, V. Arvind, “Geometric sets of low information content”, Theoret. Comput. Sci., 158:1-2 (1996), 193–219 | DOI | MR | Zbl

[2] I. Aliev, “Siegel's lemma and sum-distinct sets”, Discrete Comput. Geom., 39:1-3 (2008), 59–66 | DOI | MR | Zbl

[3] N. Alon, Van H. Vũ, “Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs”, J. Combin. Theory Ser. A, 79:1 (1997), 133–160 | DOI | MR | Zbl

[4] L. Babai, K. A. Hansen, V. V. Podolskii, Xiaoming Sun, “Weights of exact threshold functions”, Mathematical foundations of computer science 2010 (Brno, 2010), Lecture Notes in Comput. Sci., 6281, Springer, Berlin, 2010, 66–77 | DOI | MR | Zbl

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

[6] R. Beigel, J. Tarui, S. Toda, “On probabilistic ACC circuits with an exact-threshold output gate”, Algorithms and computation (ISAAC 1992) (Nagoya, 1992), Lecture Notes in Comput. Sci., 650, Springer, Berlin, 1992, 420–429 | DOI | MR | Zbl

[7] T. Bohman, “A construction for sets of integers with distinct subset sums”, Electron. J. Combin., 5 (1998), R3, 14 pp. | DOI | MR | Zbl

[8] Lijie Chen, R. R. Williams, “Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity”, 34th computational complexity conference (CCC 2019) (New Brunswick, NJ, 2019), LIPIcs. Leibniz Int. Proc. Inform., 137, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, 19, 43 pp. | DOI | MR

[9] Xue Chen, Guangda Hu, Xiaoming Sun, “A better upper bound on weights of exact threshold functions”, Theory and applications of models of computation (TAMC 2011) (Tokyo, 2011), Lecture Notes in Comput. Sci., 6648, Springer, Heidelberg, 2011, 124–132 | DOI | MR | Zbl

[10] J. H. Conway, R. K. Guy, “Sets of natural numbers with distinct subset sums”, Notices Amer. Math. Soc., 15 (1968), 345

[11] N. D. Elkies, “An improved lower bound on the greatest element of a sum-distinct set of fixed order”, J. Combin. Theory Ser. A, 41:1 (1986), 89–94 | DOI | MR | Zbl

[12] P. Erdös, “Problems and results in additive number theory”, Colloque sur la théorie des nombres (Bruxelles, 1955), George Thone, Liège; Masson and Cie, Paris, 1956, 127–137 | MR | Zbl

[13] J. Forster, “A linear lower bound on the unbounded error probabilistic communication complexity”, J. Comput. System Sci., 65:4 (2002), 612–625 | DOI | MR | Zbl

[14] F. Green, “A complex-number Fourier technique for lower bounds on the Mod-$m$ degree”, Comput. Complexity, 9:1 (2000), 16–38 | DOI | MR | Zbl

[15] 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

[16] K. A. Hansen, “Computing symmetric Boolean functions by circuits with few exact threshold gates”, Computing and combinatorics (COCOON 2007) (Banff, 2007), Lecture Notes in Comput. Sci., 4598, Springer, Berlin, 2007, 448–458 | DOI | MR | Zbl

[17] K. A. Hansen, “Depth reduction for circuits with a single layer of modular counting gates”, Computer science – theory and applications (CSR 2009) (Novosibirsk, 2009), Lecture Notes in Comput. Sci., 5675, Springer, Berlin, 2009, 117–128 | DOI | Zbl

[18] K. A. Hansen, V. V. Podolskii, “Exact threshold circuits”, 25th annual {IEEE} conference on computational complexity (CCC 2010) (Cambridge, MA, 2010), IEEE Computer Soc., Los Alamitos, CA, 2010, 270–279 | DOI | MR

[19] K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Inform. and Comput., 240 (2015), 56–73 | DOI | MR | Zbl

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

[21] J. Hertz, A. Krogh, R. G. Palmer, Introduction to the theory of neural computation, Santa Fe Inst. Stud. Sci. Complexity Lecture Notes, I, Addison-Wesley Publishing Company, Redwood City, CA, 1991, xxii+327 pp. | MR

[22] S. Muroga, I. Toda, S. Takasu, “Theory of majority decision elements”, J. Franklin Inst., 271:5 (1961), 376–418 | DOI | MR | Zbl

[23] S. Muroga, Threshold logic and its applications, Wiley-Interscience [John Wiley Sons], New York–London–Sydney, 1971, xiv+478 pp. | MR | Zbl

[24] I. Parberry, Circuit complexity and neural networks, Found. Comput. Ser., MIT Press, Cambridge, MA, 1994, xxxiv+270 pp. | MR | Zbl

[25] V. V. Podolskii, “A uniform lower bound on weights of perceptrons”, Computer science – theory and applications (Moscow, 2008), Lecture Notes in Comput. Sci., 5010, Springer, Berlin, 2008, 261–272 | DOI | MR | Zbl

[26] V. V. Podolskii, “Perceptrons of large weight”, Problems Inform. Transmission, 45:1 (2009), 46–53 | DOI | MR | Zbl

[27] D. R. Smith, “Bounds on the number of threshold functions”, IEEE Trans. Electronic Computers, EC-15:3 (1966), 368–369 | DOI | Zbl

[28] N. Vyas, R. R. Williams, “Lower bounds against sparse symmetric functions of ACC circuits: Expanding the reach of #SAT algorithms”, 37th international symposium on theoretical aspects of computer science (STACS 2020) (Montpellier, 2020), LIPIcs. Leibniz Int. Proc. Inform., 154, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, 59, 17 pp. | DOI | MR

[29] R. R. Williams, “Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials”, 33rd computational complexity conference (CCC 2018) (San Diego, CA, 2018), LIPIcs. Leibniz Int. Proc. Inform., 102, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, 6, 24 pp. | DOI | MR | Zbl

[30] J. Williamson, “Determinants whose elements are $0$ and $1$”, Amer. Math. Monthly, 53:8 (1946), 427–434 | DOI | MR | Zbl

[31] S. Yajima, T. Ibaraki, “A lower bound on the number of threshold functions”, IEEE Trans. Electronic Computers, EC-14:6 (1965), 926–929 | DOI | Zbl

[32] G. M. Ziegler, “Lectures on 0/1-polytopes”, Polytopes – combinatorics and computation (Oberwolfach, 1997), DMV Sem., 29, Birkhäuser, Basel, 2000, 1–41 | DOI | MR | Zbl

[33] D. K. Faddeev, I. S. Sominskii, Problems in higher algebra, A Series of Books in Mathematics, W. H. Freemann and Company, San Francisco–London, 1965, ix+498 pp. | MR | MR | Zbl | Zbl