DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2018.15

Hardness of Function Composition for Semantic Read once Branching Programs

Authors: Jeff Edmonds, Venkatesh Medabalimi, and Toniann Pitassi

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract

In this work, we study time/space trade-offs for function composition. We prove asymptotically optimal lower bounds for function composition in the setting of nondeterministic read once branching programs, for the syntactic model as well as the stronger semantic model of read-once nondeterministic computation. We prove that such branching programs for solving the tree evaluation problem over an alphabet of size k requires size roughly k^{Omega(h)}, i.e space Omega(h log k). Our lower bound nearly matches the natural upper bound which follows the best strategy for black-white pebbling the underlying tree. While previous super-polynomial lower bounds have been proven for read-once nondeterministic branching programs (for both the syntactic as well as the semantic models), we give the first lower bounds for iterated function composition, and in these models our lower bounds are near optimal.

Cite as

Jeff Edmonds, Venkatesh Medabalimi, and Toniann Pitassi. Hardness of Function Composition for Semantic Read once Branching Programs. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{edmonds_et_al:LIPIcs.CCC.2018.15,
  author =	{Edmonds, Jeff and Medabalimi, Venkatesh and Pitassi, Toniann},
  title =	{{Hardness of Function Composition for Semantic Read once Branching Programs}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.15},
  URN =		{urn:nbn:de:0030-drops-88747},
  doi =		{10.4230/LIPIcs.CCC.2018.15},
  annote =	{Keywords: Branching Programs, Function Composition, Time-Space Tradeoffs, Semantic Read Once, Tree Evaluation Problem}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2016.36

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs

Authors: Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, and Toniann Pitassi

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

We prove exponential lower bounds on the size of semantic read-once 3-ary nondeterministic branching programs. Prior to our result the best that was known was for D-ary branching programs with |D| >= 2^{13}.

Cite as

Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, and Toniann Pitassi. Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.ICALP.2016.36,
  author =	{Cook, Stephen and Edmonds, Jeff and Medabalimi, Venkatesh and Pitassi, Toniann},
  title =	{{Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.36},
  URN =		{urn:nbn:de:0030-drops-63166},
  doi =		{10.4230/LIPIcs.ICALP.2016.36},
  annote =	{Keywords: Branching Programs, Semantic, Non-deterministic, Lower Bounds}
}

Search Results

Documents authored by Medabalimi, Venkatesh

Hardness of Function Composition for Semantic Read once Branching Programs

Abstract

Cite as

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs

Abstract

Cite as

Thanks for your feedback!

Could not send message