---
_id: '7136'
abstract:
- lang: eng
  text: "It is well established that the notion of min-entropy fails to satisfy the
    \\emph{chain rule} of the form H(X,Y)=H(X|Y)+H(Y), known for Shannon Entropy.
    Such a property would help to analyze how min-entropy is split among smaller blocks.
    Problems of this kind arise for example when constructing extractors and dispersers.\r\nWe
    show that any sequence of variables exhibits a very strong strong block-source
    structure (conditional distributions of blocks are nearly flat) when we \\emph{spoil
    few correlated bits}. This implies, conditioned on the spoiled bits, that \\emph{splitting-recombination
    properties} hold. In particular, we have many nice properties that min-entropy
    doesn't obey in general, for example strong chain rules, \"information can't hurt\"
    inequalities, equivalences of average and worst-case conditional entropy definitions
    and others. Quantitatively, for any sequence X1,…,Xt of random variables over
    an alphabet X we prove that, when conditioned on m=t⋅O(loglog|X|+loglog(1/ϵ)+logt)
    bits of auxiliary information, all conditional distributions of the form Xi|X<i
    are ϵ-close to be nearly flat (only a constant factor away). The argument is combinatorial
    (based on simplex coverings).\r\nThis result may be used as a generic tool for
    \\emph{exhibiting block-source structures}. We demonstrate this by reproving the
    fundamental converter due to Nisan and Zuckermann (\\emph{J. Computer and System
    Sciences, 1996}), which shows that sampling blocks from a min-entropy source roughly
    preserves the entropy rate. Our bound implies, only by straightforward chain rules,
    an additive loss of o(1) (for sufficiently many samples), which qualitatively
    meets the first tighter analysis of this problem due to Vadhan (\\emph{CRYPTO'03}),
    obtained by large deviation techniques. "
article_number: '8849240'
article_processing_charge: No
arxiv: 1
author:
- first_name: Maciej
  full_name: Skórski, Maciej
  id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
  last_name: Skórski
citation:
  ama: 'Skórski M. Strong chain rules for min-entropy under few bits spoiled. In:
    <i>2019 IEEE International Symposium on Information Theory</i>. IEEE; 2019. doi:<a
    href="https://doi.org/10.1109/isit.2019.8849240">10.1109/isit.2019.8849240</a>'
  apa: 'Skórski, M. (2019). Strong chain rules for min-entropy under few bits spoiled.
    In <i>2019 IEEE International Symposium on Information Theory</i>. Paris, France:
    IEEE. <a href="https://doi.org/10.1109/isit.2019.8849240">https://doi.org/10.1109/isit.2019.8849240</a>'
  chicago: Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.”
    In <i>2019 IEEE International Symposium on Information Theory</i>. IEEE, 2019.
    <a href="https://doi.org/10.1109/isit.2019.8849240">https://doi.org/10.1109/isit.2019.8849240</a>.
  ieee: M. Skórski, “Strong chain rules for min-entropy under few bits spoiled,” in
    <i>2019 IEEE International Symposium on Information Theory</i>, Paris, France,
    2019.
  ista: 'Skórski M. 2019. Strong chain rules for min-entropy under few bits spoiled.
    2019 IEEE International Symposium on Information Theory. ISIT: International Symposium
    on Information Theory, 8849240.'
  mla: Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.”
    <i>2019 IEEE International Symposium on Information Theory</i>, 8849240, IEEE,
    2019, doi:<a href="https://doi.org/10.1109/isit.2019.8849240">10.1109/isit.2019.8849240</a>.
  short: M. Skórski, in:, 2019 IEEE International Symposium on Information Theory,
    IEEE, 2019.
conference:
  end_date: 2019-07-12
  location: Paris, France
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2019-07-07
date_created: 2019-11-28T10:19:21Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2023-09-06T11:15:41Z
day: '01'
department:
- _id: KrPi
doi: 10.1109/isit.2019.8849240
external_id:
  arxiv:
  - '1702.08476'
  isi:
  - '000489100301043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1702.08476
month: '07'
oa: 1
oa_version: Preprint
publication: 2019 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781538692912'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Strong chain rules for min-entropy under few bits spoiled
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...