On branching programs with bounded uncertainty
Identifieur interne : 002676 ( Main/Merge ); précédent : 002675; suivant : 002677On branching programs with bounded uncertainty
Auteurs : Stasys Jukna [Allemagne, Lituanie] ; Stanislav Žák [République tchèque]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1998.
Abstract
Abstract: We propose an information-theoretic approach to proving lower bounds on the size of branching programs (b.p.). The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during various stages of the computation. We first demonstrate the approach for read-once b.p. Then we introduce a strictly larger class of so-called ‘gentle’ b.p. and, using the suggested approach, prove that some explicit Boolean functions, including the Clique function and a particular Pointer function (which belongs to AC0), cannot be computed by gentle program of polynomial size. These lower bounds are new since explicit functions, which are known to be hard for all previously considered restricted classes of b.p. (like (1, + s)-b.p. or syntactic read-k-times b.p.) can be easily computed by gentle b.p. of polynomial size.
Url:
DOI: 10.1007/BFb0055059
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001420
- to stream Istex, to step Curation: 001308
- to stream Istex, to step Checkpoint: 000E58
Links to Exploration step
ISTEX:E8111076A0BC84A8CB1DA5EAC6AB57B99FC69969Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On branching programs with bounded uncertainty</title><author><name sortKey="Jukna, Stasys" sort="Jukna, Stasys" uniqKey="Jukna S" first="Stasys" last="Jukna">Stasys Jukna</name></author><author><name sortKey="Zak, Stanislav" sort="Zak, Stanislav" uniqKey="Zak S" first="Stanislav" last="Žák">Stanislav Žák</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:E8111076A0BC84A8CB1DA5EAC6AB57B99FC69969</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/BFb0055059</idno><idno type="url">https://api.istex.fr/document/E8111076A0BC84A8CB1DA5EAC6AB57B99FC69969/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001420</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001420</idno><idno type="wicri:Area/Istex/Curation">001308</idno><idno type="wicri:Area/Istex/Checkpoint">000E58</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E58</idno><idno type="wicri:doubleKey">0302-9743:1998:Jukna S:on:branching:programs</idno><idno type="wicri:Area/Main/Merge">002676</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On branching programs with bounded uncertainty</title><author><name sortKey="Jukna, Stasys" sort="Jukna, Stasys" uniqKey="Jukna S" first="Stasys" last="Jukna">Stasys Jukna</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, University of Trier, D-54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Lituanie</country><wicri:regionArea>Institute of Mathematics, Akademijos 4, LT-2600, Vilnius</wicri:regionArea><wicri:noRegion>Vilnius</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Zak, Stanislav" sort="Zak, Stanislav" uniqKey="Zak S" first="Stanislav" last="Žák">Stanislav Žák</name><affiliation wicri:level="1"><country xml:lang="fr">République tchèque</country><wicri:regionArea>Institute of Computer Science, Academy of Sciences, Pod vodárenskou vĚŽí 2, 182 00, Prague 8</wicri:regionArea><placeName><settlement type="city">Prague</settlement><region type="région" nuts="2">Bohême centrale</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1998</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">E8111076A0BC84A8CB1DA5EAC6AB57B99FC69969</idno><idno type="DOI">10.1007/BFb0055059</idno><idno type="ChapterID">24</idno><idno type="ChapterID">Chap24</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We propose an information-theoretic approach to proving lower bounds on the size of branching programs (b.p.). The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during various stages of the computation. We first demonstrate the approach for read-once b.p. Then we introduce a strictly larger class of so-called ‘gentle’ b.p. and, using the suggested approach, prove that some explicit Boolean functions, including the Clique function and a particular Pointer function (which belongs to AC0), cannot be computed by gentle program of polynomial size. These lower bounds are new since explicit functions, which are known to be hard for all previously considered restricted classes of b.p. (like (1, + s)-b.p. or syntactic read-k-times b.p.) can be easily computed by gentle b.p. of polynomial size.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002676 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002676 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:E8111076A0BC84A8CB1DA5EAC6AB57B99FC69969
|texte= On branching programs with bounded uncertainty
}}
| This area was generated with Dilib version V0.6.31. |  |