@inproceedings{5a34527d386a44d286533f1b2b3a5e20,
title = "A direct-sum theorem for read-once branching programs",
abstract = "We study a direct-sum question for read-once branching programs. If M(f) denotes the minimum average memory required to compute a function f(x1, x2, . . . , xn) how much memory is required to compute f on k independent inputs that arrive in parallel? We show that when the inputs are sampled independently from some domain X and M(f) = Ω(n), then computing the value of f on k streams requires average memory at least Ω k M(f) n . Our results are obtained by defining new ways to measure the information complexity of read-once branching programs. We define two such measures: The transitional and cumulative information content. We prove that any read-once branching program with transitional information content I can be simulated using average memory O(n(I + 1)). On the other hand, if every read-once branching program with cumulative information content I can be simulated with average memory O(I + 1), then computing f on k inputs requires average memory at least (k (M(f) - 1)).",
keywords = "Direct-sum, Information complexity, Streaming Algorithms",
author = "Anup Rao and Makrand Sinha",
year = "2016",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2016.44",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Klaus Jansen and Claire Mathieu and Rolim, {Jose D. P.} and Chris Umans",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016",
address = "Germany",
note = "19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 ; Conference date: 07-09-2016 Through 09-09-2016",
}