2022/11/03 by Karthik Natarajan, Natarajan, Karthik, Arjun Ramachandra +3
Computer Science · #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2211.01596
A collection of n random events is said to be (n - 1)-wise independent if any n - 1 events among them are mutually independent. We characterise all probability measures with respect to which n random events are (n - 1)-wise independent. We provide sharp upper and lower bounds on the probability that at least k out of n events with given marginal probabilities occur over these probability measures. The bounds are shown to be computable in polynomial time.