Hrubes, Pavel ;
Rao, Anup
Circuits with Medium FanIn
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:{0,1}^n > {0,1} that requires at least Omega(log^2(n)) noninput gates when k = 2n/3. When the circuit is restricted to being layered and depth 2, we prove a lower bound of n^(Omega(1)) on the number of noninput gates. When the circuit is a formula with gates of fanin k, we give a lower bound Omega(n^2/k*log(n)) on the total number of gates.
Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the NumberOnForehead model in communication complexity, or for bounded depth circuits in 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 timespace tradeoffs for branching programs and impossibility results for (fanin 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for a known timespace tradeoff for oblivious branching programs.
BibTeX  Entry
@InProceedings{hrubes_et_al:LIPIcs:2015:5052,
author = {Pavel Hrubes and Anup Rao},
title = {{Circuits with Medium FanIn}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {381391},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5052},
URN = {urn:nbn:de:0030drops50528},
doi = {10.4230/LIPIcs.CCC.2015.381},
annote = {Keywords: Boolean circuit, Complexity, Communication Complexity}
}
2015
Keywords: 

Boolean circuit, Complexity, Communication Complexity 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 