When Six Gates are Not Enough
classification
💻 cs.CC
keywords
applybooleancannotcomplexitycomputedelementsenoughexist
read the original abstract
We apply the pigeonhole principle to show that there must exist Boolean functions on 7 inputs with a multiplicative complexity of at least 7, i.e., that cannot be computed with only 6 multiplications in the Galois field with two elements.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.