On the complexity of the hidden weighted bit function for various BDD models

 Access to full text

 Full (PDF)

1. [1] F. Ablayev, Randomization and nondeterminism are incomparable for ordered read-once branching programs, in Proc. of ICALP '97, LNCS 1256 (1997) 195-202. MR1616185
2. [2] F. Ablayev and M. Karpinski, On the power of randomized branching programs, in Proc. of ICALP '96, LNCS 1099 (1996) 348-356. Zbl1046.68531MR1464462
3. [3] M. Agrawal and T. Thierauf, The satisfiability problem for probabilistic ordered branching programs, in Proc. 13th IEEE Conf. on Computational Complexity (1998) 81-90. Zbl0935.68025MR1655683
4. [4] L. Babai, P. Pudlák, V. Rödl and E. Szemerédi, Lower bounds in complexity of symmetric Boolean functions. Theoret. Comput. Sci. 74 (1990) 313-323. Zbl0701.68044MR1073767
5. [5] B. Becker, R. Drechsler and R. Werchner, On the relation between BDDs and FDDs. Inform. and Comput. 123 (1997) 185-197. Zbl0839.68022MR1362665
6. [6] B. Bollig and I. Wegener, Partitioned BDDs vs. other BDD models, in Proc. of the Int. Workshop on Logic Synthesis IWLS '97 (1997). 
7. [7] R. E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
8. [8] R. E. Bryant, On the complexity of VLSI implementations and graph representations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput. 40 (1991) 205-213. Zbl1220.68060MR1094031
9. [9] R. E. Bryant, Symbolic manipulation with ordered binary decision diagrams. ACM Computing Surveys 24 (1992) 293-318. 
10. [10] J. Gergov and C. Meinel, Mod-2-OBDDs-a data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams. Formal Methods in System Design 8 (1996) 273-282. 
11. [11] J. Hastad, Almost optimal lower bounds for small depth circuits, in Proc. of 18th STOC (1986) 6-20. 
12. [12] T. Hofmeister, W. Hohberg and S. Köhling, Some notes on threshold circuits, and multiplication in depth 4. Inform. Process. Lett. 39 (1991) 219-225. Zbl0735.68038MR1130753
13. [13] J. Hromkovič, Communication Complexity and Parallel Computing. Springer-Verlag (1997). Zbl0873.68098MR1442518
14. [14] J. Jain, J. A. Abraham J. Bitner and D. S. Fussell, Probabilistic verification of Boolean functions. Formal Methods in System Design 1 (1992) 61-115. Zbl0777.94021
15. [15] I. Kremer, N. Nisan and D. Ron, On randomized one-round communication complexity, in Proc. of 27th STOC (1995) 596-605. Zbl0926.94022
16. [16] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
17. [17] M. Löbbing, O. Schröer and I. Wegener, The theory of zero-suppressed BDDs and the number of knight's tours, in Proc. of IFIP Workshop on Applications of the Reed-Muller Expansion on Circuit Design (1995) 38-45. 
18. [18] A. Narayan, J. Jain, M. Fujita and A. Sangiovanni-Vincentelli, Partitioned ROBDDs- a compact, canonical and efficiently manipulable representation for Boolean functions, in Proc. of ACM/IEEE Int. Conf. on Computer Aided Design ICCAD '96 (1996) 547-554. 
19. [19] M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. of STACS '98, LNCS 1373 (1998) 105-115. MR1650785
20. [20] M. Sauerhoff. Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. of Dortmund (1999). 
21. [21] M. Sauerhoff, On the size of randomized OBDDs and read-once branching programs for k-stable functions, in Proc. of STACS '99, LNCS 1563 (1999) 488-499. MR1734076
22. [22] D. Sieling and I. Wegener, Graph driven BDDs- a new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. Zbl0873.68036MR1323158
23. [23] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. of 19th STOC (1987) 77-82. 
24. [24] L.G. Valiant, Short monotone formulae for the majority function. J. Algorithms 5 (1984) 363-366. Zbl0554.94017MR756162
25. [25] S. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams, in Proc. of STACS '97, LNCS 1200 (1997) 201-212. MR1473775
26. [26] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). Zbl0623.94018MR905473