U.S. flag   An official website of the United States government
Dot gov

Official websites use .gov
A .gov website belongs to an official government organization in the United States.


Secure .gov websites use HTTPS
A lock (Dot gov) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


New Bounds on the Multiplicative Complexity of Boolean Functions

September 13, 2022


Meltem Sönmez Turan - NIST


In 2000, Boyar et al. showed that, for all \(n\geq 0\), at most \(2^{k^2+2k+2kn+n+1}\) \(n\)-variable Boolean functions can be computed with \(k\) AND gates. This bound is used to prove the existence of a 8-variable Boolean functions with MC greater than 7. In this talk, we improve the Boyar et al. bound.

Presented at

Virtual presentation at The 7th International Workshop on Boolean Functions and their Applications (BFA), September 13, 2022

Parent Project

See: Circuit Complexity

Related Topics

Security and Privacy: cryptography

Created September 14, 2022