UnivTrevesV1, PascalFrancis, Corpus, bibRecord, 000D83

Relations between communication complexity, linear arrangements, and computational complexity

Identifieur interne : 000D83 ( PascalFrancis/Corpus ); précédent : 000D82; suivant : 000D84

Relations between communication complexity, linear arrangements, and computational complexity

Auteurs : Jürgen Forster ; Matthias Krause ; Satyanarayana V. Lokam ; Rustam Mubarakzjanov ; Niels Schmitt ; Hans Ulrich Simon

Source :

Lecture notes in computer science [ 0302-9743 ] ; 2001.

RBID : Pascal:02-0107353

Descripteurs français

Pascal (Inist)
- Complexité calcul, Complexité communication, Classe complexité, Borne inférieure, Fonction booléenne.

English descriptors

KwdEn :
- Boolean function, Communication complexity, Complexity class, Computational complexity, Lower bound.

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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0302-9743`
A05				`@2 2245`
A08	`01`	`1`	`ENG`	`@1 Relations between communication complexity, linear arrangements, and computational complexity`
A09	`01`	`1`	`ENG`	`@1 FST TCS 2001 : foundations of software technology and theoretical computer science : Bangalore, 13-15 december 2001`
A11	`01`	`1`		`@1 FORSTER (Jürgen)`
A11	`02`	`1`		`@1 KRAUSE (Matthias)`
A11	`03`	`1`		`@1 LOKAM (Satyanarayana V.)`
A11	`04`	`1`		`@1 MUBARAKZJANOV (Rustam)`
A11	`05`	`1`		`@1 SCHMITT (Niels)`
A11	`06`	`1`		`@1 SIMON (Hans Ulrich)`
A12	`01`	`1`		`@1 HARIHARAN (Ramesh) @9 ed.`
A12	`02`	`1`		`@1 MUKUND (Madhavan) @9 ed.`
A12	`03`	`1`		`@1 VINAY (V.) @9 ed.`
A14	`01`			`@1 Fakultät für Mathematik, Ruhr-Universität Bochum @2 44780 Bochum @3 DEU @Z 1 aut. @Z 5 aut. @Z 6 aut.`
A14	`02`			`@1 Institut für Informatik, Universität Mannheim @2 68131 Mannheim @3 DEU @Z 2 aut.`
A14	`03`			`@1 School of Mathematics, Institute for Advanced Study @2 Princeton, NJ 08540 @3 USA @Z 3 aut.`
A14	`04`			`@1 Fakultät für Informatik, Universität Trier @2 54286 Trier @3 DEU @Z 4 aut.`
A18	`01`	`1`		`@1 Indian Association for Research in Computing Sciences @3 IND @9 patr.`
A20				`@1 171-182`
A21				`@1 2001`
A23	`01`			`@0 ENG`
A26	`01`			`@0 3-540-43002-4`
A43	`01`			`@1 INIST @2 16343 @5 354000097058320150`
A44				`@0 0000 @1 © 2002 INIST-CNRS. All rights reserved.`
A45				`@0 16 ref.`
A47	`01`	`1`		`@0 02-0107353`
A60				`@1 P @2 C`
A61				`@0 A`
A64	`01`	`1`		`@0 Lecture notes in computer science`
A66	`01`			`@0 DEU`
C01	`01`		`ENG`	@0 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.
C02	`01`	`X`		`@0 001D02A05`
C03	`01`	`X`	`FRE`	`@0 Complexité calcul @5 02`
C03	`01`	`X`	`ENG`	`@0 Computational complexity @5 02`
C03	`01`	`X`	`SPA`	`@0 Complejidad computación @5 02`
C03	`02`	`3`	`FRE`	`@0 Complexité communication @5 03`
C03	`02`	`3`	`ENG`	`@0 Communication complexity @5 03`
C03	`03`	`X`	`FRE`	`@0 Classe complexité @5 04`
C03	`03`	`X`	`ENG`	`@0 Complexity class @5 04`
C03	`03`	`X`	`SPA`	`@0 Clase complejidad @5 04`
C03	`04`	`X`	`FRE`	`@0 Borne inférieure @5 11`
C03	`04`	`X`	`ENG`	`@0 Lower bound @5 11`
C03	`04`	`X`	`SPA`	`@0 Cota inferior @5 11`
C03	`05`	`X`	`FRE`	`@0 Fonction booléenne @5 12`
C03	`05`	`X`	`ENG`	`@0 Boolean function @5 12`
C03	`05`	`X`	`SPA`	`@0 Función booliana @5 12`
N21				`@1 056`
N82				`@1 PSI`

A30	`01`	`1`	`ENG`	`@1 International conference on the foundations of software technology and theoretical computer science @2 21 @3 Bangalore IND @4 2001-12-13`

Format Inist (serveur)

NO :	PASCAL 02-0107353 INIST
ET :	Relations between communication complexity, linear arrangements, and computational complexity
AU :	FORSTER (Jürgen); KRAUSE (Matthias); LOKAM (Satyanarayana V.); MUBARAKZJANOV (Rustam); SCHMITT (Niels); SIMON (Hans Ulrich); HARIHARAN (Ramesh); MUKUND (Madhavan); VINAY (V.)
AF :	Fakultät für Mathematik, Ruhr-Universität Bochum/44780 Bochum/Allemagne (1 aut., 5 aut., 6 aut.); Institut für Informatik, Universität Mannheim/68131 Mannheim/Allemagne (2 aut.); School of Mathematics, Institute for Advanced Study/Princeton, NJ 08540/Etats-Unis (3 aut.); Fakultät für Informatik, Universität Trier/54286 Trier/Allemagne (4 aut.)
DT :	Publication en série; Congrès; Niveau analytique
SO :	Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2001; Vol. 2245; Pp. 171-182; Bibl. 16 ref.
LA :	Anglais
EA :	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.
CC :	001D02A05
FD :	Complexité calcul; Complexité communication; Classe complexité; Borne inférieure; Fonction booléenne
ED :	Computational complexity; Communication complexity; Complexity class; Lower bound; Boolean function
SD :	Complejidad computación; Clase complejidad; Cota inferior; Función booliana
LO :	INIST-16343.354000097058320150
ID :	02-0107353

Links to Exploration step

Pascal:02-0107353

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">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><inist:fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name>
<affiliation><inist:fA14 i1="02"><s1>Institut für Informatik, Universität Mannheim</s1>
<s2>68131 Mannheim</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</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><inist:fA14 i1="03"><s1>School of Mathematics, Institute for Advanced Study</s1>
<s2>Princeton, NJ 08540</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name>
<affiliation><inist:fA14 i1="04"><s1>Fakultät für Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name>
<affiliation><inist:fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</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><inist:fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">02-0107353</idno>
<date when="2001">2001</date>
<idno type="stanalyst">PASCAL 02-0107353 INIST</idno>
<idno type="RBID">Pascal:02-0107353</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000D83</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">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><inist:fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name>
<affiliation><inist:fA14 i1="02"><s1>Institut für Informatik, Universität Mannheim</s1>
<s2>68131 Mannheim</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</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><inist:fA14 i1="03"><s1>School of Mathematics, Institute for Advanced Study</s1>
<s2>Princeton, NJ 08540</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name>
<affiliation><inist:fA14 i1="04"><s1>Fakultät für Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name>
<affiliation><inist:fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</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><inist:fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2001">2001</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<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>Complexité calcul</term>
<term>Complexité communication</term>
<term>Classe complexité</term>
<term>Borne inférieure</term>
<term>Fonction booléenne</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01>
<fA05><s2>2245</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>Relations between communication complexity, linear arrangements, and computational complexity </s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>FST TCS 2001 : foundations of software technology and theoretical computer science : Bangalore, 13-15 december 2001</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>FORSTER (Jürgen)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>KRAUSE (Matthias)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>LOKAM (Satyanarayana V.)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>MUBARAKZJANOV (Rustam)</s1>
</fA11>
<fA11 i1="05" i2="1"><s1>SCHMITT (Niels)</s1>
</fA11>
<fA11 i1="06" i2="1"><s1>SIMON (Hans Ulrich)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>HARIHARAN (Ramesh)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="02" i2="1"><s1>MUKUND (Madhavan)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="03" i2="1"><s1>VINAY (V.)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>Fakultät für Mathematik, Ruhr-Universität Bochum</s1>
<s2>44780 Bochum</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Institut für Informatik, Universität Mannheim</s1>
<s2>68131 Mannheim</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>School of Mathematics, Institute for Advanced Study</s1>
<s2>Princeton, NJ 08540</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="04"><s1>Fakultät für Informatik, Universität Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>4 aut.</sZ>
</fA14>
<fA18 i1="01" i2="1"><s1>Indian Association for Research in Computing Sciences</s1>
<s3>IND</s3>
<s9>patr.</s9>
</fA18>
<fA20><s1>171-182</s1>
</fA20>
<fA21><s1>2001</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA26 i1="01"><s0>3-540-43002-4</s0>
</fA26>
<fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000097058320150</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2002 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>16 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>02-0107353</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01"><s0>DEU</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Complexité calcul</s0>
<s5>02</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Computational complexity</s0>
<s5>02</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Complejidad computación</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="3" l="FRE"><s0>Complexité communication</s0>
<s5>03</s5>
</fC03>
<fC03 i1="02" i2="3" l="ENG"><s0>Communication complexity</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Classe complexité</s0>
<s5>04</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Complexity class</s0>
<s5>04</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Clase complejidad</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Borne inférieure</s0>
<s5>11</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Lower bound</s0>
<s5>11</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Cota inferior</s0>
<s5>11</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Fonction booléenne</s0>
<s5>12</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Boolean function</s0>
<s5>12</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Función booliana</s0>
<s5>12</s5>
</fC03>
<fN21><s1>056</s1>
</fN21>
<fN82><s1>PSI</s1>
</fN82>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>International conference on the foundations of software technology and theoretical computer science</s1>
<s2>21</s2>
<s3>Bangalore IND</s3>
<s4>2001-12-13</s4>
</fA30>
</pR>
</standard>
<server><NO>PASCAL 02-0107353 INIST</NO>
<ET>Relations between communication complexity, linear arrangements, and computational complexity</ET>
<AU>FORSTER (Jürgen); KRAUSE (Matthias); LOKAM (Satyanarayana V.); MUBARAKZJANOV (Rustam); SCHMITT (Niels); SIMON (Hans Ulrich); HARIHARAN (Ramesh); MUKUND (Madhavan); VINAY (V.)</AU>
<AF>Fakultät für Mathematik, Ruhr-Universität Bochum/44780 Bochum/Allemagne (1 aut., 5 aut., 6 aut.); Institut für Informatik, Universität Mannheim/68131 Mannheim/Allemagne (2 aut.); School of Mathematics, Institute for Advanced Study/Princeton, NJ 08540/Etats-Unis (3 aut.); Fakultät für Informatik, Universität Trier/54286 Trier/Allemagne (4 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2001; Vol. 2245; Pp. 171-182; Bibl. 16 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02A05</CC>
<FD>Complexité calcul; Complexité communication; Classe complexité; Borne inférieure; Fonction booléenne</FD>
<ED>Computational complexity; Communication complexity; Complexity class; Lower bound; Boolean function</ED>
<SD>Complejidad computación; Clase complejidad; Cota inferior; Función booliana</SD>
<LO>INIST-16343.354000097058320150</LO>
<ID>02-0107353</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000D83 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000D83 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:02-0107353
   |texte=   Relations between communication complexity, linear arrangements, and computational complexity 
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

Relations between communication complexity, linear arrangements, and computational complexity

Relations between communication complexity, linear arrangements, and computational complexity

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri