Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma

Abstract

A partition $\mathcal{P}$ of ${\mathbb{R}}^d$ is called a $(k,\epsilon )$-secluded partition if, for every $\vec{p}\in {\mathbb{R}}^d$, the ball ${\overline{B}}_{\infty }(\epsilon ,\vec{p})$ intersects at most $k$ members of $\mathcal{P}$. A goal in designing such secluded partitions is to minimize $k$ while making $\epsilon$ 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 $\epsilon$. We show that, for any bounded measure partitions and for any $d\ge 1$, it must be that $k\ge (1+2\epsilon {)}^d$. Thus, when $k=k(d)$ is restricted to $\mathrm{poly}(d)$, it follows that $\epsilon =\epsilon (d)\in O\left(\frac{\ln d}{d}\right)$. This bound is tight up to log factors, as it is known that there exist secluded partitions with $k(d)=d+1$ and $\epsilon (d)=\frac{1}{2d}$. We also provide new constructions of secluded partitions that work for a broad spectrum of $k(d)$ and $\epsilon (d)$ parameters. Specifically, we prove that, for any $f:\mathbb{N}\to \mathbb{N}$, there is a secluded partition with $k(d)=(f(d)+1{)}^{\lceil \frac{d}{f(d)}\rceil }$ and $\epsilon (d)=\frac{1}{2f(d)}$. These new partitions are optimal up to $O(\log d)$ factors for various choices of $k(d)$ and $\epsilon (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.