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. | ![]() |