---
_id: '6729'
abstract:
- lang: eng
  text: Consider the problem of constructing a polar code of block length N for the
    transmission over a given channel W. Typically this requires to compute the reliability
    of all the N synthetic channels and then to include those that are sufficiently
    reliable. However, we know from [1], [2] that there is a partial order among the
    synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce
    the computational burden of the construction problem. We show that, if we take
    advantage of the partial order [1], [2], we can construct a polar code by computing
    the reliability of roughly N/ log 3/2 N synthetic channels. Such a set of synthetic
    channels is universal, in the sense that it allows one to construct polar codes
    for any W, and it can be identified by solving a maximum matching problem on a
    bipartite graph. Our proof technique consists in reducing the construction problem
    to the problem of computing the maximum cardinality of an antichain for a suitable
    partially ordered set. As such, this method is general and it can be used to further
    improve the complexity of the construction problem in case a new partial order
    on the synthetic channels of polar codes is discovered.
arxiv: 1
author:
- first_name: Marco
  full_name: Mondelli, Marco
  id: 27EB676C-8706-11E9-9510-7717E6697425
  last_name: Mondelli
  orcid: 0000-0002-3242-7020
- first_name: S. Hamed
  full_name: Hassani, S. Hamed
  last_name: Hassani
- first_name: Rudiger
  full_name: Urbanke, Rudiger
  last_name: Urbanke
citation:
  ama: 'Mondelli M, Hassani SH, Urbanke R. Construction of polar codes with sublinear
    complexity. In: <i>2017 IEEE International Symposium on Information Theory </i>.
    IEEE; 2017:1853-1857. doi:<a href="https://doi.org/10.1109/isit.2017.8006850">10.1109/isit.2017.8006850</a>'
  apa: 'Mondelli, M., Hassani, S. H., &#38; Urbanke, R. (2017). Construction of polar
    codes with sublinear complexity. In <i>2017 IEEE International Symposium on Information
    Theory </i> (pp. 1853–1857). Aachen, Germany: IEEE. <a href="https://doi.org/10.1109/isit.2017.8006850">https://doi.org/10.1109/isit.2017.8006850</a>'
  chicago: Mondelli, Marco, S. Hamed Hassani, and Rudiger Urbanke. “Construction of
    Polar Codes with Sublinear Complexity.” In <i>2017 IEEE International Symposium
    on Information Theory </i>, 1853–57. IEEE, 2017. <a href="https://doi.org/10.1109/isit.2017.8006850">https://doi.org/10.1109/isit.2017.8006850</a>.
  ieee: M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar codes with
    sublinear complexity,” in <i>2017 IEEE International Symposium on Information
    Theory </i>, Aachen, Germany, 2017, pp. 1853–1857.
  ista: 'Mondelli M, Hassani SH, Urbanke R. 2017. Construction of polar codes with
    sublinear complexity. 2017 IEEE International Symposium on Information Theory
    . ISIT: International Symposium on Information Theory, 1853–1857.'
  mla: Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.”
    <i>2017 IEEE International Symposium on Information Theory </i>, IEEE, 2017, pp.
    1853–57, doi:<a href="https://doi.org/10.1109/isit.2017.8006850">10.1109/isit.2017.8006850</a>.
  short: M. Mondelli, S.H. Hassani, R. Urbanke, in:, 2017 IEEE International Symposium
    on Information Theory , IEEE, 2017, pp. 1853–1857.
conference:
  end_date: 2017-06-30
  location: Aachen, Germany
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2017-06-25
date_created: 2019-07-30T07:14:18Z
date_published: 2017-06-15T00:00:00Z
date_updated: 2023-02-23T12:49:08Z
day: '15'
doi: 10.1109/isit.2017.8006850
extern: '1'
external_id:
  arxiv:
  - '1612.05295'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1612.05295
month: '06'
oa: 1
oa_version: Preprint
page: 1853-1857
publication: '2017 IEEE International Symposium on Information Theory '
publication_identifier:
  eissn:
  - 2157-8117
  isbn:
  - '9781509040964'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '6663'
    relation: later_version
    status: public
status: public
title: Construction of polar codes with sublinear complexity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '6526'
abstract:
- lang: eng
  text: 'This paper studies the complexity of estimating Rényi divergences of discrete
    distributions: p observed from samples and the baseline distribution q known a
    priori. Extending the results of Acharya et al. (SODA''15) on estimating Rényi
    entropy, we present improved estimation techniques together with upper and lower
    bounds on the sample complexity. We show that, contrarily to estimating Rényi
    entropy where a sublinear (in the alphabet size) number of samples suffices, the
    sample complexity is heavily dependent on events occurring unlikely in q, and
    is unbounded in general (no matter what an estimation technique is used). For
    any divergence of integer order bigger than 1, we provide upper and lower bounds
    on the number of samples dependent on probabilities of p and q (the lower bounds
    hold for non-integer orders as well). We conclude that the worst-case sample complexity
    is polynomial in the alphabet size if and only if the probabilities of q are non-negligible.
    This gives theoretical insights into heuristics used in the applied literature
    to handle numerical instability, which occurs for small probabilities of q. Our
    result shows that they should be handled with care not only because of numerical
    issues, but also because of a blow up in the sample complexity.'
article_number: '8006529'
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. On the complexity of estimating Rènyi divergences. In: <i>2017
    IEEE International Symposium on Information Theory (ISIT)</i>. IEEE; 2017. doi:<a
    href="https://doi.org/10.1109/isit.2017.8006529">10.1109/isit.2017.8006529</a>'
  apa: 'Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In
    <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. Aachen,
    Germany: IEEE. <a href="https://doi.org/10.1109/isit.2017.8006529">https://doi.org/10.1109/isit.2017.8006529</a>'
  chicago: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In
    <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. IEEE, 2017.
    <a href="https://doi.org/10.1109/isit.2017.8006529">https://doi.org/10.1109/isit.2017.8006529</a>.
  ieee: M. Skórski, “On the complexity of estimating Rènyi divergences,” in <i>2017
    IEEE International Symposium on Information Theory (ISIT)</i>, Aachen, Germany,
    2017.
  ista: 'Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017
    IEEE International Symposium on Information Theory (ISIT). ISIT: International
    Symposium on Information Theory, 8006529.'
  mla: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” <i>2017
    IEEE International Symposium on Information Theory (ISIT)</i>, 8006529, IEEE,
    2017, doi:<a href="https://doi.org/10.1109/isit.2017.8006529">10.1109/isit.2017.8006529</a>.
  short: M. Skórski, in:, 2017 IEEE International Symposium on Information Theory
    (ISIT), IEEE, 2017.
conference:
  end_date: 2017-06-30
  location: Aachen, Germany
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2017-06-25
date_created: 2019-06-06T12:53:09Z
date_published: 2017-08-09T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '09'
department:
- _id: KrPi
doi: 10.1109/isit.2017.8006529
ec_funded: 1
external_id:
  arxiv:
  - '1702.01666'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1702.01666
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: 2017 IEEE International Symposium on Information Theory (ISIT)
publication_identifier:
  isbn:
  - '9781509040964'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: 1
status: public
title: On the complexity of estimating Rènyi divergences
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2017'
...