Widespread Correspondence.


54 views
Uploaded on:
Category: People / Lifestyle
Description
Setting. . . . . . . . . . . . . . . . . . . . . . . . . . . . 101011110001010. . 001100101011101. . 1111010110001. . . .. WHAT IS BOB GAINING FROM THIS INTERACTION??. WHY WOULD YOU TALK TO AN ALIEN?. TO SEE IF THEY ARE INTELLIGENT?. TO OBTAIN WISDOM?. TO ASK THEM TO STOP BOMBARDING US WITH DANGEROUS RADIATION??.
Transcripts
Slide 1

General Communication Brendan Juba (MIT) With: Madhu Sudan (MIT)

Slide 2

Setting 101011110001010 001100101011101 . . . 1111010110001 WHAT IS BOB GAINING FROM THIS INTERACTION??

Slide 4

TO SEE IF THEY ARE INTELLIGENT ? TO OBTAIN WISDOM? WHY WOULD YOU TALK TO AN ALIEN ? TO ASK THEM TO STOP BOMBARDING US WITH DANGEROUS RADIATION ??

Slide 5

Motivation WHAT CAN BOB LEARN FROM ALICE ?

Slide 6

Setting Fix a set S and a string x Bob wishes to learn " x S? " WANT : convention that ends with a decision that is CORRECT (whp) Also: productive long of x

Slide 7

Outline Definition: Universal convention Analysis of conveying astuteness Generalizing objectives

Slide 8

We need a hypothesis of the structure ??? "Here is a Bob s.t. for each outsider dialect and each occasion x, Bob productively learns if x S "

Slide 9

Language??? X Grammar? Terms? Strings with elucidations STRONG ASSUMPTIONS!

Slide 10

I COULD HELP, IF I WANTED. Perception Some Alices are unhelpful . x∈S? y∈S? z∈S?

Slide 11

Solution Require Alice accommodating in some dialect . x S? x S

Slide 12

WHAT\'S THE PASSWORD ? Perception Some Alices are still unhelpful . Hi?? @&^#*&^%$; x? x S I\'M NOT TALKING TO YOU ANYMORE.

Slide 13

Revision Require that some B\' can proficiently choose " x S? " with Alice\'s help, free of earlier message history Henceforth, such Alices will be called S - accommodating

Slide 14

Definition: S - Universal Bob is S - Universal if  S - supportive A  polynomial p  x (of length n ) whp Bob chooses " xS? " when chatting with A , inside p(n) ventures in desire

Slide 15

Outline Definition: Universal convention Analysis of conveying insight Generalizing objectives

Slide 16

MAIN IDEA #1 We can effectively specify and run every proficient convention If An is S - Helpful , she helps a productive convention B\' that shows up in the list

Slide 17

MAIN IDEA #2 If we can get a proof of either xS or xS , we can promise rightness If S IP , such evidences exist If S is PSPACE - complete , we can lessen demonstrating (non)membership to different examples of S

Slide 18

Theorem For any PSPACE - complete S , there is a S - Universal convention

Slide 19

For how extensive a class of sets would we be able to display an all inclusive convention ?

Slide 20

Limitation 1: fundamental perception Suppose that for some x , some noxious outsider Alice can misdirect Bob (whp) We can change over Alice into a " accommodating " A\' who still deludes Bob : cushion the valuable questions Recall: a S - Universal Bob ought not be deceived by a S - Helpful Alice !

Slide 21

Limitation 1: completing up Thus: a S - Universal Bob fulfills a solid soundness condition In PSPACE we can discover the messages that augment the likelihood that Bob stops rapidly Since Bob is sound , his decision on these messages choose S

Slide 22

First confinement If a S - Universal convention exists, S  PSPACE

Slide 23

Second restriction (Assuming BPP ≠ PSPACE ) For any PSPACE - complete S , if Alice helps a convention of length l the running time of a S - Universal Bob must incorporate a steady calculate that is exponential l

Slide 24

Outline Definition: Universal convention Analysis of imparting insight Generalizing objectives

Slide 25

What about productivity ? Our development acquired shrewdness from an Alice who could choose PSPACE We get closely resembling comes about with effective Alices : limit assets utilized by our translator Depending on assets used to confirm , may just be important in an online sense: "Bounce unites to a non-paltry mediator "

Slide 26

General setting SOME collaborations are fruitful , others are NOT. We look for a convention that lets us know how to take part in fruitful communications (whp)

Slide 27

Define: " objective " Efficiently unquestionable adequate conditions on Bob\'s perspective of connection E.g., successful, effective conventions ! Simple speculation of our definitions and general convention for the computational objective to any such objective

Slide 28

(specialized) CONCLUSION UNIVERSAL COMMUNICATION is workable for VERIFIABLE GOALS .

Slide 29

Practical inspiration Designing conventions for individual gadgets . (cf. sets, sets, and so on.) Simpler , more hearty systems

Slide 30

Practical specialized difficulties Design reasonable " objectives " (think: "program checking") Find a limited class of conventions that grants " length-effective " setup

Slide 31

Thank you! Questions?

Recommended
View more...