Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

On the joint entropy of d-wise-independent variables

Identifikátory výsledku

  • Kód výsledku v 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>

  • Výsledek na webu

    <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>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    On the joint entropy of d-wise-independent variables

  • Popis výsledku v původním jazyce

    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.

  • Název v anglickém jazyce

    On the joint entropy of d-wise-independent variables

  • Popis výsledku anglicky

    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.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    10101 - Pure mathematics

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2016

  • Kód důvěrnosti údajů

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

Údaje specifické pro druh výsledku

  • Název periodika

    Commentationes Mathematicae Universitatis Carolinae

  • ISSN

    0010-2628

  • e-ISSN

  • Svazek periodika

    57

  • Číslo periodika v rámci svazku

    3

  • Stát vydavatele periodika

    CZ - Česká republika

  • Počet stran výsledku

    11

  • Strana od-do

    333-343

  • Kód UT WoS článku

    000410778900007

  • EID výsledku v databázi Scopus

    2-s2.0-85000869378