×

Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth. (English) Zbl 1433.68141

Summary: We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., the maximum number of and-gates on a directed path to an output gate). In particular, we show that any normalized Boolean circuit of at most \(\epsilon \log n\) conjunction-depth computing the \(n\)-dimensional Boolean vector convolution has \(\Omega( n^{2 - 4 \epsilon})\) and-gates. For Boolean matrix product, we derive even a stronger lower-bound trade-off. Instead of conjunction-depth we use the negation-dependent conjunction-depth, where one counts only and-gates whose each direct predecessor has a (not necessarily direct) predecessor representing a negated input variable. We show that if a normalized Boolean circuit of at most \(\epsilon \log n\) negation-dependent conjunction-depth computes the \(n \times n\) Boolean matrix product then the circuit has \(\Omega( n^{3 - 2 \epsilon})\) and-gates. We complete our lower-bound trade-offs for the Boolean convolution and matrix product with upper-bound trade-offs of similar form yielded by the known fast algebraic algorithms.

MSC:

68Q06 Networks and circuits as models of computation; circuit complexity
Full Text: DOI

References:

[1] Alon, N.; Boppana, R. B., The monotone circuit complexity of boolean functions, Combinatorica, 7, 1, 1-22 (1987) · Zbl 0631.68041
[2] Andreev, A. E., On one method of obtaining constructive lower bounds for the monotone circuit size, Algebra Log., 26, 1, 3-26 (1987) · Zbl 0643.94027
[3] Blum, N., An \(\omega( n^{4 / 3})\) lower bound on the monotone network complexity of the n-th degree convolution, Theor. Comput. Sci., 36, 59-69 (1985) · Zbl 0577.94015
[4] Blum, N., On negations in boolean networks, (Efficient Algorithms. Efficient Algorithms, Lecture Notes in Computer Science, vol. 5760 (2009), Springer-Verlag), 18-29 · Zbl 1257.94039
[5] De, A.; Kurur, P. P.; Saha, C.; Saptharishi, R., Fast integer multiplication using modular arithmetic, SIAM J. Comput., 42, 2, 685-699 (2013) · Zbl 1271.68247
[6] (Reif, J. H., Synthesis of Parallel Algorithms (1993), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo)
[7] Fisher, M. J.; Paterson, M. S., String-matching and other products, (Proceedings of the 7th SIAM-AMS Complexity of Computation (1974)), 113-125 · Zbl 0301.68027
[8] Fürer, M., Faster integer multiplication, SIAM J. Comput., 39, 3, 979-1005 (2009) · Zbl 1192.68926
[9] Le Gall, F., Powers of tensors and fast matrix multiplication, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, Lecture Notes in Computer Science (2014), Springer-Verlag), 296-303 · Zbl 1325.65061
[10] Grinchuk, M. I.; Sergeev, I. S., Thin circulant matrices and lower bounds on the complexity of some boolean operations, Diskretn. Anal. Issled. Oper., 18, 35-53 (2011) · Zbl 1249.68087
[11] Iwama, K.; Morizumi, H., An explicit lower bound of \(5 n - o(n)\) for boolean circuits, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science (2002), Springer-Verlag), 353-364 · Zbl 1023.94550
[12] Lachish, O.; Raz, R., Explicit lower bound of \(4.5 n - o(n)\) for boolen circuits, (Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (2001), ACM), 399-408 · Zbl 1323.68303
[13] Lamagna, E. A., The complexity of monotone networks for certain bilinear forms, routing problems, sorting, and merging, IEEE Trans. Comput., c-28, 10 (1979) · Zbl 0422.68012
[14] Lingas, A., Towards an almost quadratic lower bound on the monotone circuit complexity of the boolean convolution, (Theory and Applications of Models of Computation. Theory and Applications of Models of Computation, Lecture Notes in Computer Science (2017), Springer-Verlag), 401-411 · Zbl 1462.94078
[15] Mehlhorn, K.; Galil, Z., Monotone switching circuits and boolean matrix product, Computing, 16, 99-111 (1976) · Zbl 0323.94019
[16] Paterson, M., Complexity of monotone networks for boolean matrix product, Theor. Comput. Sci., 1, 1, 13-20 (1975) · Zbl 0307.68031
[17] Pippenger, N.; Valiant, L. G., Shifting graphs and their applications, J. ACM, 23, 3, 423-432 (1976) · Zbl 0335.68032
[18] Pratt, V. R., The power of negative thinking in multiplying boolean matrices, SIAM J. Comput., 4, 3, 326-330 (1975) · Zbl 0318.94040
[19] Raz, R., On the complexity of matrix product, (Proceedings of the 34th Annual ACM Symposium on Theory of Computing (2002), ACM), 144-151 · Zbl 1192.68327
[20] Razborov, A. A., Lower bounds on the monotone complexity of some boolean functions, Dokl. Akad. Nauk, 281, 4, 798-801 (1985)
[21] Schnorr, C. P., Zwei lineare untere schranken für die komplexität boolescher funktionen, Computing, 13, 2, 155-171 (1974) · Zbl 0313.68033
[22] Schnorr, C. P., A lower bound on the number of additions in monotone computations, Theor. Comput. Sci., 2, 3, 305-315 (1976) · Zbl 0342.68024
[23] Schönhage, A.; Strassen, V., Schnelle multiplikation grober zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007
[24] Stothers, A. J., On the complexity of matrix multiplication (2010), University of Edinburgh, PhD thesis
[25] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[26] Valiant, L. G., Negation can be exponentially powerfull, Theor. Comput. Sci., 12, 303-314 (1980) · Zbl 0442.68030
[27] Wegener, I., The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science (1987), Wiley: Wiley New York, Stuttgart · Zbl 0623.94018
[28] Weiss, J., An \(n^{3 / 2}\) lower bound on the monotone network complexity of the boolean convolution, Inf. Control, 59, 184-188 (1983) · Zbl 0576.94029
[29] Vassilevska Williams, V., Multiplying matrices faster than coppersmith-winograd, (Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), ACM), 807-898 · Zbl 1286.65056
[30] Zwick, U., All pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM, 49, 3, 289-317 (2002) · Zbl 1326.05157
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.