The “log rank” conjecture for modular communication complexity
Identifieur interne : 001395 ( Istex/Corpus ); précédent : 001394; suivant : 001396The “log rank” conjecture for modular communication complexity
Auteurs : Christoph Meinel ; Stephan WaackSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: The “log rank” conjecture consists of the question how exactly the deterministic communication complexity of a problem can be determined in terms of algebraic invariants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the modular communication complexity can be characterised precisely in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to determine precisely the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the obtained bounds for the modular communication complexity, we can conclude exponential lower bounds on the size of depth two circuits having arbitary symmetric gates at the bottom level and a MODm-gate at the top.
Url:
DOI: 10.1007/3-540-60922-9_50
Links to Exploration step
ISTEX:87B540B583461315D3BD5D12EE56DAA4B34CD4DDLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">The “log rank” conjecture for modular communication complexity</title><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</mods:affiliation></affiliation></author><author><name sortKey="Waack, Stephan" sort="Waack, Stephan" uniqKey="Waack S" first="Stephan" last="Waack">Stephan Waack</name><affiliation><mods:affiliation>Inst. für Num. und Angew. Mathematik, Georg-August-Univ., D-37083, Göttingen</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:87B540B583461315D3BD5D12EE56DAA4B34CD4DD</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1007/3-540-60922-9_50</idno><idno type="url">https://api.istex.fr/document/87B540B583461315D3BD5D12EE56DAA4B34CD4DD/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001395</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001395</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">The “log rank” conjecture for modular communication complexity</title><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</mods:affiliation></affiliation></author><author><name sortKey="Waack, Stephan" sort="Waack, Stephan" uniqKey="Waack S" first="Stephan" last="Waack">Stephan Waack</name><affiliation><mods:affiliation>Inst. für Num. und Angew. Mathematik, Georg-August-Univ., D-37083, Göttingen</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1996</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">87B540B583461315D3BD5D12EE56DAA4B34CD4DD</idno><idno type="DOI">10.1007/3-540-60922-9_50</idno><idno type="ChapterID">50</idno><idno type="ChapterID">Chap50</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: The “log rank” conjecture consists of the question how exactly the deterministic communication complexity of a problem can be determined in terms of algebraic invariants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the modular communication complexity can be characterised precisely in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to determine precisely the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the obtained bounds for the modular communication complexity, we can conclude exponential lower bounds on the size of depth two circuits having arbitary symmetric gates at the bottom level and a MODm-gate at the top.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Christoph Meinel</name><affiliations><json:string>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</json:string></affiliations></json:item><json:item><name>Stephan Waack</name><affiliations><json:string>Inst. für Num. und Angew. Mathematik, Georg-August-Univ., D-37083, Göttingen</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: The “log rank” conjecture consists of the question how exactly the deterministic communication complexity of a problem can be determined in terms of algebraic invariants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the modular communication complexity can be characterised precisely in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to determine precisely the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the obtained bounds for the modular communication complexity, we can conclude exponential lower bounds on the size of depth two circuits having arbitary symmetric gates at the bottom level and a MODm-gate at the top.</abstract><qualityIndicators><score>6.584</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.28 x 662.28 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>889</abstractCharCount><pdfWordCount>5289</pdfWordCount><pdfCharCount>23861</pdfCharCount><pdfPageCount>14</pdfPageCount><abstractWordCount>132</abstractWordCount></qualityIndicators><title>The “log rank” conjecture for modular communication complexity</title><chapterId><json:string>50</json:string><json:string>Chap50</json:string></chapterId><refBibs><json:item><author><json:item><name>A Borodin</name></json:item><json:item><name>A Razborov</name></json:item><json:item><name>R Smolensky</name></json:item></author><host><volume>3</volume><pages><last>18</last><first>1</first></pages><author></author><title>Computational Complexity</title><publicationDate>1993</publicationDate></host><title>On Lower Bounds for Read-k-Times Branching Programs</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>C Damm</name></json:item><json:item><name>M Krause</name></json:item><json:item><name> Ch</name></json:item><json:item><name> Meinel</name></json:item><json:item><name> St</name></json:item><json:item><name> Waack</name></json:item></author><host><pages><last>293</last><first>281</first></pages><author></author><title>Proc. 9th STACS</title><publicationDate>1992</publicationDate></host><title>Separating Counting Commurdcation Complexity Classes</title><publicationDate>1992</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>G Turan</name></json:item></author><host><pages><last>191</last><first>186</first></pages><author></author><title>Proc. 20th ACM STOC</title><publicationDate>1988</publicationDate></host><title>On the Communication Complexity of Graph Problems</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>M Krause</name></json:item><json:item><name> St</name></json:item><json:item><name> Waack</name></json:item></author><host><pages><last>782</last><first>777</first></pages><author></author><title>Proc. 32nd IEEE FOCS</title><publicationDate>1991</publicationDate></host><title>Variation Ranks of Communication Matrices and Lower Bomlds /or Depth Two Circuits Havi~2g Symmetric Gates with Unbounded Fanha</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>S Lokam</name></json:item></author><host><author></author><title>Proc. 36th IEEE FOCS</title><publicationDate>1995</publicationDate></host><title>Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeotts and Communication Complexity</title><publicationDate>1995</publicationDate></json:item><json:item><host><pages><last>266</last><first>235</first></pages><author><json:item><name>L Lovasz</name></json:item></author><title>Commtmication complexity: A survey, in: Paths, Flows and VLSI- Layouts</title><publicationDate>1990</publicationDate></host></json:item><json:item><author><json:item><name>L Lovasz</name></json:item><json:item><name>M Saks</name></json:item></author><host><volume>47</volume><pages><last>349</last><first>322</first></pages><author></author><title>Journal of Computer and System Sciences</title><publicationDate>1993</publicationDate></host><title>Communication Complexity and Combinatorial Lattice Theory</title><publicationDate>1993</publicationDate></json:item><json:item><host><author><json:item><name> Ch</name></json:item><json:item><name> Meinel</name></json:item><json:item><name> St</name></json:item><json:item><name> Waack</name></json:item></author><title>The M'obius Function, Variation Ranks, and O(n) - Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem</title></host></json:item><json:item><author><json:item><name>K Mebahorn</name></json:item><json:item><name>E,M Schmidt</name></json:item></author><host><pages><last>337</last><first>330</first></pages><author></author><title>Las Vegas is Better than Determinism in VLSI and Distributed Computing Proc. 14th ACM STOC</title><publicationDate>1982</publicationDate></host><publicationDate>1982</publicationDate></json:item><json:item><author><json:item><name>P Pudlak</name></json:item></author><host><volume>14</volume><pages><last>216</last><first>2133</first></pages><issue>2</issue><author></author><title>Combinatorica</title><publicationDate>1994</publicationDate></host><title>Large Commtudcation in Constant Depth Circuits</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>A,A Razborov</name></json:item></author><host><volume>41</volume><pages><last>607</last><first>598</first></pages><author></author><title>Math. Zametki</title><publicationDate>1987</publicationDate></host><title>Lower botu2ds for the size of circuits of bounded depth with basis {A, fib}, 3ouru</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>A,A Razborov</name></json:item></author><host><author></author><title>On Rigid Matrices</title></host></json:item><json:item><author><json:item><name>R Raz</name></json:item><json:item><name>B Spieker</name></json:item></author><host><pages><last>176</last><first>168</first></pages><author></author><title>Proc. 34th IEEE FOCS</title><publicationDate>1993</publicationDate></host><title>On the "log rank"-Conjecture ha Communication Complexity</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>L Skyum</name></json:item><json:item><name>L,V Valiant</name></json:item></author><host><pages><last>253</last><first>244</first></pages><author></author><title>Proc. 22th IEEE FOCS</title></host><title>A Complexity Theory Based on Boolean Algebra</title></json:item><json:item><author><json:item><name>V Shoup</name></json:item><json:item><name>R Smolensky</name></json:item></author><host><pages><last>383</last><first>378</first></pages><author></author><title>Proc. 32nd IEEE FOCS</title><publicationDate>1991</publicationDate></host><title>Lower Bounds for Polynomial Evaluation and Interpolation</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>R Smolensky</name></json:item></author><host><pages><last>82</last><first>77</first></pages><author></author><title>Proc. 19th ACM STOC</title><publicationDate>1987</publicationDate></host><publicationDate>1987</publicationDate></json:item><json:item><host><author><json:item><name>A Wigderson</name></json:item></author><title>The Complexity of Graph Connectivity, TR 92-19</title></host></json:item><json:item><author><json:item><name>A,C C Yao</name></json:item></author><host><pages><last>213</last><first>209</first></pages><author></author><title>Proc. llst ACM STOC</title><publicationDate>1979</publicationDate></host><title>Some Complexity Questions Related to Distributed Computing</title><publicationDate>1979</publicationDate></json:item><json:item><author><json:item><name>A,C C Yao</name></json:item></author><host><pages><last>627</last><first>619</first></pages><author></author><title>Proc. 31st IEEE FOCS</title><publicationDate>1990</publicationDate></host><publicationDate>1990</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1996</copyrightDate></serie><host><editor><json:item><name>Claude Puech</name></json:item><json:item><name>Rüdiger Reischuk</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Programming Techniques</value></json:item><json:item><value>Operating Systems</value></json:item></subject><isbn><json:string>978-3-540-60922-3</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>STACS 96</title><bookId><json:string>3540609229</json:string></bookId><volume>1046</volume><pages><last>630</last><first>617</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-49723-3</json:string></eisbn><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/3-540-60922-9</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/3-540-60922-9_50</json:string></doi><id>87B540B583461315D3BD5D12EE56DAA4B34CD4DD</id><score>0.5458529</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/87B540B583461315D3BD5D12EE56DAA4B34CD4DD/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/87B540B583461315D3BD5D12EE56DAA4B34CD4DD/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/87B540B583461315D3BD5D12EE56DAA4B34CD4DD/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">The “log rank” conjecture for modular communication 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, 1996</p></availability><date>1996</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">The “log rank” conjecture for modular communication complexity</title><author xml:id="author-1"><persName><forename type="first">Christoph</forename><surname>Meinel</surname></persName><affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</affiliation></author><author xml:id="author-2"><persName><forename type="first">Stephan</forename><surname>Waack</surname></persName><affiliation>Inst. für Num. und Angew. Mathematik, Georg-August-Univ., D-37083, Göttingen</affiliation></author></analytic><monogr><title level="m">STACS 96</title><title level="m" type="sub">13th Annual Symposium on Theoretical Aspects of Computer Science Grenoble, France, February 22–24, 1996 Proceedings</title><idno type="pISBN">978-3-540-60922-3</idno><idno type="eISBN">978-3-540-49723-3</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/3-540-60922-9</idno><idno type="book-ID">3540609229</idno><idno type="book-title-ID">44964</idno><idno type="book-volume-number">1046</idno><idno type="book-chapter-count">54</idno><editor><persName><forename type="first">Claude</forename><surname>Puech</surname></persName></editor><editor><persName><forename type="first">Rüdiger</forename><surname>Reischuk</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-07"></date><biblScope unit="volume">1046</biblScope><biblScope unit="page" from="617">617</biblScope><biblScope unit="page" to="630">630</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1996</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">87B540B583461315D3BD5D12EE56DAA4B34CD4DD</idno><idno type="DOI">10.1007/3-540-60922-9_50</idno><idno type="ChapterID">50</idno><idno type="ChapterID">Chap50</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1996</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: The “log rank” conjecture consists of the question how exactly the deterministic communication complexity of a problem can be determined in terms of algebraic invariants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the modular communication complexity can be characterised precisely in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to determine precisely the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the obtained bounds for the modular communication complexity, we can conclude exponential lower bounds on the size of depth two circuits having arbitary symmetric gates at the bottom level and a MODm-gate at the top.</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>I16013</label><label>I16021</label><label>I1603X</label><label>I16048</label><label>I14010</label><label>I14045</label><item><term>Computer Science</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Mathematical Logic and Formal Languages</term></item><item><term>Programming Techniques</term></item><item><term>Operating Systems</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-07">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/87B540B583461315D3BD5D12EE56DAA4B34CD4DD/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 TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540609229</BookID><BookTitle>STACS 96</BookTitle><BookSubTitle>13th Annual Symposium on Theoretical Aspects of Computer Science Grenoble, France, February 22–24, 1996 Proceedings</BookSubTitle><BookVolumeNumber>1046</BookVolumeNumber><BookDOI>10.1007/3-540-60922-9</BookDOI><BookTitleID>44964</BookTitleID><BookPrintISBN>978-3-540-60922-3</BookPrintISBN><BookElectronicISBN>978-3-540-49723-3</BookElectronicISBN><BookChapterCount>54</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16013" Priority="1" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I16021" Priority="2" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I1603X" Priority="3" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I16048" Priority="4" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I14010" Priority="5" Type="Secondary">Programming Techniques</BookSubject><BookSubject Code="I14045" Priority="6" Type="Secondary">Operating Systems</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Claude</GivenName><FamilyName>Puech</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Rüdiger</GivenName><FamilyName>Reischuk</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap50" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>50</ChapterID><ChapterDOI>10.1007/3-540-60922-9_50</ChapterDOI><ChapterSequenceNumber>50</ChapterSequenceNumber><ChapterTitle Language="En">The “log rank” conjecture for modular communication complexity</ChapterTitle><ChapterFirstPage>617</ChapterFirstPage><ChapterLastPage>630</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>7</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><BookID>3540609229</BookID><BookTitle>STACS 96</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Christoph</GivenName><FamilyName>Meinel</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Stephan</GivenName><FamilyName>Waack</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgDivision>Fachbereich IV - Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Inst. für Num. und Angew. Mathematik</OrgDivision><OrgName>Georg-August-Univ.</OrgName><OrgAddress><Postcode>D-37083</Postcode><City>Göttingen</City></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>The “log rank” conjecture consists of the question how exactly the deterministic communication complexity of a problem can be determined in terms of algebraic invariants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the modular communication complexity can be characterised precisely in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to determine precisely the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the obtained bounds for the modular communication complexity, we can conclude exponential lower bounds on the size of depth two circuits having arbitary symmetric gates at the bottom level and a MOD<Subscript>m</Subscript>-gate at the top.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>The “log rank” conjecture for modular communication complexity</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>The “log rank” conjecture for modular communication complexity</title></titleInfo><name type="personal"><namePart type="given">Christoph</namePart><namePart type="family">Meinel</namePart><affiliation>Fachbereich IV - Informatik, Universität Trier, D-54286, Trier</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Stephan</namePart><namePart type="family">Waack</namePart><affiliation>Inst. für Num. und Angew. Mathematik, Georg-August-Univ., D-37083, Göttingen</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-07</dateIssued><copyrightDate encoding="w3cdtf">1996</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: The “log rank” conjecture consists of the question how exactly the deterministic communication complexity of a problem can be determined in terms of algebraic invariants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the modular communication complexity can be characterised precisely in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to determine precisely the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the obtained bounds for the modular communication complexity, we can conclude exponential lower bounds on the size of depth two circuits having arbitary symmetric gates at the bottom level and a MODm-gate at the top.</abstract><relatedItem type="host"><titleInfo><title>STACS 96</title><subTitle>13th Annual Symposium on Theoretical Aspects of Computer Science Grenoble, France, February 22–24, 1996 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Claude</namePart><namePart type="family">Puech</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Rüdiger</namePart><namePart type="family">Reischuk</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1996</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="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I14010">Programming Techniques</topic><topic authority="SpringerSubjectCodes" authorityURI="I14045">Operating Systems</topic></subject><identifier type="DOI">10.1007/3-540-60922-9</identifier><identifier type="ISBN">978-3-540-60922-3</identifier><identifier type="eISBN">978-3-540-49723-3</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">44964</identifier><identifier type="BookID">3540609229</identifier><identifier type="BookChapterCount">54</identifier><identifier type="BookVolumeNumber">1046</identifier><part><date>1996</date><detail type="volume"><number>1046</number><caption>vol.</caption></detail><extent unit="pages"><start>617</start><end>630</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1996</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><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1996</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></relatedItem><identifier type="istex">87B540B583461315D3BD5D12EE56DAA4B34CD4DD</identifier><identifier type="DOI">10.1007/3-540-60922-9_50</identifier><identifier type="ChapterID">50</identifier><identifier type="ChapterID">Chap50</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1996</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1996</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 001395 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001395 | 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:87B540B583461315D3BD5D12EE56DAA4B34CD4DD
|texte= The “log rank” conjecture for modular communication complexity
}}
| This area was generated with Dilib version V0.6.31. |  |