We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being layered and depth $2$, we prove the bound of $n^{\Omega(1)}$ on the fan-in of the top gate. When the circuit is a formula, we give a lower bound $\Omega(n^2/k \log n)$ on the total number of gates, for general $k$.

Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the Number-On-Forehead model in communication complexity, or for bounded depth circuits in $\mathsf{AC_0}$, or extractors for varieties over small fields would imply strong lower bounds in our model. On the other hand, new lower bounds for our model would prove new time-space tradeoffs for branching programs and impossibility results for (fan-in 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for the best known time-space tradeoff for oblivious branching programs.

We updated the introduction and made minor changes to the proofs.

We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being depth $2$, we prove the bound of $n^{\Omega(1)}$ on the fan-in of the top gate. When the circuit is a formula, we give a lower bound $\Omega(n^2/k \log n)$ on the total number of gates, for general $k$.

Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the Number-On-Forehead model in communication complexity, or for bounded depth circuits in $\mathsf{AC_0}$, or extractors for varieties over small fields would imply strong lower bounds in our model. On the other hand, new lower bounds for our model would prove new time-space tradeoffs for branching programs and impossibility results for (fan-in 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for the best known time-space tradeoff for oblivious branching programs.