Linear codes are hard for oblivious read-once parity branching programs
Identifieur interne : 000528 ( Istex/Corpus ); précédent : 000527; suivant : 000529Linear codes are hard for oblivious read-once parity branching programs
Auteurs : Stasys JuknaSource :
- 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 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><mods:affiliation>Department of Computer Science, University of Trier, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</mods:affiliation></affiliation><affiliation><mods:affiliation>2 Supported by DFG grant Me 1077/10-1.</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jukna@ti.uni-trier.de</mods:affiliation></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></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><mods:affiliation>Department of Computer Science, University of Trier, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</mods:affiliation></affiliation><affiliation><mods:affiliation>2 Supported by DFG grant Me 1077/10-1.</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jukna@ti.uni-trier.de</mods:affiliation></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><istex><corpusName>elsevier</corpusName><author><json:item><name>Stasys Jukna</name><affiliations><json:string>Department of Computer Science, University of Trier, D-54286 Trier, Germany</json:string><json:string>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</json:string><json:string>2 Supported by DFG grant Me 1077/10-1.</json:string><json:string>E-mail: jukna@ti.uni-trier.de</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Computational complexity</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Parity branching programs</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Lower bounds</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Linear codes</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Computer aided design</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><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.</abstract><qualityIndicators><score>2.28</score><pdfVersion>1.2</pdfVersion><pdfPageSize>540 x 684 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>5</keywordCount><abstractCharCount>307</abstractCharCount><pdfWordCount>1752</pdfWordCount><pdfCharCount>9322</pdfCharCount><pdfPageCount>3</pdfPageCount><abstractWordCount>44</abstractWordCount></qualityIndicators><title>Linear codes are hard for oblivious read-once parity branching programs</title><pii><json:string>S0020-0190(99)00027-7</json:string></pii><refBibs><json:item><author><json:item><name>R.E. Bryant</name></json:item></author><host><volume>40</volume><pages><last>213</last><first>205</first></pages><issue>2</issue><author></author><title>IEEE Trans. Comput.</title></host><title>On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication</title></json:item><json:item><author><json:item><name>J. Gergov</name></json:item></author><host><volume>51</volume><pages><last>269</last><first>265</first></pages><author></author><title>Inform. Process. Lett.</title></host><title>Time-space tradeoffs for integer multiplication on various types of input oblivious sequential machines</title></json:item><json:item><author><json:item><name>J. Gergov</name></json:item><json:item><name>Ch. Meinel</name></json:item></author><host><volume>8</volume><pages><last>282</last><first>273</first></pages><author></author><title>Formal Methods in System Design</title></host><title>Mod-2-OBDDs: A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams</title></json:item><json:item><author><json:item><name>S. Jukna</name></json:item></author><host><volume>29</volume><pages><last>83</last><first>75</first></pages><issue>1</issue><author></author><title>RAIRO Theoret. Inform. Appl.</title></host><title>A note on read-k-times branching programs</title></json:item><json:item><author><json:item><name>S. Jukna</name></json:item><json:item><name>A. Razborov</name></json:item></author><host><volume>85</volume><pages><last>238</last><first>223</first></pages><author></author><title>Discrete Appl. Math.</title></host><title>Neither reading few bits twice nor reading illegally helps much</title></json:item><json:item><host><author></author><title>The Theory of Error-Correcting Codes</title></host></json:item><json:item><author><json:item><name>E.A. Okolnishnikova</name></json:item></author><host><volume>51</volume><pages><last>83</last><first>61</first></pages><author></author><title>Metody Diskret. Analiz.</title></host><title>Lower bounds for branching programs computing characteristic functions of binary codes</title></json:item><json:item><author><json:item><name>S. Waack</name></json:item></author><host><author></author><title>Lecture Notes in Computer Sci.</title></host><serie><author></author><title>Proc. 14th Symposium on Theoretical Aspects of Computer Science, STACS'97</title></serie><title>On the descriptive and algorithmic power of parity binary decision diagrams</title></json:item></refBibs><genre><json:string>research-article</json:string></genre><serie><pages><last>212</last><first>201</first></pages><language><json:string>unknown</json:string></language><title>Proc. 14th Symposium on Theoretical Aspects of Computer Science, STACS'97</title></serie><host><volume>69</volume><pii><json:string>S0020-0190(00)X0104-4</json:string></pii><pages><last>269</last><first>267</first></pages><issn><json:string>0020-0190</json:string></issn><issue>6</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Information Processing Letters</title><publicationDate>1999</publicationDate></host><categories><wos><json:string>science</json:string><json:string>computer science, information systems</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>information & communication technologies</json:string><json:string>computation theory & mathematics</json:string></scienceMetrix></categories><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1016/S0020-0190(99)00027-7</json:string></doi><id>C611DFF0B41CE792E368D5DE71CE72C535594AC5</id><score>1.1280771</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/C611DFF0B41CE792E368D5DE71CE72C535594AC5/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/C611DFF0B41CE792E368D5DE71CE72C535594AC5/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/C611DFF0B41CE792E368D5DE71CE72C535594AC5/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Linear codes are hard for oblivious read-once parity branching programs</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1999</date></publicationStmt><notesStmt><note>Communicated by H. Ganzinger</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Linear codes are hard for oblivious read-once parity branching programs</title><author xml:id="author-1"><persName><forename type="first">Stasys</forename><surname>Jukna</surname></persName><email>jukna@ti.uni-trier.de</email><affiliation>Department of Computer Science, University of Trier, D-54286 Trier, Germany</affiliation><affiliation>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</affiliation><affiliation>2 Supported by DFG grant Me 1077/10-1.</affiliation></author></analytic><monogr><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="pISSN">0020-0190</idno><idno type="PII">S0020-0190(00)X0104-4</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="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></monogr><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></fileDesc><profileDesc><creation><date>1999</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Computational complexity</term></item><item><term>Parity branching programs</term></item><item><term>Lower bounds</term></item><item><term>Linear codes</term></item><item><term>Computer aided design</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1999-02-08">Modified</change><change when="1999">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/C611DFF0B41CE792E368D5DE71CE72C535594AC5/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>IPL</jid><aid>99000277</aid><ce:pii>S0020-0190(99)00027-7</ce:pii><ce:doi>10.1016/S0020-0190(99)00027-7</ce:doi><ce:copyright type="unknown" year="1999"></ce:copyright></item-info><head><ce:title>Linear codes are hard for oblivious read-once parity branching programs</ce:title><ce:author-group><ce:author><ce:given-name>Stasys</ce:given-name><ce:surname>Jukna</ce:surname><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup></ce:cross-ref><ce:cross-ref refid="FN1"><ce:sup>2</ce:sup></ce:cross-ref><ce:e-address>jukna@ti.uni-trier.de</ce:e-address></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>Department of Computer Science, University of Trier, D-54286 Trier, Germany</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</ce:textfn></ce:affiliation><ce:footnote id="FN1"><ce:label>2</ce:label><ce:note-para>Supported by DFG grant Me 1077/10-1.</ce:note-para></ce:footnote></ce:author-group><ce:date-received day="17" month="11" year="1998"></ce:date-received><ce:date-revised day="8" month="2" year="1999"></ce:date-revised><ce:miscellaneous>Communicated by H. Ganzinger</ce:miscellaneous><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>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.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Computational complexity</ce:text></ce:keyword><ce:keyword><ce:text>Parity branching programs</ce:text></ce:keyword><ce:keyword><ce:text>Lower bounds</ce:text></ce:keyword><ce:keyword><ce:text>Linear codes</ce:text></ce:keyword><ce:keyword><ce:text>Computer aided design</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Linear codes are hard for oblivious read-once parity branching programs</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Linear codes are hard for oblivious read-once parity branching programs</title></titleInfo><name type="personal"><namePart type="given">Stasys</namePart><namePart type="family">Jukna</namePart><affiliation>Department of Computer Science, University of Trier, D-54286 Trier, Germany</affiliation><affiliation>Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania</affiliation><affiliation>2 Supported by DFG grant Me 1077/10-1.</affiliation><affiliation>E-mail: jukna@ti.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued><dateModified encoding="w3cdtf">1999-02-08</dateModified><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract 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.</abstract><note>Communicated by H. Ganzinger</note><subject><genre>Keywords</genre><topic>Computational complexity</topic><topic>Parity branching programs</topic><topic>Lower bounds</topic><topic>Linear codes</topic><topic>Computer aided design</topic></subject><relatedItem type="host"><titleInfo><title>Information Processing Letters</title></titleInfo><titleInfo type="abbreviated"><title>IPL</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">19990326</dateIssued></originInfo><identifier type="ISSN">0020-0190</identifier><identifier type="PII">S0020-0190(00)X0104-4</identifier><part><date>19990326</date><detail type="volume"><number>69</number><caption>vol.</caption></detail><detail type="issue"><number>6</number><caption>no.</caption></detail><extent unit="issue pages"><start>267</start><end>319</end></extent><extent unit="pages"><start>267</start><end>269</end></extent></part></relatedItem><identifier type="istex">C611DFF0B41CE792E368D5DE71CE72C535594AC5</identifier><identifier type="DOI">10.1016/S0020-0190(99)00027-7</identifier><identifier type="PII">S0020-0190(99)00027-7</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000528 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000528 | 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= Corpus
|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. |  |