5 papers
Concentration from Product Moments via an Additional Element of Randomness
Michael Saks, Aravind Srinivasan, Renata Valieva
The standard method of exponential moments for proving concentration bounds can often be replaced by an argument based on elementary symmetric polynomials. We introduce an addition…
The Dirichlet Mechanism for rounding with strong negative correlation, with applications
David G. Harris, George Z. Li, Nitya Raju +1
Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" , where the goal is to select exactly one edge for each r…
Dimension-Free Correlated Sampling for the Hypersimplex
Joseph, Naor, Nitya Raju +4
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 sim…
Controlling the Spread of Epidemics on Networks with Differential Privacy
Dung Nguyen, Aravind Srinivasan, Renata Valieva +2
Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited. Th…
Concentration of Submodular Functions and Read-k Families Under Negative Dependence
Sharmila Duppala, George Z. Li, Juan Luque +2
We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We pro…