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

作者：Amano Kazuyuki^*; Tarui Jun

来源：Theoretical Computer Science, 2011, 412(18): 1646-1651.

DOI：10.1016/j.tcs.2010.12.040

• Boolean functions
• Circuit complexity
• Upper bound

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 U(2) 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 U(2)-circuit size (Mama, Lachish, Morizumi and Raz [STOC01, MFCS02]), has reached the limit.

• 出版日期2011-4-15