$\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas

DOI10.1137/0211033zbMath0488.94036OpenAlexW2092016058MaRDI QIDQ3950469

Albert R. Meyer, Michael S. Paterson, Michael J. Fischer

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211033

zbMATH Keywords

symmetric functionthreshold functionsBoolean functions of n variables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Better lower bounds for monotone threshold formulas, Upper bounds for the size and the depth of formulae for MOD-functions, Parallelizable algebras, On the depth complexity of the counting functions, Lower bounds to the complexity of symmetric Boolean functions, Upper bounds for the formula size of symmetric Boolean functions, A note on the formula size of the ``mod k functions, Shallow circuits and concise formulae for multiple addition and multiplication