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) no. 2, pp. 103-115. 
@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},
     pages = {103--115},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {2},
     year = {1999},
     mrnumber = {1707964},
     zbl = {0946.68042},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1999__33_2_103_0/}
}
TY  - JOUR
AU  - Bollig, Beate
AU  - Löbbing, Martin
AU  - Sauerhoff, Martin
AU  - Wegener, Ingo
TI  - On the complexity of the hidden weighted bit function for various BDD models
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
SP  - 103
EP  - 115
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1999__33_2_103_0/
LA  - en
ID  - ITA_1999__33_2_103_0
ER  - 
%0 Journal Article
%A Bollig, Beate
%A Löbbing, Martin
%A Sauerhoff, Martin
%A Wegener, Ingo
%T On the complexity of the hidden weighted bit function for various BDD models
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 103-115
%V 33
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1999__33_2_103_0/
%G en
%F 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) no. 2, pp. 103-115. http://archive.numdam.org/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

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

[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 | Zbl

[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 | Zbl

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

[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

[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

[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 | Zbl

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

[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

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

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

[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

[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

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

[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 | Zbl

[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

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