Cherukhin, D. Yu. On formula complexity for products of Boolean functions. (Russian) Zbl 1009.68056 Diskretn. Anal. Issled. Oper., Ser. 1 9, No. 1, 84-94 (2002). Let \(f(x_1,\dots,x_n)\) and \(g(x_1,\dots,x_m)\) be Boolean functions. A function \[ (f\otimes g)(x_1,\dots,x_{nm})= f\bigl(g(x_1,\dots,x_m),\dots,g(x_{(n-1)m+1},\dots,x_{nm})\bigr) \] is called a repetition-free product of Boolean functions. A criterion is given that makes it possible to check whether a sequence of products of Boolean functions can be computed with linear size formulas in a basis \(B\). Reviewer: E.A.Okol’nishnikova (Novosibirsk) MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) Keywords:complexity; Boolean function; lower bound; basis; formula PDFBibTeX XMLCite \textit{D. Yu. Cherukhin}, Diskretn. Anal. Issled. Oper., Ser. 1 9, No. 1, 84--94 (2002; Zbl 1009.68056)