- We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. The converse bound turns out to be tighter than previous bounds based on smooth min-entropy [Watanabe and Hayashi, ISIT 2013; arXiv:1211.5252 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with known relations between channel simulation and lossy source coding, this implies that privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to protocols of optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [arXiv:1701.05583 [quant-ph]], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a "curious duality" in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low- density generator matrix codes.
- Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained over the years, using a wide range of combinatorial objects. In this paper we establish a new characterization of nowhere dense classes, in terms of poset dimension: A monotone graph class is nowhere dense if and only if for every $h \geq 1$ and every $\epsilon > 0$, posets of height at most $h$ with $n$ elements and whose cover graphs are in the class have dimension $\mathcal{O}(n^{\epsilon})$.
- Aug 21 2017 math.AG arXiv:1708.05699v1
- Aug 21 2017 math.AP arXiv:1708.05637v1
- Aug 21 2017 math.PR arXiv:1708.05634v1
- Aug 21 2017 math.OC arXiv:1708.05632v1
- Aug 21 2017 math.PR arXiv:1708.05626v1
- Aug 21 2017 math.CV arXiv:1708.05624v1
- Aug 21 2017 math.CO arXiv:1708.05623v1
- Aug 21 2017 math.CO arXiv:1708.05598v1
- Aug 21 2017 math.FA arXiv:1708.05593v1
- Aug 21 2017 math.FA arXiv:1708.05588v1
- Aug 21 2017 math.PR arXiv:1708.05587v1
- Aug 21 2017 math.CV arXiv:1708.05585v1
- Aug 21 2017 math.PR arXiv:1708.05584v1
- Aug 21 2017 math.DS arXiv:1708.05580v1
- Aug 21 2017 math.CV arXiv:1708.05578v1
- Aug 21 2017 math.NT arXiv:1708.05577v1
- Aug 21 2017 math.GR arXiv:1708.05566v1
- Aug 21 2017 math.DS arXiv:1708.05544v1
- Aug 21 2017 math.NA arXiv:1708.05531v1
- Aug 21 2017 math.CA arXiv:1708.05530v1
- Aug 21 2017 math.CA arXiv:1708.05525v1
- Aug 21 2017 math.CO arXiv:1708.05524v1
- Aug 21 2017 math.AG arXiv:1708.05523v1
- Aug 21 2017 math.CO arXiv:1708.05518v1
- Aug 21 2017 math.OC arXiv:1708.05516v1
- Aug 21 2017 math.NT arXiv:1708.05511v1