Abstract
We present lower and upper bounds on the size of pi-sigma-pi (Π ∑ Π) formulas computing threshold functions for small thresholds. Our results show that the limitations of Π ∑ Π formulas for computing threshold functions for small thresholds are more pronounced than suggested by the lower bounds for small depth circuits computing the majority function.
Similar content being viewed by others
References
R. B. Boppana. Threshold functions and bounded depth monotone circuits.J. Comput. System Sci. 32(2) (1986), 222–229.
R. B. Boppana. Amplification of probabilistic Boolean formulas.Advances in Computing Research, Vol. 5, JAI Press, Greenwich, CT, 1989, pp. 27–45.
G. Hansel. Nombre minimal de contacts de fermature nécessaires pour réaliser une fonction booléenne symétrique den variables.C. R. Acad. Sci. Paris 258 (1964), 6037–6040.
J. Håstad. Almost optimal lower bounds for small depth circuits.Proceedings of the 18thACM Symposium on the Theory of Computing, 1986, pp. 6–20. Final version inAdvances in Computing Research, Vol. 5, JAI Press, Greenwich, CT, 1989, pp. 143–170.
R. E. Krichevskii. Complexity of contact circuits realizing a function of logical algebra.Soviet Phys. Dokl. 8 (1964), 770–772.
J. Radhakrishnan. Better bounds for threshold formulas.Proceedings of the 32ndIEEE Symposium on the Foundations of Computer Science, 1991, pp. 314–323.
J. Radhakrishnan. ∑Π∑ threshold formulas.Combinatorial 14(3) (1994), 345–374.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Radhakrishnan, J. Pi-sigma-pi threshold formulas. Math. Systems Theory 29, 357–374 (1996). https://doi.org/10.1007/BF01192692
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01192692