Abstract
Recent breakthroughs have lead to strong methods for proving lower bounds on the size of branching programs (BPs) with quite weak restrictions. Nevertheless, lower bounds for the randomized and nondeterministic variants of the established BP models still offer many challenges. Here, the knowledge on the randomized case is extended as follows:
(i) The so-far open problem of proving that randomization with arbitrary bounded error can be weaker than nondeterminism for read-once BPs is solved in the following strong sense: It is shown that the so-called “weighted sum function” requires strongly exponential size for randomized read-once BPs with error bounded by any constant smaller than 1/2, while both the function and its complement have polynomial size for nondeterministic read-once BPs.
(ii) For randomized read-k BPs, an exponential lower bound for a natural, graph-theoretical function that is easy to compute nondeterministically is presented. This is the first such bound for the boolean BP model. The function cl3,n deciding whether an n-vertex graph contains a triangle is obviously easy for nondeterministic read-once BPs while its complement is known to require strongly exponential size in this model. It is proved here that the function still requires size 2ω(k -22-4k√n) for randomized read-k BPs with error at most 2-c2 2k for some positive constant c.
Supported by DFG grant We 1066/9.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Ablayev. Randomization and nondeterminism are incomparable for polynomial ordered binary decision diagrams. In Proc. of ICALP, LNCS 1256, 195–202. Springer, 1997.
M. Ajtai. Determinism versus non-determinism for linear time RAMs with memory restrictions. In Proc. of 31st STOC, 632–641, 1999.
M. Ajtai. A non-linear time lower bound for boolean branching programs. In Proc. of 40th FOCS, 60–70, 1999.
L. Babai. The Fourier transform and equations over finite abelian groups. Lecture Notes, version 1.2, Dec. 1989.
L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proc. of 27th FOCS, 337–347, 1986.
P. Beame, T. S. Jayram, and M. Saks. Time-space tradeoffs for branching programs. Journal of Computer and System Sciences, 63(4):542–572, 2001.
P. Beame, M. Saks, X. Sun, and E. Vee. Super-linear time-space tradeoff lower bounds for randomized computation. In Proc. of 41st FOCS, 169–179, 2000.
P. Beame and E. Vee. Time-space tradeoffs, multiparty communication complexity, and nearest neighbor problems. In Proc. of 34th STOC, 688–697, 2002.
B. Bollig, M. Sauerho., I. Wegener. On the nonapproximability of boolean functions by OBDDs and read-k-times branching programs. Information and Computation, 178:263–278, 2002.
A. Borodin, A. A. Razborov, and R. Smolensky. On lower bounds for read-k-times branching programs. Computational Complexity, 3:1–18, 1993.
P. Duriš, J. Hromkovič, S. Jukna, M. Sauerho., and G. Schnitger. On multipartition communication complexity. In Proc. of 18th STACS, LNCS 2010, 206–217. Springer, 2001.
J. Hromkovič and M. Sauerho.. Tradeoffs between nondeterminism and complexity for communication protocols and branching programs. In Proc. of 17th STACS, LNCS 1770, 145–156. Springer, 2000.
S. Jukna and G. Schnitger. On multi-partition communication complexity of triangle-freeness. Combinatorics, Probability amp; Computing 11(6):549–569, 2002.
I. Kremer, N. Nisan, and D. Ron. On randomized one-round communication complexity. Computational Complexity, 8(1):21–49, 1999.
I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67–71, 1991.
E. A. Okol’nishnikova. On lower bounds for branching programs. Siberian Advances in Mathematics, 3(1):152–166, 1993.
M. Sauerhoff. Lower bounds for randomized read-k-times branching programs. In Proc. of 15th STACS, LNCS 1373, 105–115. Springer, 1998.
M. Sauerhoff. Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. Dortmund. Shaker, Aachen, 1999.
M. Sauerhoff. Approximation of boolean functions by combinatorial rectangles. ECCC, Technical Report 58, 2000. To appear in Theoretical Computer Science.
M. Sauerhoff. On the size of randomized OBDDs and read-once branching programs for k-stable functions. Computational Complexity, 10:155–178, 2001.
P. Savický and S. Žák. A read-once lower bound and a (1,+k)-hierarchy for branching programs. Theoretical Computer Science, 238(1–2):347–362, 2000.
J. Simon and M. Szegedy. A new lower bound theorem for read-only-once branching programs and its applications. In J.-J. Cai, editor, Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, 183–193. American Mathematical Society, 1993.
J. Thathachar. On separating the read-k-times branching program hierarchy. In Proc. of 30th STOC, 653–662, 1998.
I. Wegener. Branching Programs and Binary Decision Diagrams-Theory and Applications. Monographs on Discrete and Applied Mathematics. SIAM, Philadelphia, PA, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sauerhoff, M. (2003). Randomness versus Nondeterminism for Read-Once and Read-k Branching Programs. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_28
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive