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.CCC.2018.26
URN: urn:nbn:de:0030-drops-88630
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8863/
Go to the corresponding LIPIcs Volume Portal

Lingas, Andrzej

Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth

pdf-format:
LIPIcs-CCC-2018-26.pdf (0.4 MB)

Abstract

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., the maximum number of and-gates on a directed path to an output gate). In particular, we show that any normalized Boolean circuit of at most epsilon log n conjunction-depth computing the n-dimensional Boolean vector convolution has Omega(n^{2-4 epsilon}) and-gates. Analogously, any normalized Boolean circuit of at most epsilon log n conjunction-depth computing the n x n Boolean matrix product has Omega(n^{3-4 epsilon}) and-gates. We complete our lower-bound trade-offs with upper-bound trade-offs of similar form yielded by the known fast algebraic algorithms.

BibTeX - Entry

@InProceedings{lingas:LIPIcs:2018:8863,
  author =	{Andrzej Lingas},
  title =	{{Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{26:1--26:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8863},
  URN =		{urn:nbn:de:0030-drops-88630},
  doi =		{10.4230/LIPIcs.CCC.2018.26},
  annote =	{Keywords: Boolean circuits, semi-disjoint bilinear form, Boolean vector convolution, Boolean matrix product}
}

Keywords: Boolean circuits, semi-disjoint bilinear form, Boolean vector convolution, Boolean matrix product
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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