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.2017.4
URN: urn:nbn:de:0030-drops-75448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7544/
Go to the corresponding LIPIcs Volume Portal

Potechin, Aaron

A Note on Amortized Branching Program Complexity

pdf-format:
LIPIcs-CCC-2017-4.pdf (0.5 MB)

Abstract

In this paper, we show that while almost all functions require exponential size branching programs to compute, for all functions f there is a branching program computing a doubly exponential number of copies of f which has linear size per copy of f. This result disproves a conjecture about non-uniform catalytic computation, rules out a certain type of bottleneck argument for proving non-monotone space lower bounds, and can be thought of as a constructive analogue of Razborov's result that submodular complexity measures have maximum value O(n).

BibTeX - Entry

@InProceedings{potechin_et_al:LIPIcs:2017:7544,
  author =	{Aaron Potechin},
  title =	{{A Note on Amortized Branching Program Complexity}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7544},
  URN =		{urn:nbn:de:0030-drops-75448},
  doi =		{10.4230/LIPIcs.CCC.2017.4},
  annote =	{Keywords: branching programs, space complexity, amortization}
}

Keywords: branching programs, space complexity, amortization
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

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