Size-treewidth tradeoffs for circuits computing the element distinctness function

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Size-treewidth tradeoffs for circuits computing the element distinctness function
Original language description
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)).
Czech name
—
Czech description
—

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

Publication year
2016
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
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
ISBN
978-3-95977-001-9
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl
Event location
Orléans
Event date
Feb 17, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)