The Experts below are selected from a list of 9273 Experts worldwide ranked by ideXlab platform
Thomas Vidick - One of the best experts on this subject based on the ideXlab platform.
-
non signaling parallel repetition using de finetti reductions
IEEE Transactions on Information Theory, 2016Co-Authors: Rotem Arnonfriedman, Renato Renner, Thomas VidickAbstract:In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal Winning Probability $1-\alpha $ and its repeated version $G^{n}$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this paper, the case of multiplayer non-signaling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero Probability to be asked) with any number of players, we prove a threshold theorem stating that the Probability that non-signaling players win more than a fraction $1-\alpha +\beta $ of the $n$ games is exponentially small in $n\beta ^{2}$ for every $0\leq \beta \leq \alpha $ . For games with incomplete support, we derive a similar statement for a slightly modified form of repetition. The result is proved using a new technique based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
-
non signalling parallel repetition using de finetti reductions
arXiv: Quantum Physics, 2014Co-Authors: Rotem Arnonfriedman, Renato Renner, Thomas VidickAbstract:In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal Winning Probability $1-\alpha$ and its repeated version $G^n$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero Probability to be asked) with any number of players we prove a threshold theorem stating that the Probability that non-signalling players win more than a fraction $1-\alpha+\beta$ of the $n$ games is exponentially small in $n\beta^2$, for every $0\leq \beta \leq \alpha$. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
Rotem Arnonfriedman - One of the best experts on this subject based on the ideXlab platform.
-
non signaling parallel repetition using de finetti reductions
IEEE Transactions on Information Theory, 2016Co-Authors: Rotem Arnonfriedman, Renato Renner, Thomas VidickAbstract:In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal Winning Probability $1-\alpha $ and its repeated version $G^{n}$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this paper, the case of multiplayer non-signaling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero Probability to be asked) with any number of players, we prove a threshold theorem stating that the Probability that non-signaling players win more than a fraction $1-\alpha +\beta $ of the $n$ games is exponentially small in $n\beta ^{2}$ for every $0\leq \beta \leq \alpha $ . For games with incomplete support, we derive a similar statement for a slightly modified form of repetition. The result is proved using a new technique based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
-
non signalling parallel repetition using de finetti reductions
arXiv: Quantum Physics, 2014Co-Authors: Rotem Arnonfriedman, Renato Renner, Thomas VidickAbstract:In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal Winning Probability $1-\alpha$ and its repeated version $G^n$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero Probability to be asked) with any number of players we prove a threshold theorem stating that the Probability that non-signalling players win more than a fraction $1-\alpha+\beta$ of the $n$ games is exponentially small in $n\beta^2$, for every $0\leq \beta \leq \alpha$. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
Renato Renner - One of the best experts on this subject based on the ideXlab platform.
-
non signaling parallel repetition using de finetti reductions
IEEE Transactions on Information Theory, 2016Co-Authors: Rotem Arnonfriedman, Renato Renner, Thomas VidickAbstract:In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal Winning Probability $1-\alpha $ and its repeated version $G^{n}$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this paper, the case of multiplayer non-signaling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero Probability to be asked) with any number of players, we prove a threshold theorem stating that the Probability that non-signaling players win more than a fraction $1-\alpha +\beta $ of the $n$ games is exponentially small in $n\beta ^{2}$ for every $0\leq \beta \leq \alpha $ . For games with incomplete support, we derive a similar statement for a slightly modified form of repetition. The result is proved using a new technique based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
-
non signalling parallel repetition using de finetti reductions
arXiv: Quantum Physics, 2014Co-Authors: Rotem Arnonfriedman, Renato Renner, Thomas VidickAbstract:In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal Winning Probability $1-\alpha$ and its repeated version $G^n$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero Probability to be asked) with any number of players we prove a threshold theorem stating that the Probability that non-signalling players win more than a fraction $1-\alpha+\beta$ of the $n$ games is exponentially small in $n\beta^2$, for every $0\leq \beta \leq \alpha$. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
Aram W Harrow - One of the best experts on this subject based on the ideXlab platform.
-
quantum de finetti theorems under local measurements with applications
Symposium on the Theory of Computing, 2013Co-Authors: Fernando G. S. L. Brandão, Aram W HarrowAbstract:Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling Probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - e) qubits would imply a exp (n1 - 2e polylog(n))-time algorithm for 3-SAT. We show that the maximum Winning Probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/e2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum Winning Probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables $n$ by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.
-
quantum de finetti theorems under local measurements with applications
arXiv: Quantum Physics, 2012Co-Authors: Fernando G. S. L. Brandão, Aram W HarrowAbstract:Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling Probability distributions. We give the following applications of the results: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the exponential time hypothesis. We show that the maximum Winning Probability of free games can be estimated in polynomial time by linear programming. We also show that 3-SAT with m variables can be reduced to obtaining a constant error approximation of the maximum Winning Probability under entangled strategies of O(m^{1/2})-player one-round non-local games, in which the players communicate O(m^{1/2}) bits all together. We show that the optimization of certain polynomials over the hypersphere can be performed in quasipolynomial time in the number of variables n by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a result due to Aaronson -- showing that given an unknown n qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information.
Or Sattath - One of the best experts on this subject based on the ideXlab platform.
-
quantum coin hedging and a counter measure
arXiv: Quantum Physics, 2017Co-Authors: Maor Ganz, Or SattathAbstract:A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with Winning Probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol - quantum coin flipping. For this reason, when cryptographic protocols are composed, hedging may introduce serious challenges into their analysis. We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting, in which hedging is only a special case.
-
quantum coin hedging and a counter measure
Conference on Theory of Quantum Computation Communication and Cryptography, 2017Co-Authors: Maor Ganz, Or SattathAbstract:A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with Winning Probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol – quantum coin flipping. For this reason, when cryptographic protocols are composed in parallel, hedging may introduce serious challenges into their analysis. We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting of possible target functions, in which hedging is only a special case.
