Some bounds on multiparty communication complexity of pointer jumping
Identifieur interne : 001788 ( Istex/Curation ); précédent : 001787; suivant : 001789Some bounds on multiparty communication complexity of pointer jumping
Auteurs : Carsten Damm [Allemagne] ; Stasys Jukna [Allemagne] ; Ji Sgall [République tchèque]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a directed layered graph with a starting node and k layers of n nodes, and a single edge from each node to one node from the next layer. The output is the node reached by following k edges from the starting node. In a conservative protocol Player i can see only the node reached by following the first i−1 edges and the edges on the jth layer for each j>i (compared to the general model where he sees edges of all layers except for the ith one). In a one-way protocol, each player communicates only once: first Player 1 writes a message on the blackboard, then Player 2, etc., until the last player gives the answer. The cost is the total number of bits written on the blackboard. Our main results are the following bounds on k-party conservative one-way communication complexity of pointer jumping with k layers: (1) A lower bound of Ω(n/k 2) for any $$k = O(n^{1/3 - \varepsilon } )$$ . This is the first lower bound on multiparty communication complexity that works for more than log n players. (2) Matching upper and lower bounds of Θ(n log(k−1) n) for k≤log* n. No better one-way protocols are known, even if we consider non-conservative ones.
Url:
DOI: 10.1007/3-540-60922-9_52
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001904
Links to Exploration step
ISTEX:F20AB7AE0742F1BAAE2052DF8FCF905A8E6D9EA9Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Some bounds on multiparty communication complexity of pointer jumping</title>
<author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name>
<affiliation wicri:level="1"><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: damm@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Jukna, Stasys" sort="Jukna, Stasys" uniqKey="Jukna S" first="Stasys" last="Jukna">Stasys Jukna</name>
<affiliation wicri:level="1"><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: jukna@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Sgall, Ji" sort="Sgall, Ji" uniqKey="Sgall J" first="Ji" last="Sgall">Ji Sgall</name>
<affiliation wicri:level="1"><mods:affiliation>Mathematical Institute, AV ČR, Žitná 25, 115 67, Praha 1, Czech Republic</mods:affiliation>
<country xml:lang="fr">République tchèque</country>
<wicri:regionArea>Mathematical Institute, AV ČR, Žitná 25, 115 67, Praha 1</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: sgallj@earn.cvut.cz</mods:affiliation>
<country wicri:rule="url">République tchèque</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:F20AB7AE0742F1BAAE2052DF8FCF905A8E6D9EA9</idno>
<date when="1996" year="1996">1996</date>
<idno type="doi">10.1007/3-540-60922-9_52</idno>
<idno type="url">https://api.istex.fr/document/F20AB7AE0742F1BAAE2052DF8FCF905A8E6D9EA9/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001904</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001904</idno>
<idno type="wicri:Area/Istex/Curation">001788</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Some bounds on multiparty communication complexity of pointer jumping</title>
<author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name>
<affiliation wicri:level="1"><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: damm@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Jukna, Stasys" sort="Jukna, Stasys" uniqKey="Jukna S" first="Stasys" last="Jukna">Stasys Jukna</name>
<affiliation wicri:level="1"><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: jukna@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Sgall, Ji" sort="Sgall, Ji" uniqKey="Sgall J" first="Ji" last="Sgall">Ji Sgall</name>
<affiliation wicri:level="1"><mods:affiliation>Mathematical Institute, AV ČR, Žitná 25, 115 67, Praha 1, Czech Republic</mods:affiliation>
<country xml:lang="fr">République tchèque</country>
<wicri:regionArea>Mathematical Institute, AV ČR, Žitná 25, 115 67, Praha 1</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: sgallj@earn.cvut.cz</mods:affiliation>
<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>1996</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">F20AB7AE0742F1BAAE2052DF8FCF905A8E6D9EA9</idno>
<idno type="DOI">10.1007/3-540-60922-9_52</idno>
<idno type="ChapterID">52</idno>
<idno type="ChapterID">Chap52</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 introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a directed layered graph with a starting node and k layers of n nodes, and a single edge from each node to one node from the next layer. The output is the node reached by following k edges from the starting node. In a conservative protocol Player i can see only the node reached by following the first i−1 edges and the edges on the jth layer for each j>i (compared to the general model where he sees edges of all layers except for the ith one). In a one-way protocol, each player communicates only once: first Player 1 writes a message on the blackboard, then Player 2, etc., until the last player gives the answer. The cost is the total number of bits written on the blackboard. Our main results are the following bounds on k-party conservative one-way communication complexity of pointer jumping with k layers: (1) A lower bound of Ω(n/k 2) for any $$k = O(n^{1/3 - \varepsilon } )$$ . This is the first lower bound on multiparty communication complexity that works for more than log n players. (2) Matching upper and lower bounds of Θ(n log(k−1) n) for k≤log* n. No better one-way protocols are known, even if we consider non-conservative ones.</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 001788 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001788 | 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:F20AB7AE0742F1BAAE2052DF8FCF905A8E6D9EA9 |texte= Some bounds on multiparty communication complexity of pointer jumping }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |