Exercises

$\tanh(x)$ is analytic on a strip $|\Im(x)| < \pi/2$. By Bernstein's theorem, Chebyshev coefficients decay as $|c_k| \leq C e^{-k \log((\pi/2)/1)} = C e^{-k \log(\pi/2)}$.

Need $e^{-d \log(\pi/2)} < 10^{-3}$, i.e., $d \log(\pi/2) > 3 \log 10 \approx 6.9$. $d > 6.9/0.45 \approx 15$.

Degree $d = 15$, so recovery threshold $K = O(15)$ workers. Reasonable for moderate cluster sizes.

ReLU $= \max(0, x)$; derivative jumps at $x = 0$. Not differentiable at that point.

For non-smooth functions, Chebyshev coefficients decay polynomially, typically as $1/k^2$.

$\sum_{k > d} 1/k^2 = O(1/d)$. Polynomial convergence.

For $10^{-3}$ error, $d \sim 10^3$ — prohibitive recovery threshold. Production ReLU coded computing requires hybrid or learned schemes.

$T + B + \log(1/\delta)/\varepsilon^2 = 3 + 5 + \log(10^5) = 3 + 5 + 11.5 = 19.5$.

$n \cdot 19.5 \cdot d = 50 \cdot 19.5 \cdot 10^5 = 9.75 \cdot 10^7$ bits per round.

FL with no constraints: $n \cdot d = 5 \cdot 10^6$ bits. Joint axis cost: $\sim 20\times$ overhead.

$\rho \approx 1 - 0.05 \cdot 0.95 = 0.9525$.

$1/(1-\rho) = 1/0.0475 \approx 21$.

Need $\sim 21$ rounds of mixing per consensus. For D-SGD with 1000 iterations, 20x overhead is tolerable.

$Q = (6 - 2)/(6 + 2) = 4/8 = 0.5$.

$C = 1 - 2/6 = 2/3 \approx 0.667$.

Actually, classical is higher here. For large $K$, classical $\to 1 - T/N = 2/3$; quantum $(N-T)/(N+T) = 0.5$. Quantum does not always outperform — the advantage depends on the regime.

Quantum advantage is for moderate $T/N$ and specific non-classical PIR variants (coded storage + colluding). Check Allaix et al. 2022 for the exact regime.

$n(n-1)p/2 = 100 \cdot 99 \cdot 0.046/2 \approx 228$.

$2 \cdot 228 = 456$ edge-exchanges.

Centralized: $100$ uploads. D-SGD with sparse graph: $456$ exchanges — $4.5\times$ more.

Sparse D-SGD doesn't save total bandwidth, but distributes it (no central bottleneck). The trade-off is resilience vs. raw efficiency.

Threshold for polynomial encoding: $K \sim 1-2$ (most schemes) — can tolerate $\sim 10-15$ stragglers per $20$.

Softmax requires degree $8$ Lagrange code: threshold $K = O(8)$. Total effective threshold: $K \approx 10$ per $20$ workers. Can tolerate $\sim 10$ stragglers.

Coding both stages reduces straggler tolerance but preserves more of the transformer pipeline. End-to-end optimization depends on the straggler rate.

If all $M$ experts are coded redundantly, the recovery threshold is $K = O(M)$. For $M = 64$, large cluster required.

Only $k = 2$ experts are active per input. Each input has a known sparse activation pattern.

Encode only the active $k$ experts' computations per input. Threshold $K = O(k)$ — much smaller.

The activation is data-dependent: different inputs use different experts. Scheduling straggler tolerance per input breaks uniform coding. Open research.

PIR rate $= C_{\text{PIR}}(5, 1000) = (1 + 0.2 + 0.04 + \ldots)^{-1} \approx 0.8$.

Effective $K = 995$. Rate $= C(5, 995) \approx 0.8$. For $K \to \infty$ the rate saturates at $1 - 1/N = 0.8$. Cache of 5 is negligible relative to $K = 1000$.

Cache helps significantly when $M \sim K$. For $M = 900, K = 1000$: effective $K = 100$, rate $\approx 0.88$. Requires large cache.

In RAG, $M \ll K$ typical (user caches a few; library has thousands). Cache-aided PIR gives minor rate improvement; its main value is recurring- document reuse.

User wants $f(\mathbf{X})$ where $\mathbf{X}$ is split across workers. Each worker computes partial information. Recovery threshold: minimum workers needed.

Consider a subset $\mathcal{S}$ of workers. The mutual information between $f(\mathbf{X})$ and $\{\text{output}_k : k \in \mathcal{S}\}$ is bounded by the joint entropy of their inputs — in the non-linear case, this is not linearly separable.

Unlike the polynomial case, non-linear $f$ can create non-additive information. Cut-set bounds are not tight; tighter bounds require computing non-linear conditional entropies — an unsolved problem in general.

Tight converses for non-linear coded computing require new techniques — e.g., matroid theory, or generalizations of Fano's inequality to non-linear regimes. An active area.

Maximize utility (e.g., user-level privacy + system-level robustness + aggregate DP) subject to $C$ budget.

$\mathcal{L} = -U(T, B, \varepsilon, \delta) + \lambda(T + B + \log(1/\delta)/\varepsilon^2 - C/(nd))$.

Equate marginal utilities across axes: $\partial U/\partial T = \partial U/\partial B = \partial U/\partial (\log(1/\delta)/\varepsilon^2)$. The optimal $(T, B, \varepsilon)$ equalize marginal benefits.

For convex utility, the Pareto frontier is a smooth curve in $(T, B, \log(1/\delta)/\varepsilon^2)$ space. For the specific form of each axis's utility (e.g., privacy is binary — either satisfied or not), the frontier is piecewise linear.

In practice, operators set $(T, B, \varepsilon)$ from requirements (privacy law, SLA, etc.) rather than maximize utility. The Pareto frontier is a check that the requirements are feasible.

For each edge $(i, j)$ in $\mathcal{G}$, peers $i$ and $j$ mutually transmit their models. Using AirComp: $O(1)$ channel use per edge.

$O(|\mathcal{E}|) = O(pn^2)$ AirComp rounds. For sparse $p = \log n / n$: $O(n \log n)$ — sub-quadratic.

Each peer-pair must synchronize independently. Harder than synchronizing a single MAC — pairwise synchronization is harder in multi-hop networks.

Per-edge AirComp provides weak privacy between each pair only: the MAC superposition hides the sum of the two models. Stronger privacy requires additional masking.

Convergence rate of D-SGD with AirComp: can the graph-mixing and per-edge MSE be combined into a unified convergence result? Open.

$C(100, 1000, 1) = (1 + 1/100 + \ldots)^{-1} \approx 0.99$. Retrieve 1 document at rate 0.99 — download $\approx 1.01$ documents' worth.

$C(100, 1000, 5) \approx 1 - 5/100 = 0.95$. Download $\approx 1.05$ documents' worth.

$C(100, 1000, 50) \approx 1 - 50/100 = 0.5$. Download $\approx 2$ documents' worth — $2\times$ overhead.

$C(100, 1000, 90) \approx 1 - 90/100 = 0.1$. Download $\approx 10$ documents — $10\times$ overhead.

For modest $T/N$, PIR overhead is negligible. For aggressive collusion tolerance, substantial. Federated RAG deployments should pick $T$ based on threat model.

Classical: $1 - T/8$. Quantum: $(8 - T)/(8 + T)$.

$(8 - T)/(8 + T) > 1 - T/8$ $\Leftrightarrow 8(8-T) > (1 - T/8)(8+T) \cdot 8$ $\Leftrightarrow 64 - 8T > (8 - T)(1 + T/8)$ $\Leftrightarrow 64 - 8T > 8 + T - T/8 - T^2/8$ Simplifying: $56 - 9T + T/8 + T^2/8 > 0$ $\Leftrightarrow 7T^2 - 72T + 448 > 0$ Roots: $T \approx 7.3 \pm i(\ldots)$ — no real roots, so LHS always positive. Quantum always at least matches classical? Let's check $T = 1$: Classical $= 7/8 = 0.875$; Quantum $= 7/9 \approx 0.778$. Quantum is lower here! The formula in Thm. 18.4.1 applies for specific PIR variants, not vanilla $T$-colluding.

The quantum advantage is specific to coded-storage PIR or SPIR, not classical $T$-colluding. For classical $T$-colluding, classical can be equal or better than quantum. The quantum advantage emerges in multi-constraint PIR variants (Allaix et al. 2022).

Characterizing the exact classical-quantum gap for each PIR variant is open. Some variants have quantum advantage; others don't.

Setup: wireless FL with $n$ users on a sparse graph (CCESA- like topology); within each neighborhood, AirComp aggregation. Combines CCESA's $O(n\sqrt{n/\log n})$ scaling with AirComp's $O(1)$ per-round cost.

Modify CCESA's sparse-graph topology so neighbors are reachable via a pair of peers with AirComp: local edges use AirComp; global consensus uses gossip + digital filter.

• Convergence rate as a function of $p$ (sparsity), $\ntn{mseagg}$ (per-edge AirComp), and graph-mixing time.
• Privacy bound: CCESA's reliability guarantees hold under AirComp aggregation?
• Practical synchronization: neighbor-synchronous AirComp vs. full global synchronization.

A successful framework would give communication-optimal wireless FL with formal privacy-robustness-DP guarantees — closing gaps in all five prior CommIT contributions simultaneously. This is the kind of sixth contribution the CommIT community could aim for.

(1) Simulate small-scale prototype. (2) Prove convergence bound. (3) Characterize threat model. (4) Test on realistic wireless channels. Each step is a year of research. The larger research program spans 3-5 years.