Linear codes are hard for oblivious read-once parity branching programs
Identifieur interne : 000501 ( Istex/Curation ); précédent : 000500; suivant : 000502Linear codes are hard for oblivious read-once parity branching programs
Auteurs : Stasys Jukna [Allemagne, Lituanie]Source :
- Information Processing Letters [ 0020-0190 ] ; 1999.
Abstract
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.
Url:
DOI: 10.1016/S0020-0190(99)00027-7
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000528
Links to Exploration step
ISTEX:C611DFF0B41CE792E368D5DE71CE72C535594AC5Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Linear codes are hard for oblivious read-once parity branching programs</title><author><name sortKey="Jukna, Stasys" sort="Jukna, Stasys" uniqKey="Jukna S" first="Stasys" last="Jukna">Stasys Jukna</name><affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of Trier, D-54286 Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, University of Trier, D-54286 Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</mods:affiliation><country xml:lang="fr">Lituanie</country><wicri:regionArea>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius</wicri:regionArea></affiliation><affiliation><mods:affiliation>2 Supported by DFG grant Me 1077/10-1.</mods:affiliation><wicri:noCountry code="no comma">2 Supported by DFG grant Me 1077/10-1.</wicri:noCountry></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: jukna@ti.uni-trier.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:C611DFF0B41CE792E368D5DE71CE72C535594AC5</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0020-0190(99)00027-7</idno><idno type="url">https://api.istex.fr/document/C611DFF0B41CE792E368D5DE71CE72C535594AC5/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000528</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000528</idno><idno type="wicri:Area/Istex/Curation">000501</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Linear codes are hard for oblivious read-once parity branching programs</title><author><name sortKey="Jukna, Stasys" sort="Jukna, Stasys" uniqKey="Jukna S" first="Stasys" last="Jukna">Stasys Jukna</name><affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of Trier, D-54286 Trier, Germany</mods:affiliation><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, University of Trier, D-54286 Trier</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</mods:affiliation><country xml:lang="fr">Lituanie</country><wicri:regionArea>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius</wicri:regionArea></affiliation><affiliation><mods:affiliation>2 Supported by DFG grant Me 1077/10-1.</mods:affiliation></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: jukna@ti.uni-trier.de</mods:affiliation><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="ISSN">0020-0190</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">69</biblScope><biblScope unit="issue">6</biblScope><biblScope unit="page" from="267">267</biblScope><biblScope unit="page" to="269">269</biblScope></imprint><idno type="ISSN">0020-0190</idno></series><idno type="istex">C611DFF0B41CE792E368D5DE71CE72C535594AC5</idno><idno type="DOI">10.1016/S0020-0190(99)00027-7</idno><idno type="PII">S0020-0190(99)00027-7</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0020-0190</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000501 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000501 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:C611DFF0B41CE792E368D5DE71CE72C535594AC5
|texte= Linear codes are hard for oblivious read-once parity branching programs
}}
| This area was generated with Dilib version V0.6.31. |  |