Dictator-to-XOR Lipschitz inverse gap

Informal Question (Section 2) · arXiv:1812.09215

arXiv Question medium confidence— first stated 2021-12-10

Authors: Tom Johnston, Alex Scott

Status open high confidence

The informal question asks whether the gap between the general-map lower bound Ω(1/k)·log n and the linear-map upper bound O(1/log k)·log n (achieved by Rao–Shinkar) for the Lipschitz constant of φ⁻¹ can be closed for general maps. No follow-up paper resolving this gap was found in an extensive web search; the problem appears in an Oxford thesis/problems collection (Johnston) as still open. The conjecture is recent and narrowly specialised, so absence of a follow-up is credible.

Reviewer notes. The paper was published in Combinatorics, Probability and Computing 30 (2021) 513–525 (DOI 10.1017/S0963548320000541). The earlier related paper arXiv:1501.03016 (Rao–Shinkar) gives the O(1/log k) linear-map construction that achieves the upper bound. An Oxford DPhil thesis/problems document (ORA uuid:970b5eb2) explicitly lists the Ω(1/k) vs O(1/log k) gap as an open problem. No follow-up resolving the informal question was found after five web calls.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Does there exist a map $\phi$ from Dictator to XOR which is $C$-Lipschitz, where each output bit depends on at most $k$ input bits, and such that $\phi^{-1}$ is $o(\log n / \log k)$-Lipschitz as $n, k \to \infty$?

Context

Theorem 1 shows that for general maps the inverse must be at least $\Omega(1/k)\cdot\log n$-Lipschitz, while for linear maps the bound is $\Omega(1/\log k)\cdot\log n$-Lipschitz. Rao and Shinkar's construction achieves $\delta(2,k)=O(1/\log k)$ for linear maps, matching the linear-map lower bound, but a gap remains for general maps between $\Omega(1/k)$ and $O(1/\log k)$.

Notes. Stated in running prose as 'This raises the following question:' without a labelled theorem environment.

Source paper

Lipschitz bijections between boolean functions
Tom Johnston, Alex Scott · 2021-12-10
https://arxiv.org/abs/1812.09215 PDF source