An information-theoretic approach to hardness amplification
METADATA ONLY
Loading...
Author / Producer
Date
2017
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Consider two independent games of chance, G and H, which can be won with probability at most β and γ, respectively. Then it can be shown that the game consisting of winning both G and H can be won with probability at most β γ . If the bounds on the winning probability are only due to the computational hardness of the problems and the computational complexity constraints of the game solver algorithm, then the analogous statement is not trivial but indeed holds in an approximate sense under certain conditions. This paper provides a general information-theoretic treatment of this result, showing that it is an abstract statement that is independent of complexity-theoretic considerations and exhibiting explicitly the requirement that a given game instance must be clonable. The core of the proof is a lemma on multi-argument conditional probability distributions. The amplification statement can be generalized to an arbitrary number of independent games, making the winning probability exponentially small in the number of such games.
Permanent link
Publication status
published
External links
Editor
Book title
2017 IEEE International Symposium on Information Theory (ISIT)
Journal / series
Volume
Pages / Article No.
948 - 952
Publisher
IEEE
Event
2017 IEEE International Symposium on Information Theory (ISIT 2017)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03338 - Maurer, Ueli (emeritus) / Maurer, Ueli (emeritus)