A well-mixed function with circuit complexity 5n: Tightness of the Lachish–Raz-type bounds

A Boolean function on n variables is k-mixed if any two distinct restrictions fixing the same set of k variables induce distinct functions on the remaining n−k variables. We give an explicit construction of an (n−o(n))-mixed Boolean function whose circuit complexity over the basis U2 is 5n+o(n). This shows that a lower bound method for the size of a U2-circuit that applies to arbitrary well-mixed functions, which yields the largest known lower bound of 5n−o(n) for the U2-circuit size (Iwama, Lachish, Morizumi and Raz [STOC01, MFCS02]), has reached the limit.