The complexity of depth-3 circuits computing symmetric Boolean functions. (English) Zbl 1185.68355
Summary: We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin \(k\) which computes the Boolean function \(\mathbf {Exact}^n_{n/(k+1)}\), has at least \((1+1/k)^n/(n+1)\) gates. We show that for \(k = o (\sqrt n)\) this lower bound is essentially tight, by generalizing a known upper bound on the size of depth-3 circuits with bottom fanin 2, computing symmetric Boolean functions.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Blum, N., A boolean function requiring \(3n\) network size, Theoret. Comput. Sci., 28, 337-345 (1984) · Zbl 0539.94036 |
| [2] | Håstad, J., Almost optimal lower bounds for small depth circuits, (STOC’86: Proceedings of the 18th Annual ACM Symp. on Theory of Computing (1986), ACM Press: ACM Press New York, NY, USA), 6-20 |
| [3] | Håstad, J.; Jukna, S.; Pudlák, P., Top-down lower bounds for depth-three circuits, Comput. Complexity, 5, 2, 99-112 (1995) · Zbl 0838.68056 |
| [4] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. System Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052 |
| [5] | Iwama, K.; Morizumi, H., An explicit lower bound of \(5 n - o(n)\) for boolean circuits, (Diks, K.; Rytter, W., MFCS. MFCS, Lecture Notes in Computer Science, vol. 2420 (2002), Springer: Springer Berlin), 353-364 · Zbl 1023.94550 |
| [6] | Klawe, M.; Paul, W. J.; Pippenger, N.; Yannakakis, M., On monotone formulae with restricted depth, (STOC’84: Proceedings of the 16th Annual ACM Symp. on Theory of Computing (1984), ACM Press: ACM Press New York, NY, USA), 480-487 |
| [7] | O. Lachish, R. Raz, Explicit lower bound of \(4.5 n -; \operatorname{o}(n)\); O. Lachish, R. Raz, Explicit lower bound of \(4.5 n -; \operatorname{o}(n)\) · Zbl 1323.68303 |
| [8] | Lupanov, O. B., A method of circuit synthesis, Izv. Vyssh. Uchebn. Zaved. Radiofiz., 1, 120-140 (1958) · Zbl 0081.20902 |
| [9] | Paturi, R.; Pudlak, P.; Zane, F., Satisfiability coding lemma, Chicago J. Theoret. Comput. Sci. (1999) · Zbl 0940.68049 |
| [10] | R. Paturi, P. Pudlak, M.E. Saks, F. Zane, An improved exponential-time algorithm for \(k\); R. Paturi, P. Pudlak, M.E. Saks, F. Zane, An improved exponential-time algorithm for \(k\) · Zbl 1297.68217 |
| [11] | Paturi, R.; Pudlák, P.; Saks, M. E.; Zane, F., An improved exponential-time algorithm for \(k\)-SAT, J. ACM, 52, 3, 337-364 (2005) · Zbl 1297.68217 |
| [12] | Paturi, R.; Saks, M. E.; Zane, F., Exponential lower bounds for depth three boolean circuits, Comput. Complexity, 9, 1, 1-15 (2000) · Zbl 0963.68147 |
| [13] | Pippenger, N.; Fischer, M. J., Relations among complexity measures, J. ACM, 26, 2, 361-381 (1979) · Zbl 0405.68041 |
| [14] | Schnorr, G.-P., The network complexity and the Turing machine complexity of finite functions, Acta Inform., 7, 95-107 (1976) · Zbl 0338.02019 |
| [15] | Shannon, C. E., The synthesis of two-terminal switching circuits, Bell System Techn. J., 28, 1, 59-98 (1949) |
| [16] | Valiant, L. G., Graph-theoretic arguments in low-level complexity, (Gruska, J., MFCS. MFCS, Lecture Notes in Computer Science, vol. 53 (1977), Springer: Springer Berlin), 162-176 · Zbl 0384.68046 |
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.
