2026-07-23T16:56:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5757 2024-03-06T10:37:00Z ddc:004 open_access

Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function de Oliveira Oliveira, Mateus non-linear lower bounds treewidth element distinctness 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)}*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 * log(s) >= Omega(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 tau_n which exclude H as a minor must have size at least Omega(n^2/log^{4}(n)). For certain well studied functions, such as the triangle-freeness function, this last lower bound can be improved to Omega(n^2/log^2(n)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mateus de Oliveira Oliveira 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.56 urn:nbn:de:0030-drops-57571 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.56 eng https://creativecommons.org/licenses/by/3.0/legalcode