On the joint entropy of d-wise-independent variables

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00463333" target="_blank" >RIV/67985840:_____/16:00463333 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.14712/1213-7243.2015.169" target="_blank" >http://dx.doi.org/10.14712/1213-7243.2015.169</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.14712/1213-7243.2015.169" target="_blank" >10.14712/1213-7243.2015.169</a>

Result language
angličtina
Original language name
On the joint entropy of d-wise-independent variables
Original language description
How low can the joint entropy of n d-wise independent (for d 2)discrete random variables be, subject to given constraints on the individual dis-tributions (say, no value may be taken by a variable with probability greater than p, for p < 1)? This question has been posed and partially answered in a recent work of Babai [Entropy versus pairwise independence (preliminary version), http://people.cs.uchicago.edu/ laci/papers/13augEntropy.pdf, 2013]. In this paper we improve some of his bounds, prove new bounds in a wider range of parameters and show matching upper bounds in some special cases. In particular, we prove tight lower bounds for the min-entropy (as well as the entropy) of pairwise and three-wise independent balanced binary variables for infinitely many values of n.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)