@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://www.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://www.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://www.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://www.numdam.org/item/ITA_1999__33_2_103_0/
[1] Randomization and nondeterminism are incomparable for ordered read-once branching programs, in Proc. of ICALP '97, LNCS 1256 (1997) 195-202. | MR
,[2] On the power of randomized branching programs, in Proc. of ICALP '96, LNCS 1099 (1996) 348-356. | MR | Zbl
and ,[3] The satisfiability problem for probabilistic ordered branching programs, in Proc. 13th IEEE Conf. on Computational Complexity (1998) 81-90. | MR | Zbl
and ,[4] Lower bounds in complexity of symmetric Boolean functions. Theoret. Comput. Sci. 74 (1990) 313-323. | MR | Zbl
, , and ,[5] On the relation between BDDs and FDDs. Inform. and Comput. 123 (1997) 185-197. | MR | Zbl
, and ,[6] Partitioned BDDs vs. other BDD models, in Proc. of the Int. Workshop on Logic Synthesis IWLS '97 (1997).
and ,[7] Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. | Zbl
,[8] 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] Symbolic manipulation with ordered binary decision diagrams. ACM Computing Surveys 24 (1992) 293-318.
,[10] 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.
and ,[11] Almost optimal lower bounds for small depth circuits, in Proc. of 18th STOC (1986) 6-20.
,[12] Some notes on threshold circuits, and multiplication in depth 4. Inform. Process. Lett. 39 (1991) 219-225. | MR | Zbl
, and ,[13] Communication Complexity and Parallel Computing. Springer-Verlag (1997). | MR | Zbl
,[14] Probabilistic verification of Boolean functions. Formal Methods in System Design 1 (1992) 61-115. | Zbl
, and ,[15] On randomized one-round communication complexity, in Proc. of 27th STOC (1995) 596-605. | Zbl
, and ,[16] Communication Complexity. Cambridge University Press (1997). | MR | Zbl
and ,[17] 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.
, and ,[18] 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.
, , and ,[19] Lower bounds for randomized read-k-times branching programs, in Proc. of STACS '98, LNCS 1373 (1998) 105-115. | MR
,[20] Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. of Dortmund (1999).
.[21] 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] Graph driven BDDs- a new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. | MR | Zbl
and ,[23] Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. of 19th STOC (1987) 77-82.
,[24] Short monotone formulae for the majority function. J. Algorithms 5 (1984) 363-366. | MR | Zbl
,[25] On the descriptive and algorithmic power of parity ordered binary decision diagrams, in Proc. of STACS '97, LNCS 1200 (1997) 201-212. | MR
,[26] The Complexity of Boolean Functions. Wiley-Teubner (1987). | MR | Zbl
,