Imagine you're running a relay race where the baton must be passed without any runner ever seeing the other runners — they can only share a pre-agreed playbook (shared randomness) and shout limited messages into the void. The question this paper answers is: how thick does that playbook need to be before the relay works reliably? The committed claim: shared randomness for robust conditional disclosure of secrets (CDS) is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unlimited. Additionally, for one-sided-perfect f-routing, entanglement cost is lower bounded by sign rank, yielding the first linear lower bound for the inner-product function that matches the known upper bound. Two results, both resolving or significantly advancing open problems in non-local quantum computation (NLQC). The ladder matters here. Prior to this work, proving lower bounds on entanglement cost for f-routing in any robust setting was listed as a major open problem. Allerstorfer et al. (Quantum 2024) established the CDS-to-f-routing connection but left the lower bound question open. Asadi, Culf, and May (ITCS 2025) introduced the low-rank matrix positivity method but did not extract tight bounds for specific functions. This paper exploits that positivity structure to get tightness for inner-product — the benchmark function — and simultaneously establishes the CDS randomness bound as a standalone contribution. The equality function achieves tightness on the CDS side. Architecturally, this is pure complexity-theoretic proof work — no algorithms, no simulations, no hardware. The method family is combinatorial lower bounds via matrix-analytic techniques: sign rank, rank arguments, and the interplay between communication complexity models (SMP) and cryptographic primitives (CDS). The key structural move is treating the low-rank matrix in the Asadi-Culf-May framework not just as a certificate of impossibility but as a quantitative tool whose positivity yields exact constants. This is pen-and-paper mathematics, not computation. Integrity is assessed differently for proof papers than for experimental work. The validation is mathematical proof, which is the gold standard for its domain — no cherry-picking risk, no benchmark selection bias, no stale baselines. The results are stated as theorems with formal proofs across 29 pages. The tightness claims are verifiable: the inner-product lower bound matches a known upper bound, and the CDS bound matches for the equality function. The main integrity question is whether the proofs are correct, which requires peer review and community verification — standard for papers at this stage. The milestone trajectory for NLQC lower bounds has been stuck for years. The field's central open problem remains proving entanglement lower bounds for fully robust f-routing (constant error on both input classes, not just one). This paper solves the one-sided-perfect case. The gap between one-sided-perfect and fully robust is the explicit next frontier. If fully robust linear lower bounds for inner-product were established, it would have direct implications for quantum position verification security — the applied motivation driving this entire line of work. The obvious experiment not run: extending from one-sided-perfect to fully robust f-routing. The authors are transparent that their sign-rank technique specifically exploits the exactness on one input class. The fully robust case likely requires fundamentally new ideas beyond positivity of the low-rank matrix. Honest read: this isn't (b) or (c) — it's a genuine technical barrier. The method doesn't generalize, and the authors know it. They've pushed their tool to its natural limit and are signaling where the next tool needs to come from.
