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

Authors
Jukna, S
Citation
S. Jukna, Linear codes are hard for oblivious read-once parity branching programs, INF PROCESS, 69(6), 1999, pp. 267-269
Citations number
8
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
69
Issue
6
Year of publication
1999
Pages
267 - 269
Database
ISI
SICI code
0020-0190(19990326)69:6<267:LCAHFO>2.0.ZU;2-A
Abstract
We show that the characteristic functions of linear codes are exponentially hard for the model of oblivious read-once branching programs with parity a ccepting mode, known also as Parity OBDDs. The proof is extremely simple, a nd employs a particular combinatorial property of linear codes-their univer sality. (C) 1999 Published by Elsevier Science B.V. All rights reserved.