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.2016.89
URN: urn:nbn:de:0030-drops-61964
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6196/
Go to the corresponding LIPIcs Volume Portal

Hrubes, Pavel ; Yehudayoff, Amir

On Isoperimetric Profiles and Computational Complexity

pdf-format:
LIPIcs-ICALP-2016-89.pdf (0.5 MB)

Abstract

The isoperimetric profile of a graph is a function that measures, for an integer k, the size of the smallest edge boundary over all sets of vertices of size k. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, but our main result is in algebraic complexity.

We prove a sharp super-polynomial separation between monotone arithmetic circuits and monotone arithmetic branching programs. This shows that the classical simulation of arithmetic circuits by arithmetic branching programs by Valiant, Skyum, Berkowitz, and Rackoff (1983) cannot be improved, as long as it preserves monotonicity.

A key ingredient in the proof is an accurate analysis of the isoperimetric profile of finite full binary trees. We show that the isoperimetric profile of a full binary tree constantly fluctuates between one and almost the depth of the tree.

BibTeX - Entry

@InProceedings{hrubes_et_al:LIPIcs:2016:6196,
  author =	{Pavel Hrubes and Amir Yehudayoff},
  title =	{{On Isoperimetric Profiles and Computational Complexity}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{89:1--89:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6196},
  URN =		{urn:nbn:de:0030-drops-61964},
  doi =		{10.4230/LIPIcs.ICALP.2016.89},
  annote =	{Keywords: Monotone computation, separations, communication complexity, isoperimetry}
}

Keywords: Monotone computation, separations, communication complexity, isoperimetry
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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