Imperfectly Shared Randomness in Communication Madhu Sudan Microsoft Research Joint work with Clment Canonne (Columbia), Venkatesan Guruswami (CMU) and Raghu Meka (). 11/3/2014 ISR in Communication: [email protected] 1 of 26 Communication (Complexity) Recall Shannon (Noiseless setting) ( \{ 0 , 1 } Alice

Compress Decompress What will Bob do with ? Hopefully Bob In general, model allows interaction. For this talk, only one way comm. Often knowledge of is overkill. [Yao]s model: Bob has private information . Wants to know Can we get away with much less communication?

11/3/2014 ISR in Communication: [email protected] 2 of 26 Example: Parity: ; Solution: Alice sends to Bob. Bob computes . Outputs . 1 bit of communication! (No distributional assumption on

11/3/2014 ISR in Communication: [email protected] 3 of 26 Randomness in Communication As in many aspects of CS, randomness often helps find (more efficient) solutions. Two Probabilistic Communication Models: Private randomness: Alice tosses random coins and uses that to determine what to send to Bob. Shared randomness: Alice and Bob share random string Alices message depends on Bobs use of message depends on . Det. CC Private. CC Shared. CC

11/3/2014 ISR in Communication: [email protected] 4 of 26 Example: Equality Testing if and o.w. Deterministically: Communicate bits With private randomness: Alice encodes ; Picks ; sends to Bob. Bob receives and outputs 1 if Priv. CC bits With shared randomness: Alice and Bob share Alice sends Shared CC bits. 11/3/2014

ISR in Communication: [email protected] 5 of 26 This talk: Imperfect Sharing Generic motivation: Where does the shared randomness come from? Nature/Collective experience Noisy Do parties have to agree on their shares perfectly? Can they get away with imperfection? Is their a price? 11/3/2014 ISR in Communication: [email protected] 6 of 26

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 What if ? E.g. 11/3/2014 ISR in Communication: [email protected] 7 of 26

Results Model first studied by [Bavarian et al.14] (Independently and earlier). They show Our Results: Generally: Converse: 11/3/2014 ISR in Communication: [email protected] 8 of 26 Equality Testing (our proof)

Key idea: Think inner products. Encode ;; Estimating inner products: Using ideas from low-distortion embeddings Alice: Picks Gaussian sends Bob: has ; compares with (mod details): bits suffice if [Bavarian et al.] Alternate protocol. 11/3/2014 ISR in Communication: [email protected] 9 of 26 General Communication Idea: All communication Inner Products

For each random string Alices message = Bobs output = where 11/3/2014 W.p. over is the right answer. ISR in Communication: [email protected] 10 of 26 General Communication For each random string Alices message = Bobs output = where

W.p. is the right answer. Vector representation: 11/3/2014 (unit coordinate vector) (truth table of ; Acc. Prob. Gaussian protocol estimates inner products of unit vectors to within with communication. ISR in Communication: [email protected] 11 of 26 Main Technical Result: Matching lower

bound There exists (promise) problem s.t. The Problem: Gap Sparse Inner Product (G-Sparse-IP). Alice gets sparse ; Bob gets Promise: or Decide which. 11/3/2014 ISR in Communication: [email protected] 12 of 26 Protocol for G-Sparse-IP

Idea: correlated with answer. Use (perfectly) shared randomness to find random index s.t. Shared randomness: uniform over Alice Bob: smallest index s.t. Bob: Accept if Expect 11/3/2014 ISR in Communication: [email protected] 13 of 26 ISR lower bounds

Challenge: Usual CC lower bounds give a distribution and prove lower bound against it. G-Sparse-IP has a low-complexity protocol for every input, with shared randomness. Thus for every distribution, there exists a deterministic low-complexity protocol! So usual method cant work Need to fix strategy first and then tailor-make a hard distribution for the strategy 11/3/2014 ISR in Communication: [email protected] 14 of 26 ISR lower bound for GSIP: Overview

Strategies: Alice ; Bob ; Two possibilities: Case 1: Alices strategy and Bobs strategy have common highly influential coordinate: ( s.t. flipping changes Alices message etc.) Leads to protocol for agreement distillation [We prove this is impossible.] Case 2: Strategies have no common influential variable: 11/3/2014

Invariance Principle Solves some Gaussian problem High complexity lower bound for Gaussian problem. (Details shortly) ISR in Communication: [email protected] 15 of 26 Case 1: Agreement Distillation Problem: Charlie ; Dana ; -correlated Goal: Charlie outputs ; Dana outputs ; Lemma: With zero communication Proof: Small-set expansion of noisy hypercube

Well-known by now application of Bonamis lemma. See, e.g., [Analysis of Boolean functions, ODonnell] Corollary: For bits of communication, 11/3/2014 ISR in Communication: [email protected] 16 of 26 Completing Case 1 Fact: (for our defn of influence) any function has bounded number of high influence variables. (By Fact + Markov) Can assume Distributions on Yes and No instances:

No: random sparse ; Yes: Same as No on Bad coordinates. On rest, is more likely to be 1 if 11/3/2014 ISR in Communication: [email protected] 17 of 26 Completing Case 1 (contd.) Agreement strategy for Charlie + Dana: Charlie: s.t. high. Dana: s.t. high. Analysis: large since . ?: Case 1 assumption.

Combined with lower bound for agreement distillation, implies Case 1 cant occur 11/3/2014 ISR in Communication: [email protected] 18 of 26 Case 2: No common influential variable Key Lemma: Fix ; let and . If small () and distinguish Yes/No then have common influential variable. Idea: Use Invariance Principle: Remarkable theorem: Mossel, ODonnell, Oleskiewicz; Mossel++; Informal form: f,g low-degree polynomials with no common influential variable where Boolean -wise product dist. and Gaussian -wise product dist.

11/3/2014 ISR in Communication: [email protected] 19 of 26 The Gaussian-IP Problem Suppose we can get the perfect invariance theorem for us Would transform: Soln for G-Sparse-IP Soln for G-Gaussian-IP Alice, Bob get Gaussian vectors Yes: No: Theorem: Non-sparse bits Formally [Bar Yossef et al.]: Can reduce

indexing to G-Gaussian-IP. 11/3/2014 ISR in Communication: [email protected] 20 of 26 Invariance Principle + Challenges Informal Invariance Principle: low-degree polynomials with no common influential variable where Boolean -wise product dist. and Gaussian -wise product dist Challenges [+ Solutions]: Our functions not low-degree [Smoothening] Our functions not real-valued [Truncate range to ] [???, [work with ]] 11/3/2014

ISR in Communication: [email protected] 21 of 26 Invariance Principle + Challenges Informal Invariance Principle: low-degree polynomials with no common influential variable (caveat) Challenges Our functions not low-degree [Smoothening] Our functions not real-valued [Truncate] Quantity of interest is not [Can express quantity of interest as inner product. ] (lots of grunge work ) Get a relevant invariance principle (next)

11/3/2014 ISR in Communication: [email protected] 22 of 26 Invariance Principle for CC Thm: For every convex transformations s.t. if and have no common influential variable, then and satisfy Main differences: vector-valued. Functions are transformed: Range preserved exactly ()! So are still communication strategies!

11/3/2014 ISR in Communication: [email protected] 23 of 26 Summarizing bits of comm. with perfect sharing bits with imperfect sharing. This is tight (for one-way communication) Invariance principle for communication Agreement distillation Low-influence strategies 11/3/2014 ISR in Communication: [email protected] 24 of 26

Conclusions Imperfect agreement of context important. Dealing with new layer of uncertainty. Notion of scale (context LARGE) Many open directions+questions: Imperfectly shared randomness: One-sided error? Does interaction ever help? How much randomness? More general forms of correlation? 11/3/2014 ISR in Communication: [email protected] 25 of 26

Thank You! 11/3/2014 ISR in Communication: [email protected] 26 of 26