Lower bounds for restricted read-once parity branching programs
Pages 1 - 14
Abstract
We prove the first lower bounds for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. Namely, sums of k graph-driven ⊕ BP1s with polynomial size graph-orderings are under consideration. We prove lower bounds for the characteristic function of linear codes. We generalize a lower bound by Savický and Sieling (see [P. Savický, D. Sieling, A hierarchy result for read-once Branching programs with restricted parity nondeterminism, Theoret. Comput. Sci. 340 (2005) 594-605]) and recent results on graph-driven parity branching programs.
References
[1]
{1} B. Bollig, S. Waack, P. Woelfel, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, in: Proc. Second IFIP, 2002.]]
[2]
{2} B. Bollig, P. Woelfel, A lower bound technique for nondeterministic graph-driven read-once branching programs and its applications, in: Proc. 27th MFCS, Lecture Notes in Computer Science, Vol. 2420, Springer, Berlin, 2002.]]
[3]
{3} A. Borodin, A. Razborov, R. Smolensky, On lower bounds for read-k-times branching programs, Comput. Complexity 3 (1993) 1-18.]]
[4]
{4} H. Brosenne, M. Homeister, S. Waack, Graph-driven free parity BDDs: Algorithms and lower bounds, in: Proc. 26th MFCS, Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, 2001, pp. 212-223.]]
[5]
{5} H. Brosenne, M. Homeister, S. Waack, Lower bounds for general graph-driven read-once parity branching programs, in: Proc. 28th MFCS, Lecture Notes in Computer Science, Vol. 2747, Springer, Berlin, 2003, pp. 290-299.]]
[6]
{6} R.E. Bryant, Symbolic manipulation of Boolean functions using a graphical representation, in: Proc. 22nd DAC, IEEE, Piscastaway, NJ, 1985, pp. 688-694.]]
[7]
{7} R.E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput. 35 (1986) 677-691.]]
[8]
{8} R.E. Bryant, On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication, IEEE Trans. Comput. 40 (1991) 205-213.]]
[9]
{9} J. Gergov, C. Meinel, Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs, in: Proc. 10th STACS, Lecture Notes in Computer Science, Vol. 665, Springer, Berlin, 1993, pp. 576-585.]]
[10]
{10} J. Gergov, C. Meinel, Mod-2-OBDDs--a data structure that generalizes exor-sum-of-products and ordered binary decision diagrams, Formal Methods System Design 8 (1996) 273-282.]]
[11]
{11} M. Homeister, On well-structured parity-FBDDs, in: Proc. Sixth Internat. Symp. on Representations and Methodology of Future Computing Technology, 2003.]]
[12]
{12} S. Jukna, Linear codes are hard for oblivious read-once parity branching programs, Inform. Process. Lett. 69 (1999) 267-269.]]
[13]
{13} S. Jukna, Combinatorics of Finite Computations--The Lower Bounds Problem, Habilitationsschrift, University of Trier, 1999.]]
[14]
{14} S. Jukna, The graph of integer multiplication is hard for read-k-times networks, Technical Report 95-10, University of Trier, 1995.]]
[15]
{15} E.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, Elsevier, Amsterdam, 1977.]]
[16]
{16} C. Meinel, H. Sack, Heuristics for ⊕-OBDDs, in: Proc. IEEE/ACM Internat. Workshop of Logic and Synthesis, 2001, pp. 304-309.]]
[17]
{17} C. Meinel, H. Sack, Improving XOR-node placements for ⊕-OBDDs, in: Proc. Fifth Internat. Workshop of Reed-Muller Expansion in Circuit Design, 2001, pp. 51-55.]]
[18]
{18} E.I. Necbiporuk, A Boolean function, Sov. Math. Dokl. 7 (1966) 999-1000.]]
[19]
{19} H. Sack, Improving the power of OBDDs by integrating parity nodes, Ph.D. Thesis, University of Trier, 2001.]]
[20]
{20} P. Savicý, D. Sieling, A hierarchy result for read-once Branching programs with restricted parity nondeterminism, Theoret. Comput. Sci. 340 (2005) 594-605.]]
[21]
{21} D. Sieling, Lower bounds for linear transformed OBDDs and FBDDs, in: Proc. FSTTCS, Lecture Notes in Computer Science, Vol. 1738, Springer, Berlin, 1999, pp. 356-368.]]
[22]
{22} D. Sieling, I. Wegener, Graph driven BDDs--a new data structure for Boolean functions, Theoret. Comput. Sci. 141 (1995) 238-310.]]
[23]
{23} S. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams, Inform. and Comput. 166 (2001) 61-70.]]
[24]
{24} I. Wegener, Branching Programs and Binary Decision Diagrams--Theory and Applications, SIAM Monographs, SIAM, Philadelphia, PA, 2000.]]
Index Terms
- Lower bounds for restricted read-once parity branching programs
Recommendations
Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs have been studied intensively. Exponential lower bounds for read-once branching programs are known for a long time. On the other ...
Kernelization Lower Bounds Through Colors and IDs
In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size ...
Pebbling, Entropy, and Branching Program Size Lower Bounds
We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al. [2012]. Proving a superpolynomial lower bound for the size of nondeterministic thrifty branching ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 14 August 2006
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025