Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) some $k$ in $[n]$, while maximizing the sampled sets' overlap. Specifically, the expected difference between two output sets should be at most $α$ times their input vectors' $\ell_1$ distance. A value of $α=O(\log n)$ is known to be achievable, due to Chen et al.~(ICALP'17). We improve this factor to $O(\log k)$, independent of the ambient dimension~$n$. Our algorithm satisfies other desirable properties, including (up to a $\log^* n$ factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling and swift multi-scenario submodular welfare approximating reallocation.

Abstract We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We prove such a concentration inequality for the lower tail when the random variables satisfy negative association or negative regression, partially resolving an open problem raised in ([1]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([2, 3]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read- k families [4] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [4].

We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We prove such a concentration inequality for the lower tail when the random variables satisfy negative association or negative regression, partially resolving an open problem raised in ([Frederick Qiu and Sahil Singla, 2022]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([Chandra Chekuri et al., 2010; Nicholas J. A. Harvey and Neil Olver, 2014]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-k families [Dmitry Gavinsky et al., 2015] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [Dmitry Gavinsky et al., 2015].

Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited. This is a challenging question when the contact network is very heterogeneous, and strategies based on controlling network properties, such as the degree and spectral radius, have been shown to be effective. Implementation of such strategies requires detailed information on the contact structure, which might be sensitive in many applications. Our focus here is on choosing effective vaccination strategies when the edges are sensitive and differential privacy guarantees are needed. Our main contributions are $(\varepsilon,\delta)$-differentially private algorithms for designing vaccination strategies by reducing the maximum degree and spectral radius. Our key technique is a private algorithm for the multi-set multi-cover problem, which we use for controlling network properties. We evaluate privacy-utility tradeoffs of our algorithms on multiple synthetic and real-world networks, and show their effectiveness.