Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
Identifieur interne : 001868 ( Istex/Corpus ); précédent : 001867; suivant : 001869Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
Auteurs : Jürgen Forster ; Matthias Krause ; Satyanarayana V. Lokam ; Rustam Mubarakzjanov ; Niels Schmitt ; Hans Ulrich SimonSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
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
Links to Exploration step
ISTEX:7B379D46B45F5700F6B0662AC093E27351FDE0DDLe 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><affiliation><mods:affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: forster@lmi.ruhr-uni-bochum.de</mods:affiliation></affiliation></author><author><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name><affiliation><mods:affiliation>Institut für Informatik, Universität Mannheim, D-68131, Mannheim, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: krause@th.informatik.uni-mannheim.de</mods:affiliation></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><mods:affiliation>School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: satya@math.ias.edu</mods:affiliation></affiliation></author><author><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name><affiliation><mods:affiliation>Fakultät für Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: rustam@TI.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name><affiliation><mods:affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: nschmitt@lmi.ruhr-uni-bochum.de</mods:affiliation></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><mods:affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: simon@lmi.ruhr-uni-bochum.de</mods:affiliation></affiliation></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></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><mods:affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: forster@lmi.ruhr-uni-bochum.de</mods:affiliation></affiliation></author><author><name sortKey="Krause, Matthias" sort="Krause, Matthias" uniqKey="Krause M" first="Matthias" last="Krause">Matthias Krause</name><affiliation><mods:affiliation>Institut für Informatik, Universität Mannheim, D-68131, Mannheim, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: krause@th.informatik.uni-mannheim.de</mods:affiliation></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><mods:affiliation>School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: satya@math.ias.edu</mods:affiliation></affiliation></author><author><name sortKey="Mubarakzjanov, Rustam" sort="Mubarakzjanov, Rustam" uniqKey="Mubarakzjanov R" first="Rustam" last="Mubarakzjanov">Rustam Mubarakzjanov</name><affiliation><mods:affiliation>Fakultät für Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: rustam@TI.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Schmitt, Niels" sort="Schmitt, Niels" uniqKey="Schmitt N" first="Niels" last="Schmitt">Niels Schmitt</name><affiliation><mods:affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: nschmitt@lmi.ruhr-uni-bochum.de</mods:affiliation></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><mods:affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: simon@lmi.ruhr-uni-bochum.de</mods:affiliation></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></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><istex><corpusName>springer</corpusName><author><json:item><name>Jürgen Forster</name><affiliations><json:string>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</json:string><json:string>E-mail: forster@lmi.ruhr-uni-bochum.de</json:string></affiliations></json:item><json:item><name>Matthias Krause</name><affiliations><json:string>Institut für Informatik, Universität Mannheim, D-68131, Mannheim, Germany</json:string><json:string>E-mail: krause@th.informatik.uni-mannheim.de</json:string></affiliations></json:item><json:item><name>Satyanarayana V. Lokam</name><affiliations><json:string>School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA</json:string><json:string>E-mail: satya@math.ias.edu</json:string></affiliations></json:item><json:item><name>Rustam Mubarakzjanov</name><affiliations><json:string>Fakultät für Informatik, Universität Trier, D-54286, Trier, Germany</json:string><json:string>E-mail: rustam@TI.uni-trier.de</json:string></affiliations></json:item><json:item><name>Niels Schmitt</name><affiliations><json:string>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</json:string><json:string>E-mail: nschmitt@lmi.ruhr-uni-bochum.de</json:string></affiliations></json:item><json:item><name>Hans Ulrich Simon</name><affiliations><json:string>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</json:string><json:string>E-mail: simon@lmi.ruhr-uni-bochum.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><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.</abstract><qualityIndicators><score>7.736</score><pdfVersion>1.3</pdfVersion><pdfPageSize>648 x 864 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1542</abstractCharCount><pdfWordCount>5154</pdfWordCount><pdfCharCount>26474</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>228</abstractWordCount></qualityIndicators><title>Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title><chapterId><json:string>15</json:string><json:string>Chap15</json:string></chapterId><refBibs><json:item><author><json:item><name>N Alon</name></json:item><json:item><name>P Frankl</name></json:item><json:item><name>V Rödl</name></json:item></author><host><pages><last>280</last><first>277</first></pages><author></author><title>Proceedings of the 26th Symposium on Foundations of Computer Science</title><publicationDate>1985</publicationDate></host><title>Geometrical realization of set systems and probabilistic communication complexity</title><publicationDate>1985</publicationDate></json:item><json:item><author><json:item><name>N Alon</name></json:item><json:item><name>W Maass</name></json:item></author><host><volume>37</volume><pages><last>129</last><first>118</first></pages><author></author><title>Journal of Computer and System Sciences</title><publicationDate>1988</publicationDate></host><title>Meanders and their applications in lower bound arguments</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>Rosa,I Arriaga</name></json:item><json:item><name>Santosh Vempala</name></json:item></author><host><pages><last>623</last><first>616</first></pages><author></author><title>Proceedings of the 40'th Annual Symposium on the Foundations of Computer Science</title><publicationDate>1999</publicationDate></host><title>An algorithmic theory of learning: Robust concepts and random projection</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>Nadav Shai Ben-David</name></json:item><json:item><name>Hans,Ulrich Eiron</name></json:item><json:item><name> Simon</name></json:item></author><host><pages><last>401</last><first>385</first></pages><author></author><title>Proceedings of the 14th Annual Workshop on Computational Learning Theory</title><publicationDate>2001</publicationDate></host><title>Limitations of learning via embeddings in euclidean half-spaces</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>Jehoshua Bruck</name></json:item><json:item><name>Roman Smolensky</name></json:item></author><host><pages><last>641</last><first>632</first></pages><author></author><title>Proceedings of the 31st Symposium on Foundations of Computer Science</title><publicationDate>1990</publicationDate></host><title>Polynomial threshold functions, AC 0 functions and spectral norms</title><publicationDate>1990</publicationDate></json:item><json:item><host><author><json:item><name>Nello Christianini</name></json:item><json:item><name>John Shawe-Taylor </name></json:item></author><title>An Introduction to Support Vector Machines</title><publicationDate>2000</publicationDate></host></json:item><json:item><author><json:item><name>Jürgen Forster</name></json:item></author><host><pages><last>106</last><first>100</first></pages><author></author><title>Proceedings of the 16th Annual Conference on Computational Complexity</title><publicationDate>2001</publicationDate></host><title>A linear bound on the unbounded error probabilistic communication complexity</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>Jürgen Forster</name></json:item><json:item><name>Niels Schmitt</name></json:item><json:item><name>Hans,Ulrich Simon</name></json:item></author><host><pages><last>415</last><first>402</first></pages><author></author><title>Proceedings of the 14th Annual Workshop on Computational Learning Theory</title><publicationDate>2001</publicationDate></host><title>Estimating the optimal margins of embeddings in euclidean half spaces</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>A Hajnal</name></json:item><json:item><name>W Maass</name></json:item><json:item><name>P Pudì Ak</name></json:item><json:item><name>M Szegedy</name></json:item><json:item><name>G Turán</name></json:item></author><host><volume>46</volume><pages><last>154</last><first>129</first></pages><author></author><title>Journal of Computer and System Sciences</title><publicationDate>1993</publicationDate></host><title>Threshold circuits of bounded depth</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>Bernd Halstenberg</name></json:item><json:item><name>Rüdiger Reischuk</name></json:item></author><host><volume>22</volume><pages><last>934</last><first>913</first></pages><issue>5</issue><author></author><title>SIAM Journal on Computing</title><publicationDate>1993</publicationDate></host><title>Different modes of communication</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>Matthias Krause</name></json:item></author><host><volume>156</volume><pages><last>117</last><first>99</first></pages><author></author><title>Theoretical Computer Science</title><publicationDate>1996</publicationDate></host><title>Geometric arguments yield better bounds for threshold circuits and distributed computing</title><publicationDate>1996</publicationDate></json:item><json:item><author><json:item><name>Matthias Krause</name></json:item><json:item><name>Pavel Pudlák</name></json:item></author><host><pages><last>57</last><first>48</first></pages><author></author><title>Proceedings of the 25th Annual Symposium on Theory of Computing</title><publicationDate>1993</publicationDate></host><title>On the computational power of depth-2 circuits with threshold and modulo gates</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>Matthias Krause</name></json:item><json:item><name>Stephan Waack</name></json:item></author><host><pages><last>782</last><first>777</first></pages><author></author><title>Proceedings of the 32nd Symposium on Foundations of Computer Science</title><publicationDate>1991</publicationDate></host><title>Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>Ramamohan Paturi</name></json:item><json:item><name>Janos Simon</name></json:item></author><host><volume>33</volume><pages><last>123</last><first>106</first></pages><issue>1</issue><author></author><title>Journal of Computer and System Sciences</title><publicationDate>1986</publicationDate></host><title>Probabilistic communication complexity</title><publicationDate>1986</publicationDate></json:item><json:item><author><json:item><name>Martin Sauerhoff</name></json:item></author><host><pages><last>499</last><first>488</first></pages><author></author><title>Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science</title><publicationDate>1999</publicationDate></host><title>On the size of randomized OBDDs and read-once branching programs for k-stable functions</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>Ingo Wegner</name></json:item></author><host><author></author><title>Monographs on Discrete Mathematics and Applications. SIAM</title><publicationDate>2001</publicationDate></host><title>Branching programs and binary decision diagrams — theory and applications</title><publicationDate>2001</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><title>Lecture Notes in Computer Science</title><copyrightDate>2001</copyrightDate></serie><host><editor><json:item><name>Ramesh Hariharan</name><affiliations><json:string>Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India</json:string><json:string>E-mail: ramesh@csa.iisc.ernet.in</json:string></affiliations></json:item><json:item><name>V. Vinay</name><affiliations><json:string>Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India</json:string><json:string>E-mail: vinay@csa.iisc.ernet.in</json:string></affiliations></json:item><json:item><name>Madhavan Mukund</name><affiliations><json:string>Chennai Mathematical Institute, 92 G.N. Chetty Road, 600 017, Chennai, India</json:string><json:string>E-mail: madhavan@cmi.ac.in</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Programming Languages, Compilers, Interpreters</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item></subject><isbn><json:string>978-3-540-43002-5</json:string></isbn><language><json:string>unknown</json:string></language><title>FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science</title><bookId><json:string>3-540-45294-X</json:string></bookId><volume>2245</volume><pages><last>182</last><first>171</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-45294-2</json:string></eisbn><copyrightDate>2001</copyrightDate><doi><json:string>10.1007/3-540-45294-X</json:string></doi></host><publicationDate>2001</publicationDate><copyrightDate>2001</copyrightDate><doi><json:string>10.1007/3-540-45294-X_15</json:string></doi><id>7B379D46B45F5700F6B0662AC093E27351FDE0DD</id><score>0.2327569</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/7B379D46B45F5700F6B0662AC093E27351FDE0DD/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/7B379D46B45F5700F6B0662AC093E27351FDE0DD/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/7B379D46B45F5700F6B0662AC093E27351FDE0DD/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2001</p></availability><date>2001</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title><author xml:id="author-1"><persName><forename type="first">Jürgen</forename><surname>Forster</surname></persName><email>forster@lmi.ruhr-uni-bochum.de</email><affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Matthias</forename><surname>Krause</surname></persName><email>krause@th.informatik.uni-mannheim.de</email><affiliation>Institut für Informatik, Universität Mannheim, D-68131, Mannheim, Germany</affiliation></author><author xml:id="author-3"><persName><forename type="first">Satyanarayana</forename><surname>Lokam</surname></persName><email>satya@math.ias.edu</email><affiliation>School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA</affiliation></author><author xml:id="author-4"><persName><forename type="first">Rustam</forename><surname>Mubarakzjanov</surname></persName><email>rustam@TI.uni-trier.de</email><affiliation>Fakultät für Informatik, Universität Trier, D-54286, Trier, Germany</affiliation></author><author xml:id="author-5"><persName><forename type="first">Niels</forename><surname>Schmitt</surname></persName><email>nschmitt@lmi.ruhr-uni-bochum.de</email><affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</affiliation></author><author xml:id="author-6"><persName><forename type="first">Hans</forename><surname>Simon</surname></persName><email>simon@lmi.ruhr-uni-bochum.de</email><affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</affiliation></author></analytic><monogr><title level="m">FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science</title><title level="m" type="sub">21st Conference Bangalore, India, December 13–15, 2001 Proceedings</title><idno type="pISBN">978-3-540-43002-5</idno><idno type="eISBN">978-3-540-45294-2</idno><idno type="pISSN">0302-9743</idno><idno type="DOI">10.1007/3-540-45294-X</idno><idno type="book-ID">3-540-45294-X</idno><idno type="book-title-ID">71354</idno><idno type="book-sequence-number">2245</idno><idno type="book-volume-number">2245</idno><idno type="book-chapter-count">28</idno><editor><persName><forename type="first">Ramesh</forename><surname>Hariharan</surname></persName><email>ramesh@csa.iisc.ernet.in</email><affiliation>Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India</affiliation></editor><editor><persName><forename type="first">V.</forename><surname>Vinay</surname></persName><email>vinay@csa.iisc.ernet.in</email><affiliation>Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India</affiliation></editor><editor><persName><forename type="first">Madhavan</forename><surname>Mukund</surname></persName><email>madhavan@cmi.ac.in</email><affiliation>Chennai Mathematical Institute, 92 G.N. Chetty Road, 600 017, Chennai, India</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2001-11-26"></date><biblScope unit="volume">2245</biblScope><biblScope unit="page" from="171">171</biblScope><biblScope unit="page" to="182">182</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>2001</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="series-Id">558</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></fileDesc><profileDesc><creation><date>2001</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I1603X</label><label>I14037</label><label>I16048</label><label>I16021</label><label>I16013</label><label>I17028</label><item><term>Computer Science</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Programming Languages, Compilers, Interpreters</term></item><item><term>Mathematical Logic and Formal Languages</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Discrete Mathematics in Computer Science</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2001-11-26">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/7B379D46B45F5700F6B0662AC093E27351FDE0DD/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" TocLevels="0"><BookID>3-540-45294-X</BookID><BookTitle>FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science</BookTitle><BookSubTitle>21st Conference Bangalore, India, December 13–15, 2001 Proceedings</BookSubTitle><BookVolumeNumber>2245</BookVolumeNumber><BookSequenceNumber>2245</BookSequenceNumber><BookDOI>10.1007/3-540-45294-X</BookDOI><BookTitleID>71354</BookTitleID><BookPrintISBN>978-3-540-43002-5</BookPrintISBN><BookElectronicISBN>978-3-540-45294-2</BookElectronicISBN><BookChapterCount>28</BookChapterCount><BookHistory><OnlineDate><Year>2001</Year><Month>11</Month><Day>26</Day></OnlineDate></BookHistory><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2001</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I1603X" Priority="1" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I14037" Priority="2" Type="Secondary">Programming Languages, Compilers, Interpreters</BookSubject><BookSubject Code="I16048" Priority="3" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I16021" Priority="4" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I16013" Priority="5" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I17028" Priority="6" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Ramesh</GivenName><FamilyName>Hariharan</FamilyName></EditorName><Contact><Email>ramesh@csa.iisc.ernet.in</Email></Contact></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>V.</GivenName><FamilyName>Vinay</FamilyName></EditorName><Contact><Email>vinay@csa.iisc.ernet.in</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Madhavan</GivenName><FamilyName>Mukund</FamilyName></EditorName><Contact><Email>madhavan@cmi.ac.in</Email></Contact></Editor><Affiliation ID="Aff4"><OrgDivision>Department of Computer Science and Automation</OrgDivision><OrgName>Indian Institute of Science</OrgName><OrgAddress><Postcode>560012</Postcode><City>Bangalore</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>Chennai Mathematical Institute</OrgName><OrgAddress><Street>92 G.N. Chetty Road</Street><Postcode>600 017</Postcode><City>Chennai</City><Country>India</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part2"><PartInfo TocLevels="0"><PartID>2</PartID><PartSequenceNumber>2</PartSequenceNumber><PartTitle>Contributed Papers</PartTitle><PartChapterCount>23</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookID>3-540-45294-X</BookID><BookTitle>FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science</BookTitle></PartContext></PartInfo><Chapter ID="Chap15" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>15</ChapterID><ChapterDOI>10.1007/3-540-45294-X_15</ChapterDOI><ChapterSequenceNumber>15</ChapterSequenceNumber><ChapterTitle Language="En">Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</ChapterTitle><ChapterFirstPage>171</ChapterFirstPage><ChapterLastPage>182</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2001</CopyrightYear></ChapterCopyright><ChapterHistory><RegistrationDate><Year>2001</Year><Month>11</Month><Day>25</Day></RegistrationDate><OnlineDate><Year>2001</Year><Month>11</Month><Day>26</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>2</PartID><BookID>3-540-45294-X</BookID><BookTitle>FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Jürgen</GivenName><FamilyName>Forster</FamilyName></AuthorName><Contact><Email>forster@lmi.ruhr-uni-bochum.de</Email></Contact></Author><Author AffiliationIDS="Aff7"><AuthorName DisplayOrder="Western"><GivenName>Matthias</GivenName><FamilyName>Krause</FamilyName></AuthorName><Contact><Email>krause@th.informatik.uni-mannheim.de</Email></Contact></Author><Author AffiliationIDS="Aff8"><AuthorName DisplayOrder="Western"><GivenName>Satyanarayana</GivenName><GivenName>V.</GivenName><FamilyName>Lokam</FamilyName></AuthorName><Contact><Email>satya@math.ias.edu</Email></Contact></Author><Author AffiliationIDS="Aff9"><AuthorName DisplayOrder="Western"><GivenName>Rustam</GivenName><FamilyName>Mubarakzjanov</FamilyName></AuthorName><Contact><Email>rustam@TI.uni-trier.de</Email></Contact></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Niels</GivenName><FamilyName>Schmitt</FamilyName></AuthorName><Contact><Email>nschmitt@lmi.ruhr-uni-bochum.de</Email></Contact></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Hans</GivenName><GivenName>Ulrich</GivenName><FamilyName>Simon</FamilyName></AuthorName><Contact><Email>simon@lmi.ruhr-uni-bochum.de</Email></Contact></Author><Affiliation ID="Aff6"><OrgDivision>Fakultät für Mathematik</OrgDivision><OrgName>Ruhr-Universität Bochum</OrgName><OrgAddress><Postcode>D-44780</Postcode><City>Bochum</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgDivision>Institut für Informatik</OrgDivision><OrgName>Universität Mannheim</OrgName><OrgAddress><Postcode>D-68131</Postcode><City>Mannheim</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgDivision>School of Mathematics</OrgDivision><OrgName>Institute for Advanced Study</OrgName><OrgAddress><Postcode>08540</Postcode><City>Princeton</City><State>NJ</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgDivision>Fakultät für Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>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-<Emphasis Type="Italic">k</Emphasis>-times randomized ordered binary decision diagram and related models.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This work has been supported in part by the ESPRIT Working Group in Neural and Computational Learning II, NeuroCOLT2, No. 27150. The first, fifth, and sixth author was supported by the Deutsche Forschungsgemeinschaft Grant SI498/4-1. The third author was partially supported by NSF Grants CCR-9988359 and DMS- 9729992.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity</title></titleInfo><name type="personal"><namePart type="given">Jürgen</namePart><namePart type="family">Forster</namePart><affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</affiliation><affiliation>E-mail: forster@lmi.ruhr-uni-bochum.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Matthias</namePart><namePart type="family">Krause</namePart><affiliation>Institut für Informatik, Universität Mannheim, D-68131, Mannheim, Germany</affiliation><affiliation>E-mail: krause@th.informatik.uni-mannheim.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Satyanarayana</namePart><namePart type="given">V.</namePart><namePart type="family">Lokam</namePart><affiliation>School of Mathematics, Institute for Advanced Study, 08540, Princeton, NJ, USA</affiliation><affiliation>E-mail: satya@math.ias.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Rustam</namePart><namePart type="family">Mubarakzjanov</namePart><affiliation>Fakultät für Informatik, Universität Trier, D-54286, Trier, Germany</affiliation><affiliation>E-mail: rustam@TI.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Niels</namePart><namePart type="family">Schmitt</namePart><affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</affiliation><affiliation>E-mail: nschmitt@lmi.ruhr-uni-bochum.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Hans</namePart><namePart type="given">Ulrich</namePart><namePart type="family">Simon</namePart><affiliation>Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780, Bochum, Germany</affiliation><affiliation>E-mail: simon@lmi.ruhr-uni-bochum.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2001-11-26</dateIssued><copyrightDate encoding="w3cdtf">2001</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract 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.</abstract><relatedItem type="host"><titleInfo><title>FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science</title><subTitle>21st Conference Bangalore, India, December 13–15, 2001 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Ramesh</namePart><namePart type="family">Hariharan</namePart><affiliation>Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India</affiliation><affiliation>E-mail: ramesh@csa.iisc.ernet.in</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">V.</namePart><namePart type="family">Vinay</namePart><affiliation>Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India</affiliation><affiliation>E-mail: vinay@csa.iisc.ernet.in</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhavan</namePart><namePart type="family">Mukund</namePart><affiliation>Chennai Mathematical Institute, 92 G.N. Chetty Road, 600 017, Chennai, India</affiliation><affiliation>E-mail: madhavan@cmi.ac.in</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2001</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I14037">Programming Languages, Compilers, Interpreters</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic></subject><identifier type="DOI">10.1007/3-540-45294-X</identifier><identifier type="ISBN">978-3-540-43002-5</identifier><identifier type="eISBN">978-3-540-45294-2</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="BookTitleID">71354</identifier><identifier type="BookID">3-540-45294-X</identifier><identifier type="BookChapterCount">28</identifier><identifier type="BookVolumeNumber">2245</identifier><identifier type="BookSequenceNumber">2245</identifier><identifier type="PartChapterCount">23</identifier><part><date>2001</date><detail type="part"><title>Contributed Papers</title></detail><detail type="volume"><number>2245</number><caption>vol.</caption></detail><extent unit="pages"><start>171</start><end>182</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2001</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></relatedItem><identifier type="istex">7B379D46B45F5700F6B0662AC093E27351FDE0DD</identifier><identifier type="DOI">10.1007/3-540-45294-X_15</identifier><identifier type="ChapterID">15</identifier><identifier type="ChapterID">Chap15</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2001</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></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 001868 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001868 | 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:7B379D46B45F5700F6B0662AC093E27351FDE0DD
|texte= Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
}}
| This area was generated with Dilib version V0.6.31. |  |