Circuits with medium fan-in
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Circuits with medium fan-in
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Circuits with medium fan-in
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
30th Conference on Computational Complexity (CCC 2015)
ISBN
978-3-939897-81-1
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
11
Strana od-do
381-391
Název nakladatele
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Místo vydání
Dagstuhl
Místo konání akce
Portland
Datum konání akce
17. 6. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—