On the complexity of the hidden weighted bit function for various BDD models
Bollig, Beate ; Löbbing, Martin ; Sauerhoff, Martin ; Wegener, Ingo
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 103-115 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_2_103_0,
     author = {Bollig, Beate and L\"obbing, Martin and Sauerhoff, Martin and Wegener, Ingo},
     title = {On the complexity of the hidden weighted bit function for various BDD models},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {103-115},
     mrnumber = {1707964},
     zbl = {0946.68042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_2_103_0}
}

Bollig, Beate; Löbbing, Martin; Sauerhoff, Martin; Wegener, Ingo. On the complexity of the hidden weighted bit function for various BDD models. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 103-115. http://gdmltest.u-ga.fr/item/ITA_1999__33_2_103_0/

[1] F. Ablayev, Randomization and nondeterminism are incomparable for ordered read-once branching programs, in Proc. of ICALP '97, LNCS 1256 (1997) 195-202. | MR 1616185

[2] F. Ablayev and M. Karpinski, On the power of randomized branching programs, in Proc. of ICALP '96, LNCS 1099 (1996) 348-356. | MR 1464462 | Zbl 1046.68531

[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. | MR 1655683 | Zbl 0935.68025

[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. | MR 1073767 | Zbl 0701.68044

[5] B. Becker, R. Drechsler and R. Werchner, On the relation between BDDs and FDDs. Inform. and Comput. 123 (1997) 185-197. | MR 1362665 | Zbl 0839.68022

[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] R. E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. | Zbl 0593.94022

[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. | MR 1094031

[9] R. E. Bryant, Symbolic manipulation with ordered binary decision diagrams. ACM Computing Surveys 24 (1992) 293-318.

[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] J. Hastad, Almost optimal lower bounds for small depth circuits, in Proc. of 18th STOC (1986) 6-20.

[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. | MR 1130753 | Zbl 0735.68038

[13] J. Hromkovič, Communication Complexity and Parallel Computing. Springer-Verlag (1997). | MR 1442518 | Zbl 0873.68098

[14] J. Jain, J. A. AbrahamJ. Bitner and D. S. Fussell, Probabilistic verification of Boolean functions. Formal Methods in System Design 1 (1992) 61-115. | Zbl 0777.94021

[15] I. Kremer, N. Nisan and D. Ron, On randomized one-round communication complexity, in Proc. of 27th STOC (1995) 596-605. | Zbl 0926.94022

[16] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). | MR 1426129 | Zbl 0869.68048

[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] 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] M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. of STACS '98, LNCS 1373 (1998) 105-115. | MR 1650785

[20] M. Sauerhoff. Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. of Dortmund (1999).

[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. | MR 1734076

[22] D. Sieling and I. Wegener, Graph driven BDDs- a new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. | MR 1323158 | Zbl 0873.68036

[23] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. of 19th STOC (1987) 77-82.

[24] L.G. Valiant, Short monotone formulae for the majority function. J. Algorithms 5 (1984) 363-366. | MR 756162 | Zbl 0554.94017

[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. | MR 1473775

[26] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). | MR 905473 | Zbl 0623.94018