Powerpoint - Harvard John A. Paulson School of Engineering ...

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

Recently Viewed Presentations

  • Male Reproductive System Overview

    Male Reproductive System Overview

    Male Reproductive Tract. After maturing in the epididymis, the sperm cells travel through the ductus deferens (vas deferens), which travel around the urinary bladder, and join together at a structure called the ejaculatory duct.. The remaining tube is called the...
  • HSC Thespians - Drama for HSC

    HSC Thespians - Drama for HSC

    HSC Thespians. All you need to know about auditions … and more! All you need to know. Auditioning . Expected behaviors. Key dates & contact information. Audition form & Student contract. HSC THESPIANS. ... TERMS OF THE THEATER. PARENT CONTRACT....
  • Chapter 24 Poisoning and Overdose - Montgomery County, Maryland

    Chapter 24 Poisoning and Overdose - Montgomery County, Maryland

    Talking Points: The hospital may need to prepare a certain room, call a specialist, or have specific equipment ready for your arrival. Some providers and hospitals prefer medical reports be given by phone to protect patient's privacy. Be brief; excessive...
  • Measuring Engine Performance

    Measuring Engine Performance

    Engine Displacement. The total . volume. of space increase in the cylinder as the piston moves from the top to the bottom of its stroke. Determined by the circular area of the cylinder then multiplied by the total length of...
  • Lecture 12 NP Class

    Lecture 12 NP Class

    Polynomial-time many-one reduction A < m B A set A in Σ* is said to be polynomial-time many-one reducible to B in Γ* if there exists a polynomial-time computable function f: Σ* → Γ* such that x ε A iff...
  • Mobile Body Sensor Networks for Health Applications

    Mobile Body Sensor Networks for Health Applications

    Mobile Body Sensor Networks for Health Applications Yuan Xue, Vanderbilt Posu Yan, UC Berkeley A collaborative work of Vanderbilt (Sztipanovits, Xue, Werner, Mathe, Jiang)
  • To Kill a Mockingbird Anchor Chart

    To Kill a Mockingbird Anchor Chart

    To Kill a Mockingbird Anchor Chart. Your anchor chart must include: Summary of the chapter. 3 important quotes with explanation. Choose 2 main characters for the chapter. For each character, name 2 characteristics and use a quote as evidence. Theme:...
  • Status and Outlook of Experimental Study of Askaryan Radiation

    Status and Outlook of Experimental Study of Askaryan Radiation

    Predgrag Miocinovic: Frequency + Phase Reconstruct time domain pulse Reconstructed signal is a brief, unresolved, bipolar pulse of radiation Details of analysis in PRD 74, 043002 (2006) Even more data from June 2006 ice run Steve Barwick: ARIANNA "span the...