Nonlinear lower bounds on the number of processors of circuits with sublinear separators (Q1183605)

An unbounded fan-in Boolean circuit of size \(T\) is called \(t\)-separable \((t\leq T)\) if there are \(t\) gates such that their deletion divides the circuit into two components of size at most \(2T/3\) each. It is proved, for any Boolean function \(f(x_ 1,\dots,x_ n)\), that if \(f\) has the communication complexity \(\Omega(n)\) then, for any constants \(k\geq 1\) and \(0<b<1\), the function \(f\) requires \(kn^ b\)-separable circuits of size \(\Omega(n^{1/b})\). This implies that each Boolean function with linear communication complexity requires planar unbounded fan-in circuits of size \(\Omega(n^ 2)\).