We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function.
- Authors
de Oliveira Oliveira, Mateus
- Abstract
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 δ : {0, 1} → {0, 1} must have size at least $\Omega (\frac {n^{2}}{2^{O(t)} \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 Nečiporuk. 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 τ : {0, 1} → {0, 1} of the element distinctness function must satisfy the inequality $t\cdot \log s \geq \Omega (\frac {n}{\log n})$ . Using this inequality in conjunction with known results in structural graph theory, we show that for each fixed graph H, read-once circuits computing τ which exclude H as a minor must have size at least Ω( n /log n). For certain well studied functions, such as the triangle-freeness function, this last lower bound can be improved to Ω( n /log 2 n).
- Subjects
LOGIC circuits; MATHEMATICAL formulas; MATHEMATICAL functions; GEOMETRIC vertices; MATHEMATICAL bounds; GENERALIZATION
- Publication
Theory of Computing Systems, 2018, Vol 62, Issue 1, p136
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-017-9814-5