Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
Identifieur interne : 001E22 ( Main/Exploration ); précédent : 001E21; suivant : 001E23Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
Auteurs : Jürgen Forster [Allemagne] ; Matthias Krause [Allemagne] ; Satyanarayana V. Lokam [États-Unis] ; Rustam Mubarakzjanov [Allemagne] ; Niels Schmitt [Allemagne] ; Hans Ulrich Simon [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Abstract: Recently, Forster [7] proved a new lower bound on probabilistic communication complexity in terms of the operator norm of the communication matrix. In this paper, we want to exploit the various relations between communication complexity of distributed Boolean functions, geometric questions related to half space representations of these functions, and the computational complexity of these functions in various restricted models of computation. In order to widen the range of applicability of Forster’s bound, we start with the derivation of a generalized lower bound. We present a concrete family of distributed Boolean functions where the generalized bound leads to a linear lower bound on the probabilistic communication complexity (and thus to an exponential lower bound on the number of Euclidean dimensions needed for a successful half space representation), whereas the old bound fails. We move on to a geometric characterization of the well known communication complexity class C-PP in terms of half space representations achieving a large margin. Our characterization hints to a close connection between the bounded error model of probabilistic communication complexity and the area of large margin classification. In the final section of the paper, we describe how our techniques can be used to prove exponential lower bounds on the size of depth-2 threshold circuits (with still some technical restrictions). Similar results can be obtained for read-k-times randomized ordered binary decision diagram and related models.
Url:
DOI: 10.1007/3-540-45294-X_15
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001868
- to stream Istex, to step Curation: 001752
- to stream Istex, to step Checkpoint: 000C26
- to stream Main, to step Merge: 002096
- to stream PascalFrancis, to step Corpus: 000D83
- to stream PascalFrancis, to step Curation: 000153
- to stream PascalFrancis, to step Checkpoint: 000B86
- to stream Main, to step Merge: 002142
- to stream Main, to step Curation: 001E22
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title><author><name sortKey="Forster, Jurgen" sort="Forster, Jurgen" uniqKey="Forster J" first="Jürgen" last="Forster">Jürgen Forster</name></author><author><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name></author><author><name sortKey="Lokam, Satyanarayana V" sort="Lokam, Satyanarayana V" uniqKey="Lokam S" first="Satyanarayana V." last="Lokam">Satyanarayana V. Lokam</name></author><author><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name></author><author><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name></author><author><name sortKey="Simon, Hans Ulrich" sort="Simon, Hans Ulrich" uniqKey="Simon H" first="Hans Ulrich" last="Simon">Hans Ulrich Simon</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7B379D46B45F5700F6B0662AC093E27351FDE0DD</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1007/3-540-45294-X_15</idno><idno type="url">https://api.istex.fr/document/7B379D46B45F5700F6B0662AC093E27351FDE0DD/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001868</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001868</idno><idno type="wicri:Area/Istex/Curation">001752</idno><idno type="wicri:Area/Istex/Checkpoint">000C26</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C26</idno><idno type="wicri:doubleKey">0302-9743:2001:Forster J:relations:between:communication</idno><idno type="wicri:Area/Main/Merge">002096</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:02-0107353</idno><idno type="wicri:Area/PascalFrancis/Corpus">000D83</idno><idno type="wicri:Area/PascalFrancis/Curation">000153</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000B86</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B86</idno><idno type="wicri:doubleKey">0302-9743:2001:Forster J:relations:between:communication</idno><idno type="wicri:Area/Main/Merge">002142</idno><idno type="wicri:Area/Main/Curation">001E22</idno><idno type="wicri:Area/Main/Exploration">001E22</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title><author><name sortKey="Forster, Jurgen" sort="Forster, Jurgen" uniqKey="Forster J" first="Jürgen" last="Forster">Jürgen Forster</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum</wicri:regionArea><wicri:noRegion>44780, Bochum</wicri:noRegion><wicri:noRegion>Bochum</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institut für Informatik, Universität Mannheim, D-68131, Mannheim</wicri:regionArea><wicri:noRegion>68131, Mannheim</wicri:noRegion><wicri:noRegion>Mannheim</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Lokam, Satyanarayana V" sort="Lokam, Satyanarayana V" uniqKey="Lokam S" first="Satyanarayana V." last="Lokam">Satyanarayana V. Lokam</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ</wicri:regionArea><placeName><region type="state">New Jersey</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fakultät für Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum</wicri:regionArea><wicri:noRegion>44780, Bochum</wicri:noRegion><wicri:noRegion>Bochum</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Simon, Hans Ulrich" sort="Simon, Hans Ulrich" uniqKey="Simon H" first="Hans Ulrich" last="Simon">Hans Ulrich Simon</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum</wicri:regionArea><wicri:noRegion>44780, Bochum</wicri:noRegion><wicri:noRegion>Bochum</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2001</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">7B379D46B45F5700F6B0662AC093E27351FDE0DD</idno><idno type="DOI">10.1007/3-540-45294-X_15</idno><idno type="ChapterID">15</idno><idno type="ChapterID">Chap15</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Boolean function</term><term>Communication complexity</term><term>Complexity class</term><term>Computational complexity</term><term>Lower bound</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Borne inférieure</term><term>Classe complexité</term><term>Complexité calcul</term><term>Complexité communication</term><term>Fonction booléenne</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Recently, Forster [7] proved a new lower bound on probabilistic communication complexity in terms of the operator norm of the communication matrix. In this paper, we want to exploit the various relations between communication complexity of distributed Boolean functions, geometric questions related to half space representations of these functions, and the computational complexity of these functions in various restricted models of computation. In order to widen the range of applicability of Forster’s bound, we start with the derivation of a generalized lower bound. We present a concrete family of distributed Boolean functions where the generalized bound leads to a linear lower bound on the probabilistic communication complexity (and thus to an exponential lower bound on the number of Euclidean dimensions needed for a successful half space representation), whereas the old bound fails. We move on to a geometric characterization of the well known communication complexity class C-PP in terms of half space representations achieving a large margin. Our characterization hints to a close connection between the bounded error model of probabilistic communication complexity and the area of large margin classification. In the final section of the paper, we describe how our techniques can be used to prove exponential lower bounds on the size of depth-2 threshold circuits (with still some technical restrictions). Similar results can be obtained for read-k-times randomized ordered binary decision diagram and related models.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>États-Unis</li></country><region><li>New Jersey</li></region></list><tree><country name="Allemagne"><noRegion><name sortKey="Forster, Jurgen" sort="Forster, Jurgen" uniqKey="Forster J" first="Jürgen" last="Forster">Jürgen Forster</name></noRegion><name sortKey="Forster, Jurgen" sort="Forster, Jurgen" uniqKey="Forster J" first="Jürgen" last="Forster">Jürgen Forster</name><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name><name sortKey="Simon, Hans Ulrich" sort="Simon, Hans Ulrich" uniqKey="Simon H" first="Hans Ulrich" last="Simon">Hans Ulrich Simon</name><name sortKey="Simon, Hans Ulrich" sort="Simon, Hans Ulrich" uniqKey="Simon H" first="Hans Ulrich" last="Simon">Hans Ulrich Simon</name></country><country name="États-Unis"><region name="New Jersey"><name sortKey="Lokam, Satyanarayana V" sort="Lokam, Satyanarayana V" uniqKey="Lokam S" first="Satyanarayana V." last="Lokam">Satyanarayana V. Lokam</name></region><name sortKey="Lokam, Satyanarayana V" sort="Lokam, Satyanarayana V" uniqKey="Lokam S" first="Satyanarayana V." last="Lokam">Satyanarayana V. Lokam</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001E22 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001E22 | 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= Exploration
|type= RBID
|clé= ISTEX:7B379D46B45F5700F6B0662AC093E27351FDE0DD
|texte= Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
}}
| This area was generated with Dilib version V0.6.31. |  |