Linear codes are hard for oblivious read-once parity branching programs

被引：5

作者：

Jukna, S ^{[1
]}

机构：

[1] Univ Trier, Dept Comp Sci, D-54286 Trier, Germany

[2] Inst Math & Informat, LT-2600 Vilnius, Lithuania

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 06期

关键词：

computational complexity; parity branching programs; lower bounds; linear codes; computer aided design;

D O I：

10.1016/S0020-0190(99)00027-7

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that the characteristic functions of linear codes are exponentially hard for the model of oblivious read-once branching programs with parity accepting mode, known also as Parity OBDDs. The proof is extremely simple, and employs a particular combinatorial property of linear codes-their universality. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：267 / 269

页数：3

共 8 条

[1] ON THE COMPLEXITY OF VLSI IMPLEMENTATIONS AND GRAPH REPRESENTATIONS OF BOOLEAN FUNCTIONS WITH APPLICATION TO INTEGER MULTIPLICATION [J].