2026-07-25T23:43:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25391 2026-03-19T13:04:25Z ddc:004 open_access

Dimension-Free Correlated Sampling for the Hypersimplex Naor, Joseph (Seffi) Raju, Nitya Shetty, Abhishek Srinivasan, Aravind Valieva, Renata Wajc, David Correlated Rounding Dependent Rounding 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) k ∈ [n], while maximizing the overlap of the sampled sets. Specifically, the expected difference between two output sets should be at most α times their input vectors' 𝓁₁ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joseph (Seffi) Naor and Nitya Raju and Abhishek Shetty and Aravind Srinivasan and Renata Valieva and David Wajc 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.104 urn:nbn:de:0030-drops-253918 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.104 eng https://creativecommons.org/licenses/by/4.0/legalcode