2026-07-22T16:58:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5052 2024-03-06T10:35:47Z ddc:004 open_access

Circuits with Medium Fan-In Hrubes, Pavel Rao, Anup Boolean circuit Complexity Communication Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Hrubes and Anup Rao 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.381 urn:nbn:de:0030-drops-50528 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.381 eng https://creativecommons.org/licenses/by/3.0/legalcode