License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2015.381
URN: urn:nbn:de:0030-drops-50528
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5052/
Go to the corresponding LIPIcs Volume Portal

Hrubes, Pavel ; Rao, Anup

Circuits with Medium Fan-In

pdf-format:
4.pdf (0.5 MB)

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)) non-input 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 non-input gates. When the circuit is a formula with gates of fan-in 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 Number-On-Forehead 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 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 a known time-space tradeoff for oblivious branching programs.

BibTeX - Entry

@InProceedings{hrubes_et_al:LIPIcs:2015:5052,
  author =	{Pavel Hrubes and Anup Rao},
  title =	{{Circuits with Medium Fan-In}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{381--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5052},
  URN =		{urn:nbn:de:0030-drops-50528},
  doi =		{10.4230/LIPIcs.CCC.2015.381},
  annote =	{Keywords: Boolean circuit, Complexity, Communication Complexity}
}

Keywords: Boolean circuit, Complexity, Communication Complexity
Collection: 30th Conference on Computational Complexity (CCC 2015)
Issue Date: 2015
Date of publication: 06.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI