A note on the formula size of the ``mod k functions

DOI10.1016/0020-0190(87)90137-2zbMath0689.06011OpenAlexW2057790733MaRDI QIDQ1264165

D. C. Van Leijenhorst

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90137-2

zbMATH Keywords

finite fieldsymmetric Boolean functionsformula size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Related Items

Upper bounds for the size and the depth of formulae for MOD-functions ⋮ On the depth complexity of the counting functions

Cites Work

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