{"id":974,"date":"2014-01-28T10:24:55","date_gmt":"2014-01-28T08:24:55","guid":{"rendered":"https:\/\/webs.uab.cat\/giq\/seminar\/parallel-repetition-entangled-games-superposed-information-cost\/"},"modified":"2014-01-28T10:24:55","modified_gmt":"2014-01-28T08:24:55","slug":"parallel-repetition-entangled-games-superposed-information-cost","status":"publish","type":"seminar","link":"https:\/\/webs.uab.cat\/giq\/seminar\/parallel-repetition-entangled-games-superposed-information-cost\/","title":{"rendered":"Parallel Repetition of Entangled Games via the Superposed Information Cost"},"content":{"rendered":"<p>In a two player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution.<br \/> Each of them produces an output and they win the game if they satisfy some predicate on their inputs\/outputs.<br \/> The entangled value \u03c9*(G) of a game G is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs.<br \/> The n-fold parallel repetition G^n of G consists of n instances of G where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win G^n if they win each instance of G.<br \/> Here we show that for any game G such that \u03c9*(G) = 1\u2212\u03b5 &lt; 1, \u03c9*(G^n) decreases exponentially in n.<br \/> To prove this parallel repetition, we introduce the concept of Superposed Information Cost for entangled games which is inspired from the information cost used in communication complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In a two player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs\/outputs. The entangled value \u03c9*(G) of a game G is the maximum probability that Alice and [&hellip;]<\/p>\n","protected":false},"author":20,"featured_media":0,"template":"","class_list":["post-974","seminar","type-seminar","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/seminar\/974","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/seminar"}],"about":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/types\/seminar"}],"author":[{"embeddable":true,"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/users\/20"}],"wp:attachment":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/media?parent=974"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}