The multiplicative complexity of quadratic boolean forms

DOI10.1016/0304-3975(92)90235-8zbMath0753.94021OpenAlexW2026273432MaRDI QIDQ1199694

R. Mirwald, Claus Peter Schnorr

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90235-8

zbMATH Keywords

multiplicative complexityquadratic Boolean forms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (11)

The Multiplicative Complexity of Boolean Functions on Four and Five Variables ⋮ Multiplicative complexity of vector valued Boolean functions ⋮ Tight bounds for the multiplicative complexity of symmetric functions ⋮ On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\). ⋮ The multiplicative complexity of quadratic boolean forms ⋮ Multiplicative complexity of bijective \(4\times 4\) \(S\)-boxes ⋮ On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts ⋮ Boolean functions with multiplicative complexity 3 and 4 ⋮ The conjunctive complexity of quadratic Boolean functions ⋮ On the multiplicative complexity of some Boolean functions ⋮ On the multiplicative complexity of quasi-quadratic Boolean functions

Cites Work

• A Boolean function requiring 3n network size
• A 3n-lower bound on the network complexity of Boolean functions
• The multiplicative complexity of quadratic boolean forms
• A Gödel Theorem on Network Complexity Lower Bounds
• Optimal Evaluation of Pairs of Bilinear Forms
• On the Complexity of Bilinear Forms with Commutativity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The multiplicative complexity of quadratic boolean forms