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

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

  • A voir au tour de Diégo-Suarez - Immobilier Diego Suarez ...

    A voir au tour de Diégo-Suarez - Immobilier Diego Suarez ...

    La Mer d'Émeraude . Incontournable ! Un spectacle maritime dont on ne trouve l'équivalent qu'en Océanie. Emeraude, c'est bien ça ! Un chapelet d'îles paradisiaques posées sur un lagon aux eaux cristallines où il fait bon passer une petite journée...
  • Georgias Teachers-As-Advisors Program (TAA) Making Education Work for

    Georgias Teachers-As-Advisors Program (TAA) Making Education Work for

    CLICK * Located on GAcollege in "Middle and High School Resources" * Located on GAcollege in "Middle and High School Resources" * Teachers-As-Advisors has been identified as a best practice for leading students to more rigorous coursework, increasing graduation rates,...
  • MS Roadshow Presentation

    MS Roadshow Presentation

    A B+ OPG dictates that the individual is performing above the standard in most respects in direct comparison to their peer group. All of our WOs are good but only a small percentage are better than their immediate peers. ......
  • Sept. 2016 doc.: IEEE 802.11-16/01182r0 HE Sounding Segmentation

    Sept. 2016 doc.: IEEE 802.11-16/01182r0 HE Sounding Segmentation

    Beamforming Feedback Fragmentation Avoidance. AP's resource allocation in Beamforming Report Poll Trigger should be defined: in Beamforming Report Poll Trigger, the allocated UL resource for one beamformee's sounding feedback shall be enough for the beamformee to transmit the requested sounding...
  • Cells

    Cells

    The cell has been placed in the an isotonic solution (because it contains EQUAL amounts of solute inside and outside of the cell) It will cause the cell stay flaccid. ...
  • Attributes of an Effective Board

    Attributes of an Effective Board

    Presenter: Mary Beth Harrington CVA, Passionate Nonprofit Expert501c³ - Taking Nonprofits to the Third [email protected] www.mbharrington501c3.com Time, Talent, AND Treasure at the Board Level. August 9, 2016. Lone Star Summit 2016. 8.9.16. Mary Beth Harrington [email protected] How to Prioritize Everything...
  • Teaching Internet Safety for Scouts - Chief Seattle Council

    Teaching Internet Safety for Scouts - Chief Seattle Council

    OK, as it is somewhat topical to Cyber Chip and near enough to essential for your packs (troops especially), in the Den Chief training session this morning for Boy Scouts, Dr Randall Ogata was upfront with the audience about his...
  • Delegated Legislation - Mrs Sudds' classroom

    Delegated Legislation - Mrs Sudds' classroom

    Delegated Legislation is a law made by a person or body to whom Parliament has delegated law-making power. It is also known as secondary legislation. If this is secondary legislation what is primary legislation? Is it important to know if...