Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma
A partition š« of ā^d is called a (k,Īµ)-secluded partition if, for every pāāā^d, the ball B_ā(Īµ, pā) intersects at most k members of š«. A goal in designing such secluded partitions is to minimize k while making Īµ as large as possible. This partition problem has connections to a diverse range of topics, including deterministic rounding schemes, pseudodeterminism, replicability, as well as Sperner/KKM-type results. In this work, we establish near-optimal relationships between k and Īµ. We show that, for any bounded measure partitions and for any dā„ 1, it must be that kā„(1+2Īµ)^d. Thus, when k=k(d) is restricted to poly(d), it follows that Īµ=Īµ(d)ā O(ln d/d). This bound is tight up to log factors, as it is known that there exist secluded partitions with k(d)=d+1 and Īµ(d)=1/2d. We also provide new constructions of secluded partitions that work for a broad spectrum of k(d) and Īµ(d) parameters. Specifically, we prove that, for any f:āāā, there is a secluded partition with k(d)=(f(d)+1)^ād/f(d)ā and Īµ(d)=1/2f(d). These new partitions are optimal up to O(log d) factors for various choices of k(d) and Īµ(d). Based on the lower bound result, we establish a new neighborhood version of Sperner's lemma over hypercubes, which is of independent interest. In addition, we prove a no-free-lunch theorem about the limitations of rounding schemes in the context of pseudodeterministic/replicable algorithms.
READ FULL TEXT