English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The influence of the   k  th coordinate on a Boolean function    f  :    {  0  ,  1  }   n   →   {  0  ,  1  }is the probability (with respect to the uniform measure on{  0  ,  1  }   n   ) that flipping    x  k    changes the value    f  (  x  )   . The total influence    I  (  f  )    is the sum of influences of the coordinates. The well‐known ‘Junta theorem’ of Friedgut [ Combinatorica  18 (1998) 27–35] asserts that if    I  (  f  )  ⩽  M   , then   f   can be   ε  ‐approximated by a function that depends on    2   O  (  M  /  ε  )coordinates. Friedgut's theorem has a wide variety of applications in mathematics and theoretical computer science.  For a function   f   with    Pr  [  f  (  x  )  =  1  ]  =  t  ⩽  1  /  2   , the edge isoperimetric inequality on the cube implies that    I   (  f  )   ⩾  2  t   log  2    (  1  /  t  )    . Kahn and Kalai (2006) asked, in the spirit of the Junta theorem, whether any   f   such that    I  (  f  )    is within a constant factor of the minimum, can be    (  ε  t  )   ‐approximated by a disjunctive normal form (DNF) of a ‘small’ size (that is, a union of a small number of subcubes). We answer the question by proving the following structure theorem: If    I   (  f  )   ⩽  2  t  (   log  2    (  1  /  t  )   +  M  )   , then   f   can be    (  ε  t  )   ‐approximated by a DNF of size    2   2   O  (  M  /  ε  ). The dependence on   M   is sharp up to the constant factor in the double exponent.

Approximation of biased Boolean functions of small total influence by DNFs