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

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

    Presentations 2022
Presentation

New Bounds on the Multiplicative Complexity of Boolean Functions

September 13, 2022

Presenters

Meltem Sönmez Turan - NIST

Description

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