| paper | d4-conf-atal-2017-0136 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 11
statement extracted from the paper’s text layer
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?
At every prefix, the sites’ rational mass updates induce a society distribution \(\mu\) over approval types \(A\subseteq C\); the sites retain their own ordered histories because the task is distributed monitoring. The protocol must output, after each update, a candidate that can become an approval winner by adding at most \(\epsilon M\) mass. The objective is to minimize worst-case communication, parameterized by \(m,k,\epsilon,r,L\), and total mass \(N\).
The input must retain the sites’ ordered update histories; a single μ does not encode the communication task, and the paper gives no algorithmic complexity result for that static society.
fatal: False
The mirror covers Theorems 11 and 10, the deterministic Approval and randomized two-candidate Plurality communication lower bounds. It leaves the paper’s upper-bound protocols in Theorems 2–9 and other voting rules aside.
The strongest mirror is Continuous Distributed Approval-Winner Tracking. It keeps the paper’s center, \(k\) sites, and requirement to report a candidate whenever queried. The change is to the population representation: each site receives a sequence of ballot-type mass updates \((A,q)\), where \(A\subseteq C\) is an approval ballot and \(q>0\) is a binary rational. Time remains the discrete order of updates; an update may represent a cohort rather than one voter.
At a prefix of the stream, let \(\lambda(A)\) be the total mass with ballot \(A\), \(M=\sum_A\lambda(A)\), and \(\mu(A)=\lambda(A)/M\) the society’s distribution over approval types. Candidate \(c\)’s score is \(\sum_{A\ni c}\mu(A)\). Call \(c\) an \(\epsilon\)-winner if there is a nonnegative mass measure \(\nu\) over approval ballots with \(\sum_A\nu(A)\le\epsilon M\) such that \(c\) maximizes approval score in \(\lambda+\nu\). The problem is to give the center a protocol that outputs an \(\epsilon\)-winner after every update, with the required guarantee and minimum communication. An instance specifies \(C,k,\epsilon\), the sites’ local update streams, and their rational masses; the solution is such a protocol. Its complexity can be stated in \(m,k,\epsilon\), total mass \(N\) relative to a fixed reference mass, and the encoding length \(L\).
My lead anchor is Theorem 11, proved in this paper. It says that, for \(\epsilon<1/16\) and sufficiently large \(m\), every deterministic protocol for Approval-winner-tracking uses at least \(\Omega((mk/\epsilon)\log(n/k))\) bits. The paper proves this via its No Strict Majority communication lower bound and a reduction to Approval tracking. Its proof explicitly permits non-integer voter quantities in the reduction and argues that rounding changes the bound by only a constant factor. That is unusually direct evidence that replacing unit voters with cohort mass preserves the authors’ problem: the approval score, the \(\epsilon\)-winner criterion, and the sites’ information constraints all stay intact. In the mass version, the corresponding question asks whether every deterministic protocol needs \(\Omega((mk/\epsilon)\log(N/k))\) bits on the analogous mass instances.
A second, distinct anchor is Theorem 10, also proved in this paper, though its small-\(k\) argument uses a Count-tracking lower bound cited from Huang et al. It states that any randomized protocol for Plurality-winner-tracking needs \(\Omega((\epsilon^{-1}\sqrt{k}+k)\log n/\log k)\) words, even with only two candidates. Its mirror, Continuous Two-Candidate Plurality-Winner Tracking, uses the same mass-stream model with types \(a\) and \(b\): sites receive rational mass of either ballot, and after every update the center must output a candidate that can become a Plurality winner by adding at most \(\epsilon M\) mass. The solution is a randomized protocol with the paper’s constant-success guarantee; communication is measured in words of \(\Theta(\log N)\) bits. The finite streams are a subclass of these rational-mass streams, so the stated lower bound carries over to this version.
The regime is credible for regional polling stations or data centers aggregating an enormous number of respondents or customers. A type is a complete approval set over the \(m\) candidates or products; all people with the same set are interchangeable for this task. In the two-candidate anchor there are only two possible types, however large the population. In the Approval reduction, many agents arrive in cohorts sharing ballot types, while the constructed instance’s total mass grows across its phases. The paper’s own retail and polling examples support this kind of setting. Its phrase “continuous distributed monitoring” describes monitoring throughout a stream; its input voters remain discrete. The mirror continuizes the population by assigning rational mass to ballot types.
I expect the lower bounds to persist: this is the programme’s hardness-transfers case, in the communication-complexity sense. The discrete streams embed in the mass problem, and Theorem 11’s proof already uses fractional quantities. That also gives concrete follow-up questions: does a comparable lower bound hold for randomized Approval tracking, and how do continuous protocols’ bounds depend jointly on support size \(\tau\) and mass encoding length \(L\)? This proposal covers Theorems 10 and 11 only; it does not recast the paper’s upper bounds or every voting rule.
The weakest point is the resource being studied. These anchors are communication lower bounds for distributed protocols, not NP-hardness or a central algorithmic decision result. The case is strongest if ChoCo treats worst-case communication as part of its computational complexity landscape. It supports a precise, high-multiplicity continuous analogue; it does not claim that continuization reveals an LP or makes the paper’s problem an instance of the programme’s usual centralized algorithm questions.
The strongest objection is that the mirror has to preserve much more than a society distribution. The paper’s theorems measure communication for a protocol that must answer at every prefix, while votes arrive at private sites and the center cannot see their histories. Two streams can have the same final distribution and require different communication along the way. If ChoCo’s object is a static distribution \(\mu\), these theorems do not transfer as statements about \(\mu\). To keep them, the mirror must instead use a site-indexed path of rational mass updates and preserve the online protocol model. That is a coherent continuous problem, but it is a narrower and less direct fit to a programme centered on algorithms over continuous societies.
This objection does not defeat Theorem 11’s anchor. Its proof explicitly uses non-integer voter quantities and says rounding affects the bound only by a constant factor. That does not itself formulate the mass-stream problem, but it makes a claim that mass is unnatural hard to sustain. The paper’s approval types are interchangeable for the winner-tracking task, and large polling or customer populations provide plausible high-multiplicity regimes. A mirror can also state its input precision explicitly, using the rational masses’ bit length \(L\); the theorem’s \(\log n\) bound may not carry over verbatim, but that is a parameterization issue, not a reason the question is unworthy.
Theorem 10 is a weaker anchor for a *distinctively continuous* result: its lower bound uses integer voter streams, so it establishes a bound for the rational-mass version only through the discrete instances contained within it. But the programme expressly allows hardness to transfer from discrete instances; that does not invalidate the mirror. A better formulation would ask for communication complexity over rational mass streams, parameterized by update encoding length and a fixed mass scale. That is well-posed, though the paper’s lower bound alone would not settle its full complexity landscape.
So the negative case is limited to fit and payoff: preserving these results forces one to study distributed, time-ordered mass updates, where site histories and communication constraints are central. The paper does not offer an obvious continuous-optimization problem over one society distribution, and its quoted bounds are not yet bounds in the natural encoding parameters of a rational-mass model. But those are reasons to treat this as a specialized extension, not grounds for saying no worthwhile mirror exists. Given the two anchors—and especially Theorem 11—I cannot honestly make the universal negative case.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.