%PDF-1.5 % 4 0 obj << /S /GoTo /D (section.1) >> endobj 7 0 obj (Introduction) endobj 8 0 obj << /S /GoTo /D (subsection.1.1) >> endobj 11 0 obj (Coarse characterization of Communication Complexity) endobj 12 0 obj << /S /GoTo /D (subsection.1.2) >> endobj 15 0 obj (Communication with imperfectly shared randomness) endobj 16 0 obj << /S /GoTo /D (subsection.1.3) >> endobj 19 0 obj (Overview of Proofs) endobj 20 0 obj << /S /GoTo /D (subsection.1.4) >> endobj 23 0 obj (Roadmap of this paper) endobj 24 0 obj << /S /GoTo /D (section.2) >> endobj 27 0 obj (Preliminaries) endobj 28 0 obj << /S /GoTo /D (subsection.2.1) >> endobj 31 0 obj (Notations and Definitions) endobj 32 0 obj << /S /GoTo /D (subsection.2.2) >> endobj 35 0 obj (Communication Complexity) endobj 36 0 obj << /S /GoTo /D (subsection.2.3) >> endobj 39 0 obj (Information Complexity) endobj 40 0 obj << /S /GoTo /D (subsection.2.4) >> endobj 43 0 obj (Some Useful Communication Problems) endobj 44 0 obj << /S /GoTo /D (subsubsection.2.4.1) >> endobj 47 0 obj (IC lower bound for Unique-Disjointness) endobj 48 0 obj << /S /GoTo /D (subsubsection.2.4.2) >> endobj 51 0 obj (1-way CC lower bound for Sparse-Indexing) endobj 52 0 obj << /S /GoTo /D (section.3) >> endobj 55 0 obj (Coarse Characterization of Information Complexity) endobj 56 0 obj << /S /GoTo /D (subsection.3.1) >> endobj 59 0 obj (Overview of proof) endobj 60 0 obj << /S /GoTo /D (subsection.3.2) >> endobj 63 0 obj (Proof of Theorem 1.1) endobj 64 0 obj << /S /GoTo /D (subsection.3.3) >> endobj 67 0 obj (Lower and upper bounds on Gap Hamming Distance) endobj 68 0 obj << /S /GoTo /D (section.4) >> endobj 71 0 obj (Communication with Imperfectly Shared Randomness) endobj 72 0 obj << /S /GoTo /D (subsection.4.1) >> endobj 75 0 obj (ISR Protocols for Basic Problems) endobj 76 0 obj << /S /GoTo /D (subsubsection.4.1.1) >> endobj 79 0 obj (Small Set Intersection) endobj 80 0 obj << /S /GoTo /D (subsubsection.4.1.2) >> endobj 83 0 obj (Small Hamming Distance) endobj 84 0 obj << /S /GoTo /D (subsubsection.4.1.3) >> endobj 87 0 obj (Strongly Permutation-Invariant functions) endobj 88 0 obj << /S /GoTo /D (subsection.4.2) >> endobj 91 0 obj (Overview of Proofs) endobj 92 0 obj << /S /GoTo /D (subsection.4.3) >> endobj 95 0 obj (2-way ISR Protocol for Permutation-Invariant Functions) endobj 96 0 obj << /S /GoTo /D (subsection.4.4) >> endobj 99 0 obj (1-way ISR Protocol for Permutation-Invariant Functions) endobj 100 0 obj << /S /GoTo /D (subsection.4.5) >> endobj 103 0 obj (1-way CC lower bounds on Gap Hamming Distance) endobj 104 0 obj << /S /GoTo /D (section.5) >> endobj 107 0 obj (Summary and discussion) endobj 108 0 obj << /S /GoTo /D [109 0 R /FitH] >> endobj 111 0 obj << /Length 2402 /Filter /FlateDecode >> stream xY[s۸~Pŕ :iMuig