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

Chillara, Suryajith ; Limaye, Nutan ; Srinivasan, Srikanth

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

pdf-format:
LIPIcs-ICALP-2018-36.pdf (0.5 MB)

Abstract

We show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes.
Formally, for any s = s(n) = n^{O(1)} and any delta>0, we construct explicit families of multilinear polynomials P_n in F[x_1,...,x_n] that have multilinear formulas of size s and depth three but no multilinear formulas of size s^{1/2-delta} and depth o(log n/log log n).
As far as we know, this is the first such result for an algebraic model of computation.
Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using epsilon-biased spaces.

BibTeX - Entry

@InProceedings{chillara_et_al:LIPIcs:2018:9040,
  author =	{Suryajith Chillara and Nutan Limaye and Srikanth Srinivasan},
  title =	{{A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9040},
  URN =		{urn:nbn:de:0030-drops-90401},
  doi =		{10.4230/LIPIcs.ICALP.2018.36},
  annote =	{Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds}
}

Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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