Nonlinear lower bounds on the number of processors of circuits with sublinear separators (Q1183605)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nonlinear lower bounds on the number of processors of circuits with sublinear separators |
scientific article |
Statements
Nonlinear lower bounds on the number of processors of circuits with sublinear separators (English)
0 references
28 June 1992
0 references
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)\).
0 references
graph separation
0 references
magnifiers
0 references
unbounded fan-in Boolean circuit
0 references
Boolean function
0 references
communication complexity
0 references