Communication complexity of permutation-invariant functions
Thesis: S.M. in Computer Science & Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/99861 |
| _version_ | 1826216258922610688 |
|---|---|
| author | Kamath, Pritish |
| author2 | Madhu Sudan. |
| author_facet | Madhu Sudan. Kamath, Pritish |
| author_sort | Kamath, Pritish |
| collection | MIT |
| description | Thesis: S.M. in Computer Science & Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. |
| first_indexed | 2024-09-23T16:44:31Z |
| format | Thesis |
| id | mit-1721.1/99861 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:44:31Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/998612019-04-10T17:11:00Z Communication complexity of permutation-invariant functions Kamath, Pritish Madhu Sudan. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: S.M. in Computer Science & Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. Cataloged from PDF version of thesis. Includes bibliographical references (pages 68-71). Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function f : {0, 1}n x {0, 1}n --> {0, 1, ?} is permutation-invariant if for every bijection [pi]: {1,..., n} --> {1,.. ., n} and every x, y [sum] {0, I}n, it is the case that f (x, y) = f (x[pi], y[pi]). Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in n given an implicit description of f) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as SET-DISJOINTNESS and INDEXING, while complementing them with the relatively lesser-known upper bounds for GAP-INNER-PRODUCT (from the sketching literature) and SPARSE-GAP-INNER-PRODUCT (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive O(log log n) loss. by Pritish Kamath. S.M. in Computer Science & Engineering 2015-11-09T19:53:41Z 2015-11-09T19:53:41Z 2015 2015 Thesis http://hdl.handle.net/1721.1/99861 927749345 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 71 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kamath, Pritish Communication complexity of permutation-invariant functions |
| title | Communication complexity of permutation-invariant functions |
| title_full | Communication complexity of permutation-invariant functions |
| title_fullStr | Communication complexity of permutation-invariant functions |
| title_full_unstemmed | Communication complexity of permutation-invariant functions |
| title_short | Communication complexity of permutation-invariant functions |
| title_sort | communication complexity of permutation invariant functions |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/99861 |
| work_keys_str_mv | AT kamathpritish communicationcomplexityofpermutationinvariantfunctions |