{"ID":2894904,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.10329","arxiv_id":"2507.10329","title":"Computing the probability of intersection","abstract":"Let $Ω_1, \\ldots, Ω_m$ be probability spaces, let $Ω=Ω_1 \\times \\cdots \\times Ω_m$ be their product and let $A_1, \\ldots, A_n \\subset Ω$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x \\in Ω$, $x=\\left(ξ_1, \\ldots, ξ_m\\right)$, and that for each event $A_i$ there are $Δ_i$ of other events $A_j$ that depend on some of the coordinates that $A_i$ depends on. Let $Δ=\\max\\{5,\\ Δ_i: i=1, \\ldots, n\\}$ and let $μ_i=\\min\\{r_i,\\ Δ_i+1\\}$ for $i=1, \\ldots, n$. We prove that if $P(A_i) \u003c (3Δ)^{-3μ_i}$ for all $i$, then for any $0 \u003c ε\u003c 1$, the probability $P\\left( \\bigcap_{i=1}^n \\overline{A}_i\\right)$ of the intersection of the complements of all $A_i$ can be computed within relative error $ε$ in polynomial time from the probabilities $P\\left(A_{i_1} \\cap \\ldots \\cap A_{i_k}\\right)$ of $k$-wise intersections of the events $A_i$ for $k = e^{O(Δ)} \\ln (n/ε)$.","short_abstract":"Let $Ω_1, \\ldots, Ω_m$ be probability spaces, let $Ω=Ω_1 \\times \\cdots \\times Ω_m$ be their product and let $A_1, \\ldots, A_n \\subset Ω$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x \\in Ω$, $x=\\left(ξ_1, \\ldots, ξ_m\\right)$, and that for each event $A_i$ there are $Δ_i$ of other e...","url_abs":"https://arxiv.org/abs/2507.10329","url_pdf":"https://arxiv.org/pdf/2507.10329v3","authors":"[\"Alexander Barvinok\"]","published":"2025-07-14T14:38:31Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}