License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.56
URN: urn:nbn:de:0030-drops-57571
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5757/
Go to the corresponding LIPIcs Volume Portal

de Oliveira Oliveira, Mateus

Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function

pdf-format:
57.pdf (0.7 MB)

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 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)).

BibTeX - Entry

@InProceedings{deoliveiraoliveira:LIPIcs:2016:5757,
  author =	{Mateus de Oliveira Oliveira},
  title =	{{Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5757},
  URN =		{urn:nbn:de:0030-drops-57571},
  doi =		{10.4230/LIPIcs.STACS.2016.56},
  annote =	{Keywords: non-linear lower bounds, treewidth, element distinctness}
}

Keywords: non-linear lower bounds, treewidth, element distinctness
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI