Answer: —
Theorem 11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor $\epsilon< 1/16$, and for large enough $m$, any deterministic protocol for Approval-winner-tracking uses at least $\Omega\left(\frac{mk}{\epsilon}\cdot\log\left(\frac{n}{k}\right)\right)$ bits of communication.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For \(m\) candidates and \(k\) sites, take a globally ordered stream of at most \(r\) updates \((s,A,q)\), where \(s\) is a site, \(A\subseteq C\) is an approval ballot, and \(q>0\) is a binary rational encoded in at most \(L\) bits. At each prefix, let \(\lambda(A)\) be the total mass of ballot type \(A\), \(M=\sum_A\lambda(A)\), and \(\mu(A)=\lambda(A)/M\). A candidate \(c\) is an \(\epsilon\)-winner if some nonnegative mass measure \(\nu\), with \(\sum_A\nu(A)\le\epsilon M\), makes \(c\) maximize approval score in \(\lambda+\nu\). What is the minimum worst-case communication, in bits, of a deterministic protocol that reports an \(\epsilon\)-winner after every update, as a function of \(m,k,\epsilon,r,L\) and the total-mass bound \(N\)? In particular, for \(\epsilon<1/16\) and sufficiently large \(m\), does the lower bound \(\Omega((mk/\epsilon)\log(r/k))\) hold on rational-mass streams?
Let \(C\) contain \(m\ge2\) candidates; there are \(k\ge1\) sites and one center, connected by private bidirectional links in a star. Public parameters are \(r\ge1\), \(L\ge1\), rational \(N>0\), and rational \(0<\epsilon<1\).
An adversary supplies at most \(r\) globally ordered insertions \((s,A,q)\), with \(s\in\{1,\ldots,k\}\), \(A\subseteq C\), and positive rational \(q\) whose binary numerator-denominator encoding has at most \(L\) bits; cumulative mass never exceeds \(N\). Only site \(s\) observes this insertion.
A society is represented by its support: the list of its \(\tau\) approval types with positive mass, each mass a binary rational. Here these lists are maintained locally from insertions; the center is not given the global support. \(\tau\) denotes actual support size, not \(2^m\).
At a nonempty prefix, write \(\lambda(A)\) for cumulative mass, \(M=\sum_{A\subseteq C}\lambda(A)\), and \(\mu(A)=\lambda(A)/M\). Total mass is not normalized to one. Approval uses these masses, and every score maximizer is a co-winner.
A candidate \(c\) is an \(\epsilon\)-winner if some nonnegative real mass measure \(\nu\) on all approval types satisfies \(\sum_A\nu(A)\le\epsilon M\) and makes \(c\) a co-winner in \(\lambda+\nu\); added types need not belong to the existing support.
Protocols are deterministic, with unrestricted local computation. Communication triggered by an insertion finishes before the next insertion; sites can initiate communication upon an insertion or received message, and the center upon a received message. There are no accessible clocks, public update counters, or free notifications of insertions.
After every insertion, the center's maintained answer must be an \(\epsilon\)-winner, available without further communication. Cost is the worst-case total number of transmitted bits in both directions; local output is free. Express running times, if supplied, in \(m,\tau,L,r,k\) and the encoding lengths of \(\epsilon,N\).
What is the asymptotically minimum worst-case communication \(B(m,k,\epsilon,r,L,N)\)?
For \(\epsilon<1/16\) and sufficiently large \(m\), does \(B=\Omega((mk/\epsilon)\log(r/k))\) hold on rational-mass streams, or can it fail, and in which parameter regimes?
For unit-voter streams, deterministic Approval-winner tracking has a verified lower bound \(\Omega((mk/\epsilon)\log(n/k))\) bits under these approximation conditions, and a deterministic upper bound \(O((mk/\epsilon)\log(k/\epsilon)\log n)\) bits. [Source](https://www.cs.columbia.edu/~arnoldf/papers/FT19.pdf).
No result settling the stated rational-mass communication problem was located in the literature search.
The proposed lower bound is not uniform over the stated parameters. The declared insertion limit can substantially exceed the feasible horizon; very small $\epsilon$ causes finite-horizon saturation; and the single-site case has much lower communication.
The general optimum remains open. The results below strengthen the supplied notes in two ways:
I also determine the optimum for at most two insertions when the mass cap permits every pair of admissible masses.
Let $\mathcal Q_L$ be the finite set of positive rationals admitted by the stipulated encoding. If $\mathcal Q_L$ is empty, or its minimum exceeds $N$, there are no legal insertions and $B=0$.
Otherwise, define
$$
a=\min\mathcal Q_L,\qquad
b=\max\mathcal Q_L,\qquad
R=\min\{r,\lfloor N/a\rfloor\},\qquad
W=\min\{N,Rb\}.
$$
Every insertion has mass at least $a$, so every legal stream has at most $R$ insertions. Conversely, $R$ repetitions of mass $a$ are legal. Thus $R$ is exactly the maximum feasible insertion count. At every nonempty prefix,
$$
a\le M\le W.
$$
All logarithms below have base two. Under the usual binary numerator-denominator encoding,
$$
2^{-L}\le a\le b\le2^L,
\qquad
|\mathcal Q_L|\le2^{L+1}.
$$
Using the exact alphabet $\mathcal Q_L$ avoids dependence on minor encoding conventions.
Fix a public ordering of candidates and an initial candidate $c_0$ stored at the center. No running-time bound is asserted: the protocols use unrestricted local computation, as permitted by the task.
For a mass measure $\lambda$, write
$$
S_\lambda(c)=\sum_{A\ni c}\lambda(A),
\qquad
S_\lambda^*=\max_{d\in C}S_\lambda(d).
$$
Lemma 1. A candidate $c$ is an $\epsilon$-winner if and only if
$$
S_\lambda^*-S_\lambda(c)\le\epsilon M.
$$
Proof. Suppose added mass $\nu$, of total mass $T\le\epsilon M$, makes $c$ a co-winner. For every $d$,
$$
S_\lambda(d)-S_\lambda(c)
\le S_\nu(c)-S_\nu(d)
\le T.
$$
Taking the maximum over $d$ proves necessity.
Conversely, add mass $S_\lambda^*-S_\lambda(c)$ to the approval type $\{c\}$. This makes $c$ a co-winner and uses at most $\epsilon M$ mass. The definition permits this type whether or not it belongs to the existing support. $\square$
Define the individually feasible mass alphabet
$$
\mathcal Q=\{q\in\mathcal Q_L:q\le N\}.
$$
Set
$$
\beta=1+\epsilon/2.
$$
Partition $\mathcal Q$ into the occupied intervals
$$
[a\beta^j,a\beta^{j+1}),
\qquad j=0,1,\ldots.
$$
Let $J$ be the number of occupied intervals. In each occupied interval, choose its smallest member as the public representative.
Upon an insertion $(s,A,q)$, site $s$ sends:
The center replaces $q$ by the corresponding representative $\widehat q$ and maintains an exact maximizer of the resulting rounded election $\widehat\lambda$.
For every insertion,
$$
\widehat q\le q<\beta\widehat q,
$$
so
$$
0\le q-\widehat q
<
\left(1-\frac1\beta\right)q
<
\frac{\epsilon q}{2}.
$$
Consequently, at every prefix, the total rounding loss satisfies
$$
E=M-\widehat M<\frac{\epsilon M}{2}.
$$
If $c$ maximizes the rounded scores, then, for every $d$,
$$
S_\lambda(d)-S_\lambda(c)
\le S_{\widehat\lambda}(d)+E-S_{\widehat\lambda}(c)
\le E.
$$
Lemma 1 proves correctness.
The link identifies the inserting site. The message itself supplies the notification of the insertion, so the protocol uses no free notifications. Its cost is
$$
B=O\!\left(R\bigl(m+\log(2+J)\bigr)\right).
$$
Moreover,
$$
J\le|\mathcal Q_L|
$$
and
$$
J\le1+\frac{\log(b/a)}{\log(1+\epsilon/2)}.
$$
For $0<\epsilon<1$, the usual encoding bounds therefore give
$$
\log(2+J)
=
O\!\left(
\min\left\{
L,\,
\log(2+L)+\log(1/\epsilon)
\right\}
\right).
$$
Define
$$
D=
\min\left\{
L,\,
\log(2+L)+\log(1/\epsilon)
\right\}.
$$
We have proved the improved general bound
$$
\boxed{B=O\!\left(R(m+D)\right).}
$$
In particular, for fixed $\epsilon$, communicating a mass requires only $O(\log(2+L))$ bits in this protocol.
The deterministic unit-voter protocol supplied in the task has bit communication
$$
O\!\left(
\frac{mk}{\eta}
\log(2k/\eta)\log(2+n)
\right)
$$
at approximation parameter $\eta$. Its deterministic bit bound is discussed in Section 5.2 of [Filtser–Talmon, *Distributed monitoring of election winners*](https://www.cs.columbia.edu/~arnoldf/papers/FT19.pdf).
Set
$$
h=\frac{\epsilon a}{4},
\qquad
\eta=\frac{\epsilon}{2}.
$$
Locally replace an insertion of mass $q$ by $\lfloor q/h\rfloor$ virtual unit voters with the same approval set.
Let $\widetilde\lambda$ be the virtual election scaled by $h$. Each insertion loses less than $h$, and
$$
h=\frac{\epsilon a}{4}\le\frac{\epsilon q}{4}.
$$
Thus
$$
0\le E=M-\widetilde M\le\frac{\epsilon M}{4}.
$$
If the simulated protocol returns $c$, then
$$
\begin{aligned}
S_\lambda^*-S_\lambda(c)
&\le S_{\widetilde\lambda}^*-S_{\widetilde\lambda}(c)+E\\
&\le\frac{\epsilon}{2}\widetilde M+E\\
&\le\frac{3\epsilon M}{4}.
\end{aligned}
$$
Lemma 1 again proves correctness.
Every actual insertion produces virtual voters because $q/h\ge4/\epsilon$. Their total number is at most
$$
\frac{W}{h}=\frac{4W}{\epsilon a}.
$$
Therefore
$$
B=
O\!\left(
\frac{mk}{\epsilon}
\log(2k/\epsilon)
\log\!\left(2+\frac{W}{\epsilon a}\right)
\right).
$$
The virtual insertions are local computation. All simulated communication completes before the next actual insertion, and the center receives only messages generated by the simulated protocol.
Since the protocol choice depends only on public parameters, the two bounds combine to give
$$
\boxed{
B=
O\!\left(
\min\left\{
R(m+D),\,
\frac{mk}{\epsilon}
\log(2k/\epsilon)
\log\!\left(2+\frac{W}{\epsilon a}\right)
\right\}
\right).
}
$$
When $k=1$, the site knows the entire election. It mirrors the center's current candidate, initially $c_0$. Whenever this candidate ceases to be an $\epsilon$-winner, the site sends the name of an exact maximizer.
Suppose a report occurs at mass $M_0$, followed by another report after additional mass $\Delta$. The previously reported candidate's deficit can increase by at most $\Delta$: every competitor gains at most $\Delta$, while its own score cannot decrease. A new report therefore requires
$$
\Delta>\epsilon(M_0+\Delta),
$$
and hence
$$
M_0+\Delta>\frac{M_0}{1-\epsilon}.
$$
The first report occurs at mass at least $a$, and no prefix exceeds $W$. Thus
$$
\boxed{
B(m,1,\epsilon,r,L,N)
=
O\!\left(
\log m\cdot
\min\left\{
R,\,
1+\frac{\log(W/a)}
{\log(1/(1-\epsilon))}
\right\}
\right).
}
$$
This includes the bound $O(R\log m)$.
The lower bounds use a fixed schedule of blocks, each involving one active site.
For clarity, use the following serialization convention in the communication reduction.
The public block order identifies the active site. Only that site receives insertions during the block. A fixed delivery order serializes messages initiated by the active site and all resulting messages. Center-to-site recipients are determined by the simulated center's state and message history; site-to-center messages have a fixed recipient. Thus sender and recipient identities do not need to be transmitted as arbitrary site labels.
Encode a nonempty original message by doubling its payload bits and adding a terminator. Add completion indicators for activated handlers and one marker when the active site finishes its whole block. The number of handler activations is at most the number of original messages plus the number of blocks. This gives total overhead
$$
O(\text{original transmitted bits}+\text{number of blocks}).
$$
A block may contain many unit insertions. The active site processes them locally; only one block-completion marker is required. These markers belong to the reduction and are never delivered to the simulated tracking protocol. Similarly, validation messages below do not modify its state.
Under this convention, the next transmitting role is determined by the public schedule and transcript. A fixed deterministic transcript consequently defines a rectangle in the sites' private inputs: replacing each site's input by another input consistent with that transcript preserves the transcript. This follows inductively, because each transmitted bit depends only on that site's input and its preceding received history.
Use an even number $K=2p$ of sites. There is a code
$$
\mathcal E\subseteq\{0,1\}^p
$$
with pairwise Hamming distance greater than $p/4$ and
$$
|\mathcal E|\ge2^{\gamma p},
\qquad
\gamma=1-H_2(1/4)>0,
$$
where
$$
H_2(u)=-u\log u-(1-u)\log(1-u).
$$
To prove this, greedily select strings and remove Hamming balls of radius $\lfloor p/4\rfloor$. Each ball contains at most
$$
\sum_{j=0}^{\lfloor p/4\rfloor}\binom pj
\le2^{H_2(1/4)p}
$$
strings. For the last inequality, put $u=1/4$. For every integer $j\le p/4$,
$$
u^j(1-u)^{p-j}
\ge u^{p/4}(1-u)^{3p/4}.
$$
Apply this inequality to the corresponding terms in the binomial expansion of $(u+(1-u))^p=1$. The greedy packing bound follows.
For each candidate and each of $t$ phases, independently choose a codeword. In site pair $j$, assign its $j$th bit to the first site and the complementary bit to the second. Every candidate is therefore approved by exactly $p$ sites in each phase.
There are at least
$$
|\mathcal E|^{mt}\ge2^{\gamma mpt}
$$
such arrays.
Consider two different arrays. At some phase-candidate coordinate their codewords differ in $d>p/4$ positions. Mix the arrays by selecting each site's entire input from one of the two arrays, choosing an approving row whenever possible at that coordinate. The selected candidate then has
$$
p+d>\frac{5p}{4}
$$
approving sites.
Consequently, these arrays form a fooling family for the promise problem:
If two members of the family shared a transcript of a correct deterministic protocol, their positive mixed input would share that transcript, contradicting correctness. Counting transcripts gives a lower bound
$$
\Omega(mKt)
$$
bits.
Let $q_s>0$ be the public aggregate block mass in phase $s$, and define
$$
x_1=0,
\qquad
x_{s+1}=x_s+q_s.
$$
In phase $s$:
A block can be one weighted insertion or several equal-weight insertions.
At the beginning of phase $s$, every site has total mass $2x_s$, and every candidate has local score $x_s$. The complementary block restores this invariant with $x_s$ replaced by $x_{s+1}$.
At the inspected prefix, if candidate $c$ has $h_c$ current approving sites, then
$$
S(c)=Kx_s+h_cq_s,
\qquad
M=K(2x_s+q_s).
$$
Assume
$$
\frac{q_s}{4}>2\epsilon(2x_s+q_s).
$$
If some candidate has more than $5p/4$ approvals, its score exceeds that of every candidate with at most $p$ approvals by more than
$$
\frac{pq_s}{4}
>
\epsilon K(2x_s+q_s)
=
\epsilon M.
$$
Thus an $\epsilon$-winner must have more than $p$ approvals.
The reduction broadcasts the maintained candidate's name and collects its membership bit from every site. A negative input never yields more than $p$ memberships; a positive input necessarily does so at its relevant phase.
Validation and block markers cost
$$
O\!\left(t(K+\log m)\right)
$$
bits, in addition to a constant multiple of the tracking communication. For sufficiently large $m$, this overhead is absorbed by the fooling-family lower bound.
We have proved:
Lemma 2. If $t$ phases are legally realizable and satisfy
$$
\frac{q_s}{4}>2\epsilon(2x_s+q_s)
$$
in every phase, then
$$
B=\Omega(mKt)
$$
for sufficiently large $m$.
Assume
$$
k\ge2,\qquad R\ge2,\qquad 0<\epsilon<1/16.
$$
Theorem 3. For sufficiently large $m$,
$$
\boxed{
B=
\Omega\!\left(
\frac{mk}{\epsilon}
\log\!\left(1+\frac{\epsilon R}{k}\right)
\right).
}
$$
Proof for a fixed even number of sites. First use $K\le k$ even, with $R\ge2K$. Implement every elementary insertion with mass $a$. Set
$$
q_1=a,
\qquad
q_s=a\left\lceil\frac{32\epsilon x_s}{a}\right\rceil
\quad(s\ge2).
$$
These are aggregate block masses; the elementary insertions all have the admissible mass $a$.
For phase one, Lemma 2's inequality follows from $\epsilon<1/16$. For subsequent phases,
$$
q_s\ge32\epsilon x_s,
$$
so
$$
\begin{aligned}
q_s(1/4-2\epsilon)-4\epsilon x_s
&\ge
32\epsilon x_s(1/4-2\epsilon)-4\epsilon x_s\\
&=
4\epsilon x_s(1-16\epsilon)>0.
\end{aligned}
$$
This is the required inequality.
Writing $u_s=x_s/a$ gives
$$
u_{s+1}\le(1+32\epsilon)u_s+1,
\qquad u_1=0.
$$
Induction yields
$$
u_{t+1}
\le
\frac{(1+32\epsilon)^t-1}{32\epsilon}.
$$
Both approval and complementary blocks together use $2Ku_{t+1}$ insertions. Therefore choose
$$
t=
\left\lfloor
\frac{\log(1+16\epsilon R/K)}
{\log(1+32\epsilon)}
\right\rfloor.
$$
The construction uses at most $R$ insertions and hence mass at most $Ra\le N$.
Because $R\ge2K$, the expression being floored is at least one, so its floor is at least half its value. Also $\log(1+32\epsilon)=O(\epsilon)$. Lemma 2 gives
$$
B=
\Omega\!\left(
\frac{mK}{\epsilon}
\log\!\left(1+\frac{\epsilon R}{K}\right)
\right).
$$
Choosing the number of active sites. For $R\ge4$, take
$$
K=
2\left\lfloor
\frac{\min\{k,R/2\}}2
\right\rfloor.
$$
Then $R\ge2K$ and
$$
K\ge\frac12\min\{k,R/2\}.
$$
If $k\le R/2$, then $K\ge k/2$, and the last lower bound is at least a constant multiple of the claimed bound.
If $k>R/2$, then $K\ge R/4$ and
$$
\frac{\epsilon R}{K}\le4\epsilon<1/4.
$$
Using $\log(1+z)\ge z/((1+z)\ln2)$, the lower bound is $\Omega(mR)$. This implies the claimed bound because
$$
\frac{k}{\epsilon}\log(1+\epsilon R/k)
\le\frac{R}{\ln2}.
$$
For $R=2$ or $R=3$, it remains to prove $\Omega(m)$ communication. Two sites insert mass $a$, approving respectively $U$ and $V$. If $U\cap V$ is nonempty, every $\epsilon$-winner lies in the intersection: such candidates have score $2a$, while all others have score at most $a$, and
$$
a>2\epsilon a.
$$
Thus the tracker, followed by candidate-membership validation, decides whether $U\cap V$ is empty. The $2^m$ pairs
$$
(U,C\setminus U)
$$
form a fooling family for this decision problem: for distinct $U,U'$, at least one crossed pair has nonempty intersection. Hence the decision problem requires at least $m-O(1)$ bits. Validation and serialization add only $O(\log m)$ bits, proving $B=\Omega(m)$.
For $R\in\{2,3\}$, the claimed expression is $O(mR)=O(m)$, completing the proof. $\square$
For $0\le z\le1$, $\log(1+z)$ is bounded above and below by positive constant multiples of $z$. Therefore, if
$$
k\ge2,\qquad R\ge2,\qquad
\frac{\epsilon R}{k}\le1,
$$
Theorem 3 gives $B=\Omega(mR)$.
Combining this with Section 3.1 proves:
$$
\boxed{
B=\Theta(mR)
\quad\text{if}\quad
\frac{\epsilon R}{k}\le1
\ \text{and}\ D=O(m),
}
$$
for $\epsilon<1/16$ and sufficiently large $m$.
This resolves a substantial regime of simultaneous parameter growth.
Assume
$$
r=2,\qquad k\ge2,\qquad
N\ge2b,\qquad
0<\epsilon<1/16.
$$
The mass-cap condition ensures that every pair of admissible masses is legal.
Define
$$
\rho=\frac{1+\epsilon}{1-\epsilon}.
$$
Let $P$ be the maximum cardinality of a subset of $\mathcal Q_L$ whose elements, in increasing order, have consecutive ratios strictly greater than $\rho$.
Theorem 4. For sufficiently large $m$,
$$
\boxed{B=\Theta\!\left(m+\log(2+P)\right).}
$$
Use the multiplicative-grid protocol from Section 3.1. We show that its number of occupied bins satisfies
$$
J\le8P.
$$
Greedily select the smallest remaining mass $q$, remove all remaining masses in $[q,\rho q]$, and repeat. The selected masses form a $\rho$-separated set, so their number is at most $P$. Their removal intervals cover $\mathcal Q_L$.
Each such interval intersects at most
$$
\left\lceil
\frac{\log\rho}{\log(1+\epsilon/2)}
\right\rceil+2
$$
grid bins. For $\epsilon<1/16$,
$$
\ln\rho\le\frac{2\epsilon}{1-\epsilon},
\qquad
\ln(1+\epsilon/2)\ge\frac{\epsilon}{2+\epsilon}.
$$
Their ratio is less than $5$, so eight bins suffice. Hence $J\le8P$.
There are at most two insertion messages, giving
$$
B=O(m+\log(2+P)).
$$
The two-insertion intersection construction in Theorem 3 is legal because $N\ge2b\ge2a$. It gives
$$
B=\Omega(m).
$$
Choose separated masses
$$
q_1<\cdots<q_P.
$$
Fix two candidates $c,d$. Site one inserts $(\{c\},x)$, followed by site two inserting $(\{d\},y)$.
For $i<j$, separation gives
$$
q_j-q_i>\epsilon(q_i+q_j).
$$
Thus $d$ is the unique $\epsilon$-winner on $(x,y)=(q_i,q_j)$, while $c$ is the unique $\epsilon$-winner on $(q_j,q_i)$.
Consider the $P$ diagonal inputs $(q_i,q_i)$. If two diagonals shared a transcript, the rectangle property would give that same transcript on both crossed inputs. The center would return the same candidate on those inputs, contradicting their different unique $\epsilon$-winners.
Consequently there are at least $P$ transcripts. Serialization adds only constant overhead for the two insertion blocks, yielding
$$
B=\Omega(\log P)-O(1).
$$
Combining the two lower bounds proves the theorem. $\square$
Under the usual binary numerator-denominator encoding, for sufficiently large $L$,
$$
\log(2+P)
=
\Theta\!\left(
\min\{L,\log(2+L)+\log(1/\epsilon)\}
\right).
$$
The upper bound follows from $P\le|\mathcal Q_L|$ and
$$
(P-1)\log\rho<\log(b/a)=O(L),
$$
with $\log\rho$ bounded below by a positive constant multiple of $\epsilon$.
For the lower bound, powers of two with exponents between zero and a sufficiently small constant multiple of $L$ are admissible. Their ratios are $2>\rho$, giving
$$
P=\Omega(L).
$$
Also choose $d=\lfloor cL\rfloor$ for a sufficiently small fixed $c>0$. The dyadic rationals
$$
\frac{j}{2^d},
\qquad
2^d\le j\le2^{d+1},
$$
are admissible. Set
$$
h=\lfloor4\epsilon2^d\rfloor+1.
$$
Taking every $h$th numerator gives a set of size
$$
\Omega\!\left(\min\{2^d,1/\epsilon\}\right).
$$
Distinct selected masses differ by more than $4\epsilon$. Since both lie in $[1,2]$, their difference exceeds $\epsilon$ times their sum, which is equivalent to ratio greater than $\rho$.
These constructions give both
$$
\log(2+P)=\Omega(\log(2+L))
$$
and
$$
\log(2+P)=\Omega(\min\{L,\log(1/\epsilon)\}).
$$
Together they imply the asserted lower bound.
Thus Theorem 4 becomes
$$
\boxed{
B=
\Theta\!\left(
m+\min\{L,\log(2+L)+\log(1/\epsilon)\}
\right)
}
$$
in this two-insertion regime.
Assume
$$
k\ge2,\qquad
N\ge ra,\qquad
r/k\ge\epsilon^{-2},\qquad
0<\epsilon<1/16.
$$
Then $R=r$. Writing $y=r/k$, we have $\epsilon y\ge\sqrt y$, so
$$
\log(1+\epsilon y)\ge\frac12\log y.
$$
Theorem 3 consequently proves
$$
\boxed{
B=\Omega\!\left(
\frac{mk}{\epsilon}\log(r/k)
\right).
}
$$
These are sufficient conditions, not a characterization of all regimes.
If $R=1$, the observing site sends the name of any approved candidate when needed. If its approval set is empty, the initial candidate remains a winner. Thus communication is $O(\log m)$.
Conversely, singleton approval sets at one fixed site force $m$ different answers, since $\epsilon<1$. Transcript counting gives $\Omega(\log m)$. Therefore
$$
\boxed{B=\Theta(\log m)\quad\text{when }R=1.}
$$
The declared $r$ can be arbitrarily large.
The failure persists with a growing feasible horizon. Fix $k=2$, $\epsilon=1/32$, and constant $L$ admitting a positive rational. Set
$$
N=a\lfloor\log r\rfloor.
$$
Then $R=\lfloor\log r\rfloor$. The virtual-voter upper bound gives $O(m\log R)$, while Theorem 3 gives $\Omega(m\log R)$. Hence
$$
B=\Theta(m\log\log r).
$$
The proposed expression has order $m\log r$, exceeding the optimum by an unbounded factor.
More generally, for fixed $k\ge2$, fixed $\epsilon<1/16$, and fixed admissible $L$, as $R$ tends to infinity,
$$
B=\Theta(m\log R)
$$
for sufficiently large $m$.
Fix $k=2$ and constant admissible $L$, and take
$$
N=ra,\qquad \epsilon=r^{-2}.
$$
Then $R=r$ and $D=O(1)$. Section 3.1 gives $B=O(mr)$, and the saturation regime gives the matching lower bound:
$$
B=\Theta(mr).
$$
The proposed expression is
$$
\Theta(mr^2\log r),
$$
so it fails by an unbounded factor.
This obstruction already occurs when every insertion has the same mass. The supplied unit-voter formula therefore also requires a parameter regime; it cannot be uniform over arbitrarily small $\epsilon$ and finite horizons.
Fix $\epsilon=1/32$, constant admissible $L$, $N=ra$, and $k=1$. Then $W/a=O(r)$, so Section 3.3 gives
$$
B=O(\log m\log r).
$$
For example, with $m=r^2$, this is $O((\log r)^2)$, while the proposed expression has order $r^2\log r$.
Thus the single-site exception is intrinsic to the stated model.
The mass cap alone does not force logarithmic dependence on the insertion count.
Fix
$$
k=2,\qquad
\epsilon=1/32,\qquad
N=2,\qquad
L=\Theta(r).
$$
Then, for sufficiently large $m$,
$$
\boxed{B=\Theta(mr).}
$$
To prove the lower bound, let $c_0$ be a fixed encoding constant such that $2^{-u}$ has encoding length at most $c_0(u+1)$. Choose
$$
t=
\min\left\{
\lfloor r/4\rfloor,\,
\lfloor L/(2c_0)\rfloor
\right\}.
$$
For sufficiently large parameters, $t=\Theta(r)$ and all masses below are admissible.
Use Lemma 2 with
$$
q_1=2^{-t},
\qquad
q_s=2^{s-2-t}\quad(s\ge2).
$$
The recurrence gives
$$
x_s=q_s\quad(s\ge2),
\qquad
x_{t+1}=1/2.
$$
There are four insertions per phase, so the insertion count is $4t\le r$. The final mass is
$$
2Kx_{t+1}=2,
$$
and every preceding prefix has smaller mass.
For phase one, Lemma 2's inequality holds directly. For every subsequent phase,
$$
\frac{q_s}{4}=\frac{x_s}{4}
>
\frac{3x_s}{16}
=
2\epsilon(2x_s+q_s).
$$
Thus $B=\Omega(mt)=\Omega(mr)$.
For the upper bound, $a\ge2^{-L}$ and $W\le2$. The virtual-voter protocol, with fixed $k$ and $\epsilon$, costs
$$
O(m(L+1))=O(mr).
$$
This example shows why rational-mass tracking cannot generally be described solely by the logarithmic horizon dependence of equal-weight streams.
The general upper and lower bounds do not match for arbitrary simultaneous growth of the parameters. In particular, outside the saturation and special regimes proved above, the necessity of the factors involving $k$, $\epsilon$, and the available mass range remains undetermined.
The main unresolved target is the asymptotically minimum value of $B(m,k,\epsilon,r,L,N)$ in full generality. The proposed lower bound has been proved in a concrete sufficient regime and disproved as a uniform assertion, but its complete regime characterization remains open.
⟨structured verdict parsed — rendered above⟩
Overall assessment: correct and substantial partial progress, with minor clarification issues. I found no false central mathematical step in the stated constructions. The output establishes upper bounds, lower bounds, several matching regimes, and counterexamples to the proposed uniform lower bound. It does not determine the asymptotically minimum communication for all parameters, and explicitly acknowledges this.
The lower-bound verification uses the natural convention that every transmitted message contains at least one charged bit. That convention, and the precise interpretation of the serialization procedure, should be stated explicitly.
The definitions
$$
a=\min\mathcal Q_L,\qquad
R=\min\{r,\lfloor N/a\rfloor\}
$$
correctly identify the maximum feasible insertion count when legal insertions exist.
Both directions are justified:
The prefix bounds
$$
a\le M\le W=\min\{N,Rb\}
$$
are also correct. The argument does not require $W$ itself to be attainable.
The claims
$$
2^{-L}\le a\le b\le2^L,\qquad
|\mathcal Q_L|\le2^{L+1}
$$
are valid under the usual interpretation that the combined binary encoding of numerator and denominator has length at most $L$.
Minor issue: the precise encoding convention is not specified. The alphabet-based results avoid this ambiguity, but the explicit dependence on $L$, especially the admissibility constructions in Sections 6 and 8, requires an explicit convention.
Minimum clarification: specify how numerator, denominator, and any separators contribute to encoding length, and state that the encoding constants are fixed independently of the public parameters.
Lemma 1 is correct.
For necessity, the displayed inequality
$$
S_\lambda(d)-S_\lambda(c)
\le S_\nu(c)-S_\nu(d)
\le \sum_A\nu(A)
$$
uses precisely the co-winner condition and nonnegativity of the added measure.
For sufficiency, adding the deficit to the singleton type $\{c\}$ raises only $c$’s score. The added mass is nonnegative and satisfies the budget exactly when
$$
S_\lambda^*-S_\lambda(c)\le\epsilon M.
$$
The construction respects the permission to add types outside the current support. No normalization assumption is introduced.
The representative of an occupied interval satisfies
$$
\widehat q\le q<\beta\widehat q,
\qquad
\beta=1+\epsilon/2.
$$
Consequently, the stated rounding loss bound is correct:
$$
0\le q-\widehat q<\frac{\epsilon q}{2}.
$$
At every prefix, the loss of any candidate’s score is at most the total mass loss $E$. Therefore, a maximizer of the rounded scores has original deficit at most $E$. This proves correctness through Lemma 1.
The protocol sends a message on every insertion and obtains the site identity from the link, so it does not rely on free insertion notifications.
The bounds on occupied intervals and the resulting communication bound
$$
B=O\!\left(R(m+D)\right)
$$
are correct under the stated usual encoding interpretation. The center need not know the actual global support beforehand.
The rounding calculation is correct. Each insertion loses less than
$$
h=\frac{\epsilon a}{4}\le\frac{\epsilon q}{4},
$$
so
$$
E\le\frac{\epsilon M}{4}.
$$
The transfer of the approximate-winner guarantee correctly gives
$$
S_\lambda^*-S_\lambda(c)
\le\frac{\epsilon}{2}\widetilde M+E
\le\frac{3\epsilon M}{4}.
$$
Every insertion generates at least one virtual voter, and the total number is bounded by
$$
\frac{4W}{\epsilon a}.
$$
The cited deterministic unit-voter upper bound is the one supplied in the task and discussed in Section 5.2 of the [Filtser–Talmon paper](https://www.cs.columbia.edu/~arnoldf/papers/FT19.pdf). The paper’s model excludes accessible clocks, and its checkpoint construction triggers center actions through received count updates. The simulation therefore respects the relevant triggering restrictions.
The two public-parameter-dependent protocol choices can legitimately be combined by taking the smaller bound.
The site can determine whether the center’s current candidate is an $\epsilon$-winner because it holds the entire election.
Between two reports, the previous exact winner’s deficit increases by at most the added mass $\Delta$. Hence the necessary condition for another report,
$$
\Delta>\epsilon(M_0+\Delta),
$$
and the resulting multiplicative growth condition are correct.
The report-count and bit bounds follow. The first report and the possibility of no reports are handled by the additive constant.
The intended reduction is reasonable: communication is serialized into a public transcript while the simulated tracking protocol receives only its original messages. Public block-completion markers do not give the tracker forbidden notifications.
Two details need clarification.
Minor issue: nonempty-message convention. The overhead bound uses the fact that the number of original messages is bounded by the original transmitted bits. This requires every message to contain at least one charged bit. The task does not explicitly state this convention.
Without it, arbitrarily many empty messages would invalidate that particular accounting argument. Under the natural standard convention, this is an expositional issue rather than a mathematical obstruction.
Minimum clarification: state the positive-length message convention used in the communication model.
Minor issue: handler counting and reduction model. The sentence bounding handler activations by messages plus blocks is not literally valid if every insertion-triggered handler is counted separately. The following paragraph evidently intends to process silent insertions internally within a block, but the accounting should say so explicitly.
Also, the validation cost
$$
O\!\left(t(K+\log m)\right)
$$
uses a public broadcast reduction. Sending the candidate separately over all private tracking links would have a different cost.
Minimum clarification: specify that the reduction operates with a public broadcast transcript, and identify precisely which handler completions receive markers. Explicitly explain that silent insertion processing receives no separate marker.
Subject to these conventions, the transcript-rectangle argument is valid: a site’s actions depend on its own input and received history, while the center has no private stream input.
The code construction is correct. The entropy estimate bounds the Hamming-ball volume, and greedy packing gives the claimed exponential code size, including small positive values of $p$.
Complementary site pairs give exactly $p$ approvals for every candidate in every phase.
For two different arrays, mixing entire site inputs at a differing phase-candidate coordinate produces
$$
p+d>\frac{5p}{4}
$$
approvals. The mixing is compatible with rectangle arguments because each site contributes its entire private input from one of the two arrays.
The resulting fooling-family count establishes
$$
\Omega(mKt)
$$
communication in the serialized reduction.
The phase invariant, inspected-prefix scores, and total mass are correct:
$$
S(c)=Kx_s+h_cq_s,\qquad
M=K(2x_s+q_s).
$$
The phase condition guarantees that a candidate with more than $5p/4$ approvals exceeds every candidate with at most $p$ approvals by more than $\epsilon M$.
Validation therefore distinguishes negative inputs from promised positive inputs. Intermediate inputs outside the promise cause no problem.
For sufficiently large $m$, the stated validation and marker overhead is absorbed by the fooling-family bound. Lemma 2 follows, subject to the serialization clarifications above.
The phase construction satisfies the required inequality. The critical computation is correct:
$$
32\epsilon x_s(1/4-2\epsilon)-4\epsilon x_s
=
4\epsilon x_s(1-16\epsilon)>0.
$$
The recurrence and its geometric bound are correct. The chosen phase count ensures
$$
2Ku_{t+1}\le R,
$$
so the elementary insertions are legal both in count and total mass.
The floor estimate applies because $R\ge2K$ makes the unfloored expression at least one.
The choice of an even active-site count handles both ranges of $k$ correctly. In the range $k>R/2$, the logarithmic estimate yields $\Omega(mR)$, which implies the stated bound.
For $R\in\{2,3\}$, the intersection reduction is valid. A nonempty intersection forces every approximate winner into it, and the displayed complementary pairs form a fooling family.
Thus Theorem 3 is established under the clarified communication conventions.
The saturation conclusion
$$
B=\Theta(mR)
$$
also follows under its stated conditions, including $D=O(m)$.
The upper-bound covering argument is correct. Greedy removal intervals cover the mass alphabet, and each interval meets only a constant number of multiplicative bins. The asserted constant of eight is sufficient.
For the precision lower bound, separated masses satisfy
$$
q_j-q_i>\epsilon(q_i+q_j).
$$
The two crossed inputs consequently have different unique $\epsilon$-winners. The diagonal-input rectangle argument therefore forces at least $P$ transcripts.
The approval-set lower bound and precision lower bound combine correctly to yield
$$
B=\Theta\!\left(m+\log(2+P)\right).
$$
The explicit encoding dependence is also correct for the usual combined numerator-denominator encoding:
The only clarification needed here is the encoding convention already identified.
The sufficient regime is correctly derived. With $R=r$ and $r/k\ge\epsilon^{-2}$,
$$
\log(1+\epsilon r/k)\ge\frac12\log(r/k),
$$
so Theorem 3 implies the proposed lower bound.
The failure examples are valid:
These examples genuinely disprove uniformity over the parameters. They do not rely on an unintended degenerate interpretation.
The observation that the unit-voter lower-bound formula also requires a parameter regime is consistent with the finite-horizon upper bound.
The geometric masses satisfy the claimed recurrence:
$$
x_s=q_s\quad(s\ge2),\qquad
x_{t+1}=1/2.
$$
There are four insertions per phase, and the final mass is exactly $2$. The phase inequality at $\epsilon=1/32$ is correctly checked.
With the stated ordinary encoding convention, the choice of $t$ makes the masses admissible and gives $t=\Theta(r)$.
The upper bound follows from $a\ge2^{-L}$ and $W\le2$. Thus the stated
$$
B=\Theta(mr)
$$
example is established.
Major scope issue: the task asks for the asymptotically minimum communication in general. The output leaves unmatched upper and lower bounds outside its special regimes.
This is acknowledged incompleteness, not an erroneous claim of a complete solution. The established results remain useful and support another round.
Minimum additional work: settle the unmatched parameter regimes before claiming a general asymptotic formula. Merely clarifying the existing arguments cannot supply that missing result.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.