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 nontrivial generalization of a superlinear lower bound for the size of Boolean formulas (treewidth 1) due to Neciporuk. Subsequently, we turn our attention to readonce circuits, which are circuits where each variable labels at most one input vertex. For each n, we show that any readonce 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, readonce 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 trianglefreeness 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 = {{SizeTreewidth Tradeoffs for Circuits Computing the Element Distinctness Function}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {56:156:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5757},
URN = {urn:nbn:de:0030drops57571},
doi = {10.4230/LIPIcs.STACS.2016.56},
annote = {Keywords: nonlinear lower bounds, treewidth, element distinctness}
}
Keywords: 

nonlinear 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 