Circuits with medium fan-in

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00448837" target="_blank" >RIV/67985840:_____/15:00448837 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2015.381" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.CCC.2015.381</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2015.381" target="_blank" >10.4230/LIPIcs.CCC.2015.381</a>

Result language
angličtina
Original language name
Circuits with medium fan-in
Original language description
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 ... that requires at least ... non-input gates when k = 2n/3. When the circuit is restricted to being layered and depth 2, we prove a lower bound of ... on the number of non-input gates. When the circuit is a formula with gates of fan-in k, we give a lower bound ... 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
30th Conference on Computational Complexity (CCC 2015)
ISBN
978-3-939897-81-1
ISSN
1868-8969
e-ISSN
—
Number of pages
11
Pages from-to
381-391
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl
Event location
Portland
Event date
Jun 17, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)