A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

被引：4

作者：

Bollig, B ^{[1
]}

Woelfel, P ^{[1
]}

机构：

[1] Univ Dortmund, FB Informat, D-44221 Dortmund, Germany

来源：

THEORY OF COMPUTING SYSTEMS | 2005年 / 38卷 / 06期

关键词：

Computational Mathematic; Program Model; Communication Complexity; Exponential Complexity; Polynomial Size;

D O I：

10.1007/s00224-004-1130-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a new lower bound technique for a restricted branching program model, namely for nondeterministic graph-driven read-once branching, programs (g.d.-BPls). The technique is derived by drawing a connection between omega-nondeterministic g.d.-BP Is and omega-nondeterininistic communication complexity (for the nondeterministic acceptance modes omega is an element of {boolean OR, boolean AND, +}). We apply the technique in order to prove an exponential lower bound for integer multiplication for omega-nondeterministic well-structured g.d.-BP1s. (For omega = + an exponential lower bound was already obtained in [5] by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined function which can be represented by polynomial size omega-nondeterministic BP1s that it has exponential complexity in the omega-nondeterministic well-structured g.d.-BP1 model for omega is an element of {boolean OR, +}. This answers an open question from Brosenne et al. [7], whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant.

引用

页码：671 / 685

页数：15

共 24 条

[1]

Ajtai M., A non-linear time lower bound for boolean branching programs, Proc. of 40th FOCS, pp. 60-70, (1999)

[2]

Beame P., Saks M., Sun X., Vee E., Super-linear time-space tradeoff lower bounds for randomized computation, Proc. of 41st FOCS, pp. 169-179, (2000)

[3]

Beame P., Vee E., Time-space tradeoffs, multiparty communication complexity, and nearest neighbor problems, Proc. of 34th ACM STOC, pp. 688-697, (2002)

[4]

Bollig B., Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication, RAIRO, 35, pp. 149-162, (2001)

[5]

Bollig B., Waack S., Woelfel P., Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, Proc. of 2nd TCS, pp. 83-94, (2002)

[6]

Bollig B., Woelfel P., A read-once branching program lower bound of Ω (2<sup>n/4</sup>) for integer multiplication using universal hashing, Proc. of 33rd ACM STOC, pp. 419-1124, (2001)

[7]

Brosenne H., Homeister M., Waack S., Graph-driven free parity BDDs: Algorithms and lower bounds, Proc. of 26th MFCS, pp. 212-223, (2001)

[8]

Bryant R.E., Graph-based algorithms for boolean function manipulation, IEEE Trans. Comput., C-35, pp. 677-691, (1986)

[9]

Bryant R.E., On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication, IEEE Trans. Comput., 40, pp. 205-213, (1991)

[10]

Damm C., Krause M., Meinel C., Waack S., Separating counting communication complexity classes, Proc. of 9th STACS, pp. 281-292, (1992)

← 1 2 3 →