Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-020 | 5th March 2014 19:41

Circuits with Medium Fan-In

RSS-Feed




Revision #1
Authors: Pavel Hrubes, Anup Rao
Accepted on: 5th March 2014 19:41
Downloads: 1396
Keywords: 


Abstract:

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.



Changes to previous version:

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


Paper:

TR14-020 | 18th February 2014 02:51

Circuits with Medium Fan-In





TR14-020
Authors: Pavel Hrubes, Anup Rao
Publication: 18th February 2014 02:52
Downloads: 3376
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint