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
