@inproceedings{6729,
  abstract     = {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.},
  author       = {Mondelli, Marco and Hassani, S. Hamed and Urbanke, Rudiger},
  booktitle    = {2017 IEEE International Symposium on Information Theory },
  isbn         = {9781509040964},
  issn         = {2157-8117},
  location     = {Aachen, Germany},
  pages        = {1853--1857},
  publisher    = {IEEE},
  title        = {{Construction of polar codes with sublinear complexity}},
  doi          = {10.1109/isit.2017.8006850},
  year         = {2017},
}

@inproceedings{6526,
  abstract     = {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.},
  author       = {Skórski, Maciej},
  booktitle    = {2017 IEEE International Symposium on Information Theory (ISIT)},
  isbn         = {9781509040964},
  location     = {Aachen, Germany},
  publisher    = {IEEE},
  title        = {{On the complexity of estimating Rènyi divergences}},
  doi          = {10.1109/isit.2017.8006529},
  year         = {2017},
}