Threshold functions and bounded depth monotone circuits

DOI10.1016/0022-0000(86)90027-9zbMath0617.94012OpenAlexW2062196111MaRDI QIDQ1088970

Ravi B. Boppana

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90027-9

zbMATH Keywords

connectivityHamiltonian cyclescliquesmajority functionmonotone circuitsize-depth trade-offlower bound for the sizelower bounds for graph problems

Mathematics Subject Classification ID

Related Items (2)

How to Share a Secret, Infinitely ⋮ Pi-sigma-pi threshold formulas

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Short monotone formulae for the majority function
• A complexity theory based on Boolean algebra

This page was built for publication: Threshold functions and bounded depth monotone circuits