Powerpoint - Madhu Sudan

Powerpoint - Madhu Sudan

Communication Amid Uncertainty Madhu Sudan Microsoft Research Based on joint works with Brendan Juba, Oded Goldreich, Adam Kalai, Sanjeev Khanna, Elad Haramaty, Jacob Leshno, Clement Canonne, Venkatesan Guruswami, Badih Ghazi, Pritish Kamath, Ilan Komargodski and Pravesh Kothari. July 28, 2015 CMU: Communication Amid Uncertainty 1 of 28 Context in Communication Sender + Receiver share (huuuge) context In human comm: Language, news, Social In computer comm: Protocols, Codes, Distributions Helps compress communication

Perfectly shared Can be abstracted away. Imperfectly shared What is the cost? How to study? July 28, 2015 CMU: Communication Amid Uncertainty 2 of 28 Communication Complexity The model (with shared randomness) : ( , )

=$ $ $ Alice Usually studied for lower bounds. This talk: CC as +ve model. bits exchanged by best protocol July 28, 2015 CMU: Communication Amid Uncertainty Bob ( , )

w.p. 2/3 3 of 28 Modelling Shared Context + Imperfection 1 Many possibilities. Ongoing effort. Alice+Bob may have estimates of and More generally: correlated. Knowledge of function Bob wants to compute may not be exactly known to Alice! Shared randomness 3 Alice + Bob may not have identical copies. 2 July 28, 2015

CMU: Communication Amid Uncertainty 4 of 28 Part 1: Uncertain Compression July 28, 2015 CMU: Communication Amid Uncertainty 5 of 28 Specific Motivation: Dictionary

Dictionary: maps words to meaning Multiple words with same meaning Multiple meanings to same word How to decide what word to use (encoding)? How to decide what a word means (decoding)? Common answer: Context Really Dictionary specifies: Encoding: context meaning word Decoding: context word meaning Context implicit; encoding/decoding works even if context used not identical! July 28, 2015 CMU: Communication Amid Uncertainty 6 of 28 Context? In general complex notion

What does sender know/believe What does receiver know/believe Modifies as conversation progresses. Our abstraction: Context = Probability distribution on potential meanings. Certainly part of what the context provides; and sufficient abstraction to highlight the problem. July 28, 2015 CMU: Communication Amid Uncertainty 7 of 28 The (Uncertain Compression) problem Wish to design encoding/decoding schemes () to be used as follows:

Sender has distribution on Receiver has distribution on Sender gets Sends to receiver. Receiver receives Decodes to ) Want: (provided close), While minimizing July 28, 2015 CMU: Communication Amid Uncertainty 8 of 28 Closeness of distributions: is -close to if for all ,

-close to July 28, 2015 . CMU: Communication Amid Uncertainty 9 of 28 Dictionary = Shared Randomness? Modelling the dictionary: What should it be? Simplifying assumption it is shared randomness, so Assume sender and receiver have some shared randomness and independent of .

Want July 28, 2015 CMU: Communication Amid Uncertainty 10 of 28 Solution (variant of Arith. Coding) Use to define sequences where chosen s.t.

Either Or July 28, 2015 CMU: Communication Amid Uncertainty 11 of 28 Performance Obviously decoding always correct. Easy exercise: Limits: No scheme can achieve Can reduce randomness needed.

July 28, 2015 CMU: Communication Amid Uncertainty 12 of 28 Implications Reflects the tension between ambiguity resolution and compression. Larger the ((estimated) gap in context), larger the encoding length. Entropy is still a valid measure! Coding scheme reflects the nature of human communication (extend messages till they feel unambiguous). The shared randomness assumption A convenient starting point for discussion

But is dictionary independent of context? This is problematic. July 28, 2015 CMU: Communication Amid Uncertainty 13 of 28 Deterministic Compression: Challenge Say Alice and Bob have rankings of N players. Rankings = bijections = rank of i th player in Alices ranking. Further suppose they know rankings are close. Bob wants to know: Is How many bits does Alice need to send (noninteractively). With shared randomness

Deterministically? With Elad Haramaty: July 28, 2015 CMU: Communication Amid Uncertainty 14 of 28 Part 2: Imperfectly Shared Randomness July 28, 2015 CMU: Communication Amid Uncertainty 15 of 28 Model: Imperfectly Shared Randomness

Alice and Bob where i.i.d. sequence of correlated pairs ; . Notation: = cc of with -correlated bits. : Perfectly Shared Randomness cc. cc with PRIVate randomness Starting point: for Boolean functions 1( ) 0( ) What if ? E.g. July 28, 2015

CMU: Communication Amid Uncertainty 16 of 28 Imperfectly Shared Randomness: Results Model first studied by [Bavarian,Gavinsky,Ito14] (Independently and earlier). Their focus: Simultaneous Communication; general models of correlation. They show (among other things) Our Results: Generally: Converse: July 28, 2015 CMU: Communication Amid Uncertainty 17 of 28

Aside: Easy CC Problems Equality testing: Hamming distance: Small set intersection: [Huang etal.] Protocol: Fix ECC

Shared randomness: Protocol: Exchange Use common randomness Accept iff . to hash [Hstad Wigderson] Gap (Real) Inner Product: Main Insight: If , then [Ghazi,Kamath,S15]: Roughly [Alon, Matias, Szegedy] essence of perm. inv. functions July 28, 2015

CMU: Communication Amid Uncertainty 18 of 28 Equality Testing (our proof) Key idea: Think inner products. Encode ;; Estimating inner products: Building on sketching protocols Alice: Picks Gaussians Sends maximizing to Bob. Bob: Accepts iff Analysis: bits suffice if July 28, 2015 CMU: Communication Amid Uncertainty Gaussian

Protocol 19 of 28 General One-Way Communication Idea: All communication Inner Products (For now: Assume one-way-cc) For each random string Alices message = Bobs output = where W.p. over July 28, 2015 is the right answer. CMU: Communication Amid Uncertainty

20 of 28 General One-Way Communication For each random string Alices message = Bobs output = where W.p. is the right answer. Vector representation: (unit coordinate vector) (truth table of

; Acc. Prob. Gaussian protocol estimates inner products of unit vectors to within with communication. July 28, 2015 CMU: Communication Amid Uncertainty 21 of 28 Two-way communication Still decided by inner products. Simple lemma: convex, that describe private coin k-bit comm. strategies for Alice, Bob s.t. accept prob. of equals

Putting things together: Theorem: July 28, 2015 CMU: Communication Amid Uncertainty 22 of 28 Part 3: Uncertain Functionality July 28, 2015 CMU: Communication Amid Uncertainty 23 of 28 Model

Alice knows ; Bob wishes to compute Alice, Bob given explicitly. (Input size ~ Questions: What is ? Is it reasonable to expect to compute ? E.g., Cant compute without communicating Answers: Assume uniformly. if . Suffices to compute for July 28, 2015 CMU: Communication Amid Uncertainty 24 of 28 Results - 1

Thm [Ghazi,Komargodski,Kothari,S.]: If has oneway communication , then in the uncertain model it has communication complexity Main Idea: Canonical protocol for : Alice + Bob share random Alice sends to Bob. Protocol used previously but not as canonical. Canonical protocol robust when . July 28, 2015 CMU: Communication Amid Uncertainty 25 of 28 Results - 2

Can extend model to for arbitrary distribution Results: If is product distribution () then results extend. Else Upper bound: Multiplicative factor of Lower bound: Some blowup necessary and dist. on pairs of functions of constant comm. complexity; but computing in the uncertain model costs bits. Open: Significance of above? July 28, 2015 CMU: Communication Amid Uncertainty 26 of 28 Conclusions

Context Important: New layer of uncertainty. New notion of scale (context LARGE) Many open directions+questions July 28, 2015 CMU: Communication Amid Uncertainty 27 of 28 Thank You! July 28, 2015 CMU: Communication Amid Uncertainty 28 of 28

Recently Viewed Presentations

  • The rotational spectra of 4,4,4-trifluorobutyric acid and its

    The rotational spectra of 4,4,4-trifluorobutyric acid and its

    The rotational spectra of 4,4,4-trifluorobutyric acid and its complex with Formic acid. Yoon Jeong Choi, Alex Treviño, Susanna L. Stephens, Stephen A. Cooke, Stewart E. Novick, Wei Lin. WD04 Clusters and Complexes . Wednesday 21th June
  • Columbia St. Marys Instructor Orientation Onboarding for New

    Columbia St. Marys Instructor Orientation Onboarding for New

    AIDET is a framework for CSM's staff to communicate with patients and their families as well as with each other. It is a simple acronym that represents a very powerful way to communicate with people who are often nervous, anxious...
  • It's All About Safety - MISS DIG System, Inc.

    It's All About Safety - MISS DIG System, Inc.

    MISS DIG 811 Gold Shovel Standard. Michigan has adopted the Gold Shovel Standard, a certification process/program that demonstrates commitment to public safety, and protecting Michigan's underground facilities by following safe excavation practices, such as PA 174, as well as CGA...
  • Diapositiva 1 - Unive

    Diapositiva 1 - Unive

    Flavio Gregori (Iniziative/eventi culturali di ateneo (convegni, mostre …) e coordinamento attività culturali nelle biblioteche) Carmelo Alberti (Teatro) Daniele Goldoni (Musica) Carlo Bagnoli (Rapporti con la Regione e il Territorio) Irene Poli (Rapporti con l'Unione Europea) Giuseppe Barbieri (Fund Raising)...
  • Healthiest Wisconsin 2020 Overview, Sept. 16, 2011

    Healthiest Wisconsin 2020 Overview, Sept. 16, 2011

    Healthiest Wisconsin 2020:Collaborative Leadership See also the companion document entitled: HW2020 Collaborative Leadership Supplement (April 2013). This supplement was prepared for public health system partners as a means to deepen knowledge and broaden the availability of community leadership practices to...
  • 06.01 Classification Project Classifying Birds The 6.01 lesson

    06.01 Classification Project Classifying Birds The 6.01 lesson

    Here's a reminder of how a cladogram can look: Blue Jay Robin Cardinal Canary Pelican Cladogram #1 Describe the physical traits your birds had in common with one another in your taxonomy chart. Break down your descriptions by taxa (kingdom,...
  • Blue Sky Strategy for SmartTracks - CDE

    Blue Sky Strategy for SmartTracks - CDE

    Strategies for Creating Safe, Inclusive Schools. Student-led groups that focus on creating inclusive schools (e.g. Gay Straight Alliances, No Place for Hate) Inclusive curriculum and classroom materials (e.g. Facing History and Ourselves) Inclusive celebration of events and holidays (e.g. African...
  • Polymer Characterization - Sahand University of Technology

    Polymer Characterization - Sahand University of Technology

    2. In a linear polymer there are twice as many end of the chain . and groups as polymer molecules. 3. If having different end group, the number of detected end group is average molecular weight. 4. End group analysis...