Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 37, Issue: 1, page 51-66
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topReferences
top- M. Ajtai, A non-linear time lower bound for boolean branching programs, in Proc. of 40th FOCS (1999) 60-70.
- P. Beame, M. Saks, X. Sun and E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, in Proc. of 41st FOCS (2000) 169-179.
- P. Beame and E. Vee, Time-space trade-offs, multiparty communication complexity, and nearest neighbor problems, in Proc. of 34th STOC (2002) 688-697.
- B. Bollig, Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO: Theoret. Informatics Appl.35 (2001) 149-162.
- B. Bollig, St. Waack and P. Woelfel, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, in Proc. of 2nd IFIP International Conference on Theoretical Computer Science (2002) 83-94.
- B. Bollig and P. Woelfel, A lower bound technique for nondeterministic graph-driven read-once branching programs and its applications, in Proc. of MFCS 2002. Springer, Lecture Notes in Comput. Sci. 2420 (2002) 131-142.
- A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Comput. Complexity3 (1993) 1-18.
- H. Brosenne, M. Homeister and St. Waack, Graph-driven free parity BDDs: Algorithms and lower bounds, in Proc. of MFCS. Springer, Lecture Notes in Comput. Sci. 2136 (2001) 212-223.
- R.E. Bryant, Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput.35 (1986) 677-691.
- J. Gergov and C. Meinel, Frontiers of feasible and probabilistic feasible boolean manipulation with branching programs, in Proc. of STACS. Springer, Lecture Notes in Comput. Sci. 665 (1993) 576-585.
- J. Gergov and C. Meinel, Efficient boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput.43 (1994) 1197-1209.
- J. Hromkovic, Communication Complexity and Parallel Computing. Springer (1997).
- M. Krause, BDD-based cryptanalysis of keystream generators, in Proc. of EUROCRYT (2002) 222-237.
- E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).
- J. Jain, J. Bitner, D.S. Fussell and J.A. Abraham, Functional partitioning for verification and related problems. Brown/MIT VLSI Conference (1992) 210-226.
- E.I. Nechiporuk, On a boolean function. Soviet Math. Dokl.7 (1966) 999-1000.
- A.A. Razborov, Lower bounds for deterministic and nondeterministic branching programs, in Proc. of FCT. Springer, Lecture Notes in Comput. Sci. 529 (1991) 47-60.
- P. Savický and D. Sieling, A hierarchy result for read-once branching programs with restricted parity nondeterminism, in Proc. of 25th MFCS. Springer, Lecture Notes in Comput. Sci. 1893 (2000) 650-659.
- P. Savický and S. Zák, A read-once lower bound and a (1, +k)-hierarchy for branching programs. Theoret. Comput. Sci.238 (2000) 347-362.
- D. Sieling and I. Wegener, I. (1995). Graph driven BDDs - A new data structure for boolean functions. Theoret. Comput. Sci.141 (1995) 283-310.
- D. Sieling and I. Wegener, A comparison of free BDDs and transformed BDDs. Formal Meth. System Design19 (2001) 223-236.
- J. Thathachar, On separating the read-k-times branching program hierarchy, in Proc. of 30th Ann. ACM Symposium on Theory of Computing (STOC) (1998) 653-662.
- I. Wegener, The Complexity of boolean Functions. Wiley-Teubner (1987).
- I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000).
- P. Woelfel, A lower bound technique for restricted branching programs and applications, in Proc. of 19th STACS. Springer, Lecture Notes in Comput. Sci. 2285 (2002) 431-442.