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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the extent of independence needed to approximate the product of bounded random variables in expectation. This natural question has applications in pseudorandomness and min-wise independent hashing. For random variables with absolute value bounded by 1, we give an error bound of the form σΩ(k) when the input is k-wise independent and σ2 is the variance of their sum. Previously, known bounds only applied in more restricted settings, and were quantitatively weaker. Our proof relies on a new analytic inequality for the elementary symmetric polynomials Sk(x) for x ∈ Rn. We show that if |Sk(x)|, |Sk+1(x)| are small relative to |Sk−1(x)| for some k > 0 then |S`(x)| is also small for all ` > k. We use this to give a simpler and more modular analysis of a construction of min-wise independent hash functions and pseudorandom generators for combinatorial rectangles due to Gopalan et al., which also improves the overall seed-length. ACM Classification: G.3 AMS Classification: 68Q87

Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials