Size-treewidth tradeoffs for circuits computing the element distinctness function

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00458244" target="_blank" >RIV/67985840:_____/16:00458244 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2016.56" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2016.56</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2016.56" target="_blank" >10.4230/LIPIcs.STACS.2016.56</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Size-treewidth tradeoffs for circuits computing the element distinctness function

Popis výsledku v původním jazyce

In this work we study the relationship between size and treewidth of circuits computing variants of the element distinctness function. First, we show that for each n, any circuit of treewidth t computing the element distinctness function delta_n:{0,1}^n -> {0,1} must have size at least Omega((n^2)/(2^{O(t)}times log(n))). This result provides a non-trivial generalization of a super-linear lower bound for the size of Boolean formulas (treewidth 1) due to Neciporuk. Subsequently, we turn our attention to read-once circuits, which are circuits where each variable labels at most one input vertex. For each n, we show that any read-once circuit of treewidth t and size s computing a variant tau_n:{0,1}^n -> {0,1} of the element distinctness function must satisfy the inequality t times log(s) >= Omega(n/log(n)).

Název v anglickém jazyce

Size-treewidth tradeoffs for circuits computing the element distinctness function

Popis výsledku anglicky

In this work we study the relationship between size and treewidth of circuits computing variants of the element distinctness function. First, we show that for each n, any circuit of treewidth t computing the element distinctness function delta_n:{0,1}^n -> {0,1} must have size at least Omega((n^2)/(2^{O(t)}times log(n))). This result provides a non-trivial generalization of a super-linear lower bound for the size of Boolean formulas (treewidth 1) due to Neciporuk. Subsequently, we turn our attention to read-once circuits, which are circuits where each variable labels at most one input vertex. For each n, we show that any read-once circuit of treewidth t and size s computing a variant tau_n:{0,1}^n -> {0,1} of the element distinctness function must satisfy the inequality t times log(s) >= Omega(n/log(n)).

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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ů

Název statě ve sborníku

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

ISBN

978-3-95977-001-9

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl

Místo konání akce

Orléans

Datum konání akce

17. 2. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—