Answer: —
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is an $\epsilon > 0$ such that any $\epsilon$-approximate streaming algorithm for Approval-CC or Approval-M needs $\Omega(m)$ space.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(C\), \(k\), \(\epsilon\), and a one-pass stream of binary-rational records \((A_i,w_i)\) with approval types \(A_i\subseteq C\) and total mass \(1\), what is the minimum space for a randomized algorithm that outputs, with high probability, a size-\(k\) committee \(S\) that wins in some society \(\nu\) satisfying \(\tfrac12\lVert\mu-\nu\rVert_1\le\epsilon\)? Here \(S\) wins when it maximizes its continuous Monroe score, defined by assigning each type’s mass to committee members with each member receiving exactly \(1/k\) mass.
Let \(C\) be a known candidate set, \(m=|C|\geq1\), \(1\leq k\leq m\), and \(0<\epsilon<1\) a binary rational. Approval types are arbitrary subsets of \(C\), including the empty set.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational, summing to \(1\). Here \(\tau\) is the support size, not the number \(2^m\) of possible types. The support records arrive once, in arbitrary order; \(L\) is the total input bit length.
For a society \(\rho\) and a size-\(k\) committee \(S\), define its continuous Monroe score by \(M_\rho(S)=\max_x\sum_{A\subseteq C}\sum_{c\in S\cap A}x_{A,c}\), subject to \(x_{A,c}\geq0\), \(\sum_{c\in S}x_{A,c}=\rho(A)\), and \(\sum_{A\subseteq C}x_{A,c}=1/k\) for every \(c\in S\). Type masses may be split, and assignment to unapproved candidates is allowed.
A committee wins if it maximizes this score among all size-\(k\) committees; ties count as wins. It is \(\epsilon\)-winning for \(\mu\) if it wins for some probability distribution \(\nu\) on all approval types with \(\frac12\sum_{A\subseteq C}|\mu(A)-\nu(A)|\leq\epsilon\); new types may receive mass.
The algorithm must output such a committee after one pass with probability at least \(1-\delta\), where the binary-rational confidence parameter satisfies \(0<\delta<1/2\). Space means worst-case working memory in bits; the input is read-only and the final output is write-only. Computation time is unrestricted, but any time bounds are stated in \(m,\tau,L,k,\epsilon^{-1},\delta^{-1}\).
What is the asymptotically minimum space \(s(m,\tau,L,k,\epsilon,\delta)\) for this randomized streaming problem, as characterized by upper and lower bounds?
For discrete Approval-M, changing at most an \(\epsilon\) fraction of ballots defines approximate winning; a linear space lower bound \(\Omega(m)\) is established for some fixed positive \(\epsilon\), already for \(k=1\), and an upper bound \(O(\epsilon^{-2}k^3m\log m)\) is reported. [Source](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p15.pdf)
No result settling the optimal space for the exact distributional model above was located.
The general minimum space remains unresolved. The following bounds are proved directly for the stated distributional model.
All logarithms below are base two, except $\ln$. Candidates are indexed by $C=\{1,\ldots,m\}$. Input-length estimates for the lower-bound families use characteristic vectors for approval types and binary numerator–denominator encodings for rational masses.
The upper bounds are
$$
s\leq O(L+m)
$$
and
$$
s\leq O\!\left(\tau\left[m+\log(1/\epsilon)\right]+\log L\right).
$$
For $k=1$, there are also the bounds
$$
s\leq O\!\left(m\left[\log(\tau+1)+\log(1/\epsilon)\right]+\log L\right)
$$
deterministically, and
$$
s\leq O\!\left(
m\left[1+\log(1/\epsilon)+\log\log(m/\delta)\right]+\log L
\right)
$$
randomly. The minimum of the applicable upper bounds may be taken.
The new lower bounds establish that the factor $\log(1/\epsilon)$ can be necessary:
$$ \Theta(mr)=\Theta\!\left(m\log(1/\epsilon)\right). $$
These are bounds on specified parameter families, not a matching characterization for every parameter tuple.
The [cited Approval-M paper](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p15.pdf) studies discrete ballot changes. No transfer of its upper bound to the present model is assumed here.
For $T\subseteq C$, define
$$
N(T)=\{A\subseteq C:A\cap T\neq\varnothing\},
\qquad
p_\rho(T)=\rho(N(T)).
$$
Proposition 1. For every distribution $\rho$ and every size-$k$ committee $S$,
$$
M_\rho(S)=
\min_{T\subseteq S}
\left(p_\rho(T)+\frac{k-|T|}{k}\right).
$$
Proof. Construct a finite network with a source, one vertex for each approval type, one vertex for each member of $S$, and a sink. Give the source-to-type edge capacity $\rho(A)$, each approved type-to-candidate edge capacity $2$, and each candidate-to-sink edge capacity $1/k$.
A feasible flow is an approved partial assignment satisfying row and column upper bounds. It extends to a full assignment: remaining row masses and column capacities have equal total, and all type–candidate assignments are permitted. Conversely, the approved portion of a full assignment is a feasible flow. Thus maximum flow equals the Monroe score.
A cut of capacity $1$ exists. Consequently, no minimum cut crosses a capacity-$2$ edge. If $T$ is the set of committee candidates on the sink side, every type intersecting $T$ must also be on that side. For this fixed $T$, placing exactly those types on the sink side minimizes capacity and gives
$$
p_\rho(T)+\frac{k-|T|}{k}.
$$
The finite max-flow/min-cut theorem applies because all capacities are nonnegative. Minimizing over $T$ proves the formula. $\square$
Write
$$
d_{\mathrm{TV}}(\mu,\nu)=
\frac12\sum_{A\subseteq C}|\mu(A)-\nu(A)|,
\qquad
M_\mu^*=\max_{|R|=k}M_\mu(R).
$$
Corollary 2. For every committee $S$,
$$
|M_\mu(S)-M_\nu(S)|
\leq d_{\mathrm{TV}}(\mu,\nu).
$$
In particular, every $\epsilon$-winning committee satisfies
$$
M_\mu^*-M_\mu(S)\leq 2\epsilon.
$$
Proof. Every event probability changes by at most total variation distance. Apply this to each $N(T)$ in Proposition 1; taking a minimum preserves the uniform error bound.
If $S$ wins for $\nu$ with $d_{\mathrm{TV}}(\mu,\nu)\leq\epsilon$, then, for every $R$,
$$
M_\mu(R)
\leq M_\nu(R)+\epsilon
\leq M_\nu(S)+\epsilon
\leq M_\mu(S)+2\epsilon.
$$
Taking the maximum over $R$ proves the second assertion. $\square$
Only this necessary condition is used in the lower bounds.
Store the input and enumerate all committees and the subsets appearing in Proposition 1.
The product of all input mass denominators has bit length $O(L)$. Using this common denominator and then incorporating the factor $k$, exact score calculations and comparisons require $O(L+\log k)$ arithmetic bits. They can be performed one type at a time without storing a separate converted numerator for every type.
Committee enumeration uses $O(m)$ bits. Therefore exact winner determination uses
$$
O(L+m)
$$
working bits. Its output is valid for every $\epsilon$ and $\delta$.
Lemma 3. A binary-encoded rational $w\in[0,1]$ can be read once and rounded to an integer $q$ satisfying
$$
0\leq \frac q{2^b}\leq w,
\qquad
w-\frac q{2^b}\leq \frac2{2^b},
$$
using $O(b+\log L)$ bits.
Proof. Write $w=p/d$. Retain the leading $h=b+4$ bits of each integer and count their bit lengths. Truncating the numerator downward and the denominator upward gives integers, represented by a leading significand and an exponent, satisfying
$$
p_-\leq p,\qquad d_+\geq d.
$$
If an integer has more than $h$ bits, its relative approximation error is at most $2^{1-h}$; shorter integers are retained exactly. Since $p/d\leq1$,
$$
0\leq \frac pd-\frac{p_-}{d_+}
\leq 2^{2-h}.
$$
Rounding $2^bp_-/d_+$ downward contributes less than $2^{-b}$ additional error, proving the stated bound.
Significands use $O(b)$ bits and bit-length counters use $O(\log L)$ bits. If the exponent difference makes the ratio smaller than $2^{-b}$, return zero. Otherwise the shifts needed for the calculation have length $O(b)$. Thus no full-precision input integer must be retained. $\square$
A conservative dyadic estimate of $\epsilon$ within a constant factor can be obtained by the same leading-bit method. Its full encoding need not be stored.
Choose a power of two $D_0\geq32/\epsilon$. For record $i\geq1$, use
$$
D_i=D_0\,2^{2\lceil\log(i+1)\rceil}.
$$
These denominators are nondecreasing powers of two. Apply Lemma 3 to obtain a rounded mass
$$
r_i=\frac{q_i}{D_i}\leq w_i,
\qquad
w_i-r_i\leq \frac2{D_i}.
$$
Because $D_i\geq D_0(i+1)^2$,
$$
R:=1-\sum_{i=1}^{\tau}r_i
\leq \frac2{D_0}\sum_{i=1}^{\infty}\frac1{(i+1)^2}
\leq \frac2{D_0}
\leq \frac{\epsilon}{16}.
$$
The series bound follows by comparing its terms with the integral of $x^{-2}$ from $1$ to infinity.
Define $\nu$ by retaining every rounded mass and placing the residual $R$ on the empty approval type. Downward rounding gives
$$
d_{\mathrm{TV}}(\mu,\nu)
=\sum_{A\neq\varnothing}\bigl(\mu(A)-r_A\bigr)
\leq R.
$$
Store each type and its rounded mass. Whenever $D_i$ increases, rescale earlier stored integers to the new denominator. The final denominator has bit length
$$
b_\tau=O\!\left(\log(\tau+1)+\log(1/\epsilon)\right).
$$
After the pass, compute an exact winner for $\nu$ using Proposition 1. The distribution $\nu$ is its required witness.
The space is
$$
O\!\left(
\tau\left[m+\log(\tau+1)+\log(1/\epsilon)\right]+\log L
\right).
$$
Since distinct support types satisfy $\tau\leq2^m$, this is
$$
O\!\left(\tau\left[m+\log(1/\epsilon)\right]+\log L\right).
$$
When $k=1$, the score of candidate $c$ is its approval probability
$$
p_\rho(c)=\rho(\{A:c\in A\}).
$$
Use the preceding rounding scheme, but retain only the $m$ approval sums. All counters use the current common denominator and are rescaled when it increases. An arriving type can be held in an $m$-bit buffer while its mass is parsed.
The final counters are exactly the approval probabilities for the rounded witness distribution $\nu$; its residual empty mass contributes nothing. Return a candidate maximizing its counter.
Consequently, the deterministic space bound is
$$
O\!\left(
m\left[\log(\tau+1)+\log(1/\epsilon)\right]+\log L
\right).
$$
The algorithm does not need $\tau$ in advance.
The following bound can be smaller when $\tau$ is large.
Lemma 4. If
$$
g=\max_d p_\mu(d)-p_\mu(c),
$$
then $c$ wins for a distribution at total variation distance at most $g$ from $\mu$.
Proof. Since $g\leq1-p_\mu(c)$, take mass $g$ from types not approving $c$ and move it to $\{c\}$. Candidate $c$ gains approval mass $g$, while every other candidate’s approval mass weakly decreases. Thus $c$ becomes a winner. The total variation change is at most $g$. $\square$
Choose a power of two
$$
D\geq16\,2^m/\epsilon
$$
and round every input mass downward using Lemma 3 with this denominator. Put the residual mass on the empty type. The resulting distribution $\nu$ satisfies
$$
d_{\mathrm{TV}}(\mu,\nu)\leq \frac{2\tau}{D}\leq\frac{\epsilon}{8}.
$$
Take
$$
N\geq8\epsilon^{-2}\ln(2m/\delta)
$$
with $N=O(\epsilon^{-2}\log(m/\delta))$. Conservative dyadic estimates of the parameters suffice to choose such an integer.
The approval counts of $N$ independent samples from $\nu$ can be generated during the pass. Initially let $n=N$ and $B=D$. On a record of rounded integer mass $q_A$, draw
$$
J_A\sim\operatorname{Binomial}(n,q_A/B),
$$
add $J_A$ to the counters of all candidates in $A$, and update
$$
n\leftarrow n-J_A,\qquad B\leftarrow B-q_A.
$$
Remaining samples at the end belong to the residual empty category.
This is exactly conditional multinomial sampling: conditional on avoiding earlier categories, each remaining independent sample has current-category probability $q_A/B$. Cases $q_A=0$ and $q_A=B$ are deterministic. Exact rational Bernoulli draws, and hence binomial draws, can be implemented by rejection sampling using $O(\log D+\log N)$ bits.
Let $\widehat p(c)$ be a sampled approval frequency. For each fixed candidate, the $N$ indicators are independent Bernoulli variables. Hoeffding’s inequality gives
$$
\Pr\!\left(
|\widehat p(c)-p_\nu(c)|>\epsilon/4
\right)
\leq 2e^{-N\epsilon^2/8}.
$$
A union bound over the $m$ candidates shows that, with probability at least $1-\delta$,
$$
|\widehat p(c)-p_\mu(c)|\leq3\epsilon/8
\quad\text{for every }c.
$$
If $c$ maximizes $\widehat p$ and $d$ maximizes $p_\mu$, then
$$
p_\mu(d)-p_\mu(c)\leq3\epsilon/4.
$$
Lemma 4 makes $c$ $\epsilon$-winning.
There are $m$ counters bounded by $N$, one type buffer, and $O(\log D+\log L)$ parsing and sampling bits. Therefore space is
$$
O\!\left(
m\left[1+\log(1/\epsilon)+\log\log(m/\delta)\right]+\log L
\right).
$$
Rejection sampling has bounded workspace and finite expected running time. The overall expected running time is polynomial in the parameters allowed in the question.
We use an elementary one-way communication bound.
Lemma 5. Suppose Alice holds a uniformly random string
$$
X=(X_1,\ldots,X_q)\in\{0,1\}^q
$$
and sends a state $Z$ of at most $s$ bits. Bob, given an index $j$, the prefix $X_1,\ldots,X_{j-1}$, and public randomness, estimates $X_j$ with error at most $\delta$ for every input and index. Then
$$
s\geq q\bigl(1-h_2(\delta)\bigr)-1,
$$
where
$$
h_2(u)=-u\log u-(1-u)\log(1-u).
$$
Proof. Let $R$ denote public randomness, independent of $X$. For each $j$, let $E_j$ indicate estimation error. Given $Z,R,X_1,\ldots,X_{j-1}$, the bit $X_j$ is determined by the estimate and $E_j$. Hence
$$
H(X_j\mid Z,R,X_1,\ldots,X_{j-1})
\leq H(E_j)
\leq h_2(\delta).
$$
The last inequality uses $\Pr(E_j=1)\leq\delta<1/2$.
By the entropy chain rule,
$$
H(X\mid Z,R)\leq qh_2(\delta).
$$
Since $H(X\mid R)=q$,
$$
I(X;Z\mid R)\geq q(1-h_2(\delta)).
$$
A variable-length state of at most $s$ bits has fewer than $2^{s+1}$ possible values, so $H(Z\mid R)\leq s+1$. This proves the result. $\square$
For a streaming reduction, Alice processes an initial segment and sends the complete retained state. Bob processes the remaining records and decodes the output. Independent public random tapes for the two segments reproduce the algorithm’s randomness.
Fix an integer $r\geq1$. Put
$$
b=\lceil\log r\rceil,
\qquad
n=m-b-2,
$$
and assume $n\geq1$.
Use signal candidates $c_1,\ldots,c_n$, candidates $d,z$, and $b$ marker candidates. Assign each row $j\in\{1,\ldots,r\}$ a distinct marker subset $G_j$.
Alice holds $nr$ bits $x_{j,\ell}$. She supplies $r$ records
$$
A_j=\{z\}\cup G_j\cup\{c_\ell:x_{j,\ell}=1\},
\qquad
w_j=4^{-(j+1)}.
$$
Their total mass is
$$
W=\sum_{j=1}^r w_j<\frac1{12}.
$$
The types are distinct because their marker subsets are distinct.
Bob asks for bit $x_{t,i}$ and knows all earlier bits in row-major order. In particular, he knows
$$
P=\sum_{j<t}w_jx_{j,i}.
$$
Set
$$
D=P+\frac{w_t}{2},
\qquad
u=\frac{1-W-D}{2},
\qquad
v=\frac{1-W+D}{2}.
$$
Bob supplies two records:
$$
\{c_i\}\text{ with mass }u,
\qquad
\{d\}\text{ with mass }v.
$$
Because $0<D<W$, both masses are positive. All masses are dyadic and sum to $1$. These two types are distinct from Alice’s types because every Alice type contains $z$. Thus
$$
\tau=r+2.
$$
Let
$$
T=\sum_{j>t}w_jx_{j,i}.
$$
The geometric weights satisfy
$$
0\leq T<\frac{w_t}{3}.
$$
The approval-score difference between $c_i$ and $d$ is
$$
p_\mu(c_i)-p_\mu(d)
=P+w_tx_{t,i}+T+u-v
=w_tx_{t,i}+T-\frac{w_t}{2}.
$$
Therefore:
Every other candidate has approval probability at most $W<1/12$. Meanwhile,
$$
u\geq\frac{1-2W}{2}>\frac5{12},
\qquad
v>\frac5{12}.
$$
Thus every candidate other than the better of $c_i,d$ has score deficit at least $w_r/6$.
If
$$
\epsilon<\frac{w_r}{12},
$$
Corollary 2 forces every successful output to be $c_i$ exactly when $x_{t,i}=1$. Applying Lemma 5 yields
$$
s\geq
\left(m-\lceil\log r\rceil-2\right)
r\bigl(1-h_2(\delta)\bigr)-1.
$$
Choose
$$
\epsilon_r=\frac{w_r}{32}=2^{-2r-7}.
$$
For $m\geq16$ and $1\leq r\leq m$,
$$
m-\lceil\log r\rceil-2\geq m/2.
$$
For fixed $\delta<1/2$, the lower bound is consequently $\Omega(mr)$.
The type vectors contribute $\Theta(mr)$ input bits. The dyadic masses contribute $O(r^2)$ bits, and Bob’s two masses have $O(r)$-bit encodings. Since $r\leq m$,
$$
L=\Theta(mr).
$$
Exact storage gives the matching $O(mr)$ upper bound. Hence, on these explicit families,
$$
s=\Theta(mr)
=\Theta\!\left(m\log(1/\epsilon_r)\right).
$$
This also proves an $\Omega(m\tau)$ lower bound on families where the accuracy is exponentially small in the support size.
Let
$$
\alpha=2^{-\lceil\log k\rceil},
\qquad
\frac1{2k}\leq\alpha\leq\frac1k.
$$
Introduce $k-1$ anchor candidates $a_1,\ldots,a_{k-1}$. Give each singleton anchor type mass $\alpha$, and give the all-anchor type mass $1-k\alpha$ when this is positive.
The total anchor mass is $1-\alpha$. The anchors can all receive approved mass $1/k$: after assigning the singleton masses, the remaining required mass is
$$
(k-1)\left(\frac1k-\alpha\right),
$$
which is at most $1-k\alpha$, since the difference is $1/k-\alpha\geq0$.
Multiply every signal mass in the preceding construction by $\alpha$. Its total mass is then $\alpha$. The full distribution still sums to $1$.
For a committee containing all anchors and one signal candidate $c$, its score is exactly
$$
\frac{k-1}{k}+\alpha p(c),
$$
where $p(c)$ is its approval probability in the normalized signal distribution. Indeed, anchor capacities can all be filled, and the signal contribution is at most $\alpha\leq1/k$.
For $k\geq2$, a committee omitting an anchor has score at most
$$
\frac{k-2}{k}+\alpha
\leq\frac{k-1}{k}.
$$
The best committee with all anchors scores more than
$$
\frac{k-1}{k}+\frac{5\alpha}{12}.
$$
Consequently, under
$$
\epsilon<\frac{\alpha w_r}{12},
$$
every successful committee contains all anchors and chooses the correct one of $c_i,d$.
There are now
$$
n=m-k-\lceil\log r\rceil-1
$$
variable signal candidates. When $n\geq1$, Lemma 5 proves
$$
s\geq
\left(m-k-\lceil\log r\rceil-1\right)
r\bigl(1-h_2(\delta)\bigr)-1.
$$
The support size is at most $k+r+2$. In particular, with
$$
\epsilon=\frac{\alpha w_r}{32},
$$
the construction encodes accuracy precision satisfying
$$
\log(1/\epsilon)=2r+7+\lceil\log k\rceil.
$$
This establishes a stronger accuracy-dependent lower bound for general $k$, but does not match a general upper bound.
The preceding tight family assumes $r\leq m$. A second construction removes this restriction for $k=1$.
Let $m\geq3$, put $n=m-2$, and use candidates
$$
c_1,\ldots,c_n,z,d.
$$
Set
$$
\beta=2^{-\lceil\log n\rceil-6},
\qquad
\lambda_j=\beta4^{-j},
\qquad
\eta=\beta4^{-(r+1)},
\qquad
W=\frac1{16}.
$$
Alice holds $nr$ bits $x_{i,j}$. For each $i$, she supplies type $\{c_i,z\}$ with mass
$$
a_i=\beta+\eta+\sum_{j=1}^r\lambda_jx_{i,j}.
$$
She also supplies $\{z\}$ with mass
$$
W-\sum_{i=1}^n a_i.
$$
All these masses are positive. Indeed,
$$
a_i<\frac32\beta,
\qquad
n\beta\leq\frac1{64},
$$
so
$$
\sum_i a_i<\frac3{128}<W.
$$
Alice’s segment always has total mass $W$, and $z$ has approval probability $W$.
Bob asks for bit $x_{i,t}$ and knows earlier bits in candidate-major order. He knows
$$
P=\beta+\eta+\sum_{j<t}\lambda_jx_{i,j}.
$$
Define
$$
D=P+\frac{\lambda_t}{2},
\qquad
u=\frac{1-W-D}{2},
\qquad
v=\frac{1-W+D}{2}.
$$
Bob supplies $\{c_i\}$ with mass $u$ and $\{d\}$ with mass $v$.
Since $0<D<W$, both Bob masses exceed $7/16$. Every unqueried candidate has approval probability at most $W$. The queried score difference is
$$
p_\mu(c_i)-p_\mu(d)
=\lambda_tx_{i,t}
+\sum_{j>t}\lambda_jx_{i,j}
-\frac{\lambda_t}{2}.
$$
The same geometric-tail calculation gives the correct sign with magnitude at least $\lambda_r/6$. Thus, if
$$
\epsilon<\frac{\lambda_r}{12},
$$
every successful output identifies $x_{i,t}$. Lemma 5 proves
$$
s\geq(m-2)r\bigl(1-h_2(\delta)\bigr)-1.
$$
The support types are distinct and number exactly
$$
\tau=n+3=m+1.
$$
The constant $\eta$ ensures that each $a_i$, expressed over the denominator of $\eta$, has odd numerator: its numerator is congruent to $1$ modulo $4$. Therefore each such mass has binary encoding length $\Theta(r+\log n)$ even after reduction.
With characteristic-vector type encodings,
$$
L=\Theta(m^2+mr).
$$
Choose
$$
\epsilon=\frac{\lambda_r}{32}
=2^{-\lceil\log n\rceil-2r-11}.
$$
For $r\geq m$ and fixed $\delta<1/2$,
$$
L=\Theta(mr),
\qquad
\log(1/\epsilon)=\Theta(r).
$$
The lower bound and exact-storage upper bound therefore match:
$$
s=\Theta(mr)
=\Theta\!\left(m\log(1/\epsilon)\right).
$$
Thus the accuracy-dependent lower bound persists for arbitrarily high rational precision, without increasing support beyond $m+1$.
For completeness, a simpler construction gives stronger constant-accuracy thresholds.
For $k=1$, use candidates $c_1,\ldots,c_{m-1},d$. Alice supplies
$$
A(x)=\{d\}\cup\{c_j:x_j=1\}
$$
with mass $5/8$. Bob, querying $i$, supplies $\{c_i\}$ with mass $3/8$.
If $x_i=1$, candidate $c_i$ scores $1$ and all others score at most $5/8$. If $x_i=0$, candidate $c_i$ scores $3/8$ while $d$ scores $5/8$. For
$$
\epsilon<1/8,
$$
Corollary 2 forces a successful output to equal $c_i$ exactly when $x_i=1$.
Lemma 5, which remains applicable when Bob does not need his prefix, gives
$$
s\geq(m-1)(1-h_2(\delta))-1.
$$
Here $\tau=2$ and $L=\Theta(m)$. For fixed $\epsilon<1/8$ and fixed $\delta<1/2$, exact storage proves the matching $\Theta(m)$ bound.
Adding the anchors of Section 5.3 and scaling these two signal masses by $\alpha$ gives
$$
s\geq(m-k)(1-h_2(\delta))-1
$$
for
$$
\epsilon<1/(16k),
$$
using at most $k+2$ support types. The two relevant signal-score deficits are at least $\alpha/4$, and
$$
2\epsilon<\frac1{8k}\leq\frac{\alpha}{4}.
$$
Committees omitting anchors are excluded by the anchor-score bound already proved.
If $k=m$, the unique committee can be output with $O(\log m)$ working bits.
There is also an easy accuracy regime.
Proposition 6. Every predetermined size-$k$ committee is valid for every society when
$$
\epsilon\geq\frac{k}{k+1}.
$$
For $m>k$, this universal radius is sharp.
Proof of the upper bound. For a fixed committee $S$, let $\sigma_S$ put mass $1/k$ on each singleton $\{c\}$ with $c\in S$. Set
$$
t=\frac{k}{k+1},
\qquad
\nu=(1-t)\mu+t\sigma_S.
$$
Then $d_{\mathrm{TV}}(\mu,\nu)\leq t$. Assign the singleton component to its corresponding members of $S$ and distribute the remaining component equally. This gives $M_\nu(S)\geq t$.
Any different committee $R$ receives approved mass at most
$$
1-t+\frac{t|R\cap S|}{k}
\leq1-t+\frac{t(k-1)}{k}
=t.
$$
Hence $S$ wins. $\square$
Proof of sharpness. Choose $b\notin S$ and let $\mu$ be concentrated on $\{b\}$. Suppose $d_{\mathrm{TV}}(\mu,\nu)=t<k/(k+1)$. Then
$$
\nu(\{b\})\geq1-t,
\qquad
M_\nu(S)\leq t.
$$
In an optimal approved partial assignment to $S$, some member $c$ receives approved mass
$$
q_c\leq M_\nu(S)/k\leq t/k.
$$
Replace $c$ by $b$, retain all other approved assignments, and assign $\{b\}$ mass to $b$ up to its quota. This is feasible because the retained approved assignment uses no $\{b\}$ mass. The resulting score is at least
$$
M_\nu(S)-q_c+\min\{\nu(\{b\}),1/k\}.
$$
Both $1-t$ and $1/k$ are strictly greater than $t/k$. Thus the replacement committee strictly beats $S$. No distance smaller than $k/(k+1)$ suffices. $\square$
The upper-bound algorithm in this regime ignores the society and outputs a predetermined committee using $O(\log m)$ working bits.
The proved bounds now settle several substantial families, including families requiring
$$
\Theta\!\left(m\log(1/\epsilon)\right)
$$
space. They still do not determine the minimum space for arbitrary $(m,\tau,L,k,\epsilon,\delta)$.
For general $k$, score sampling alone leaves a genuine missing implication. Proposition 1 and Hoeffding’s inequality provide simultaneous score approximation from samples, but an approximately optimal score has not here been converted into the required nearby-distribution winner guarantee.
In particular, the point-mass society used in Proposition 6 has
$$
M_\mu^*-M_\mu(S)=1/k
$$
for a committee excluding $b$, while its winner distance is $k/(k+1)$. Any universal linear conversion must therefore have factor at least
$$
\frac{k^2}{k+1}.
$$
A simple proposed repair—mixing toward equal singleton mass on $S$—also fails to close arbitrarily small score gaps. Here is an exact example.
Let $k=2$, $C=\{a,b,c\}$, $S=\{b,c\}$, and $0<g<1/12$. Give masses
$$
\mu(\varnothing)=\frac1{10},\qquad
\mu(\{a\})=\frac1{10},\qquad
\mu(\{b\})=\frac3{10}+g,\qquad
\mu(\{a,c\})=\frac12-g.
$$
Proposition 1 gives
$$
M_\mu(S)=\frac45,\qquad
M_\mu(\{a,b\})=\frac45+g,\qquad
M_\mu(\{a,c\})=\frac35-g.
$$
Moving mass $g$ from the empty type to $\{c\}$ makes $S$ a winner, so its winner distance is at most $g$.
Nevertheless, for
$$
\nu_t=(1-t)\mu+t\sigma_S,
$$
Proposition 1 gives
$$
M_{\nu_t}(S)=\frac45+\frac t5.
$$
For $R=\{a,b\}$, its four cut values are
$$
1,\qquad
\frac12+(1-t)\left(\frac35-g\right),\qquad
(1-t)\left(\frac45+g\right)+t,\qquad
\frac9{10}-\frac{2t}{5}.
$$
Every one is strictly greater than $4/5+t/5$ when $0\leq t<1/6$. For the second value, the difference is
$$
\frac3{10}-g-t\left(\frac45-g\right)
>
\frac3{10}-\frac1{12}-\frac{2}{15}
=\frac1{12}.
$$
The other differences are respectively
$$
\frac{1-t}{5},\qquad
(1-t)g,\qquad
\frac1{10}-\frac{3t}{5}.
$$
Thus this particular mixing method needs a constant mixing amount even as $g$ tends to zero. This does not refute a better perturbation construction; it explains why that method cannot supply the missing general upper bound.
⟨structured verdict parsed — rendered above⟩
Overall assessment: correct and substantial partial progress, but the requested general minimum-space characterization is not established. The score formula, streaming upper bounds, communication lower bounds, and perturbation examples withstand verification. I found no false central step.
The main unresolved issue is acknowledged by the prover: matching bounds are obtained only on specified parameter families. There is also one minor precision-choice omission in the upper-bound presentation.
The output addresses the correct distributional model:
The distinction from the cited discrete model is accurate. That paper defines approximate winning through changing ballots; the output does not assume its upper bound transfers to the distributional setting. See [Definition 1 in the cited paper](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p15.pdf).
Nevertheless, the output explicitly leaves the minimum space for arbitrary parameter tuples unresolved. Its bounds should therefore be accepted as a partial characterization, not as a complete answer to the requested minimum-space question.
The network argument is correct.
The approved part of any feasible full assignment is a feasible flow. Conversely, the unused row masses and column capacities of a feasible flow have equal total. Because unapproved assignments are permitted, extending that flow to a full assignment is valid.
The cut analysis is also correct:
This yields precisely the claimed formula:
$$
M_\rho(S)=\min_{T\subseteq S}
\left(p_\rho(T)+\frac{k-|T|}{k}\right).
$$
The network is finite and its capacities are nonnegative, so the stated max-flow/min-cut application is valid. Zero-mass types and the empty type cause no problem.
Both conclusions follow correctly.
Each event probability changes by at most total variation distance, and taking a minimum preserves a common additive error bound. The subsequent comparison with a winner under $\nu$ correctly gives
$$
M_\mu^*-M_\mu(S)\leq 2\epsilon.
$$
The lower bounds use this only as a necessary condition. They do not incorrectly treat it as sufficient.
The bound
$$
O(L+m)
$$
is justified.
The product of the mass denominators has bit length $O(L)$. Incorporating $k$ adds $O(\log k)$ bits. Exact event sums, score comparisons, and committee enumeration fit the claimed workspace.
The algorithm may revisit its stored copy after the pass; this does not violate the one-pass restriction on the original stream.
The parsing argument is sound.
With $h=b+4$, the combined numerator and denominator truncation error is bounded by
$$
2^{2-h}=\frac14\,2^{-b}.
$$
The final downward rounding contributes less than $2^{-b}$. Their sum is smaller than the stated allowance $2\,2^{-b}$.
Leading significands and bit-length counters fit in $O(b+\log L)$ bits. The zero numerator and integers shorter than $h$ bits are compatible with the described procedure.
The accumulated rounding loss is bounded correctly:
$$
R\leq
\frac{2}{D_0}\sum_{i=1}^{\infty}\frac{1}{(i+1)^2}
\leq \frac{2}{D_0}
\leq \frac{\epsilon}{16}.
$$
Moving that loss to the empty type gives a probability distribution. If the empty type already occurs, its retained mass and the residual are combined. The claimed total variation expression correctly excludes that type.
Returning an exact winner of this rounded distribution directly supplies the required witness. No score-to-winner conversion is needed.
The simplification using
$$
\tau\leq 2^m
$$
is legitimate because $\tau$ counts distinct support types.
Minor issue: The instruction “Choose a power of two $D_0\geq32/\epsilon$” supplies only a lower bound. The subsequent denominator-length bound also requires $D_0$ to be chosen within a constant factor of that threshold. This is an expositional omission.
Minimum clarification: Specify the smallest admissible power of two, or explicitly require a constant-factor choice.
The approval counters are exactly the approval probabilities of the rounded witness distribution. Its residual empty mass contributes nothing.
The type buffer, common denominator, counters, and parsing workspace fit
$$
O\!\left(
m\left[\log(\tau+1)+\log(1/\epsilon)\right]+\log L
\right).
$$
The changing denominator and record counter allow the algorithm to operate without knowing $\tau$ beforehand.
The perturbation argument is valid.
There is enough mass outside the event “approves $c$” because
$$
g\leq 1-p_\mu(c).
$$
Moving mass $g$ from those types to $\{c\}$ increases $c$’s approval probability by $g$ and cannot increase another candidate’s approval probability. Thus $c$ becomes a winner within the claimed distance.
The rounding error satisfies
$$
d_{\mathrm{TV}}(\mu,\nu)
\leq\frac{2\tau}{D}
\leq\frac{\epsilon}{8}.
$$
The sequential binomial procedure has the stated conditional multinomial distribution. Its denominator $B$ is the remaining rounded mass, including the residual category. The deterministic boundary cases are consistent with that interpretation.
Exact rational sampling with bounded workspace and finite expected running time is compatible with the stated unrestricted-time model.
The Hoeffding calculation is correct:
$$
2e^{-N\epsilon^2/8}\leq\frac{\delta}{m}.
$$
After the union bound and rounding error, every approval estimate differs from its original probability by at most $3\epsilon/8$. Maximizing the estimates therefore gives deficit at most $3\epsilon/4$, which is sufficient through Lemma 4.
The counter and auxiliary-memory accounting yields the stated bound. The polynomial expected-time claim is consistent with the described sampling procedure and applies to this algorithm.
Minor issue: As with $D_0$, the instruction $D\geq16\,2^m/\epsilon$ needs an accompanying upper-size choice to justify the asserted workspace.
Minimum clarification: Specify the smallest admissible power of two, or another constant-factor choice. This is the same precision-choice issue as in the deterministic construction.
Lemma 5 is correct.
The estimator is determined by the retained state, public randomness, and supplied prefix. Its estimate together with the error bit determines the queried bit. The conditional entropy bound, entropy chain rule, and mutual-information comparison are valid.
The assumption $\delta<1/2$ justifies using the monotonicity of binary entropy on the relevant interval. The variable-length-state allowance correctly yields the additive subtraction of $1$.
Sending the complete retained streaming state is a valid one-way reduction. Independent public random tapes for the two segments reproduce fresh algorithmic randomness; any retained random information belongs to the transmitted state.
The distribution and decoding conditions are correct.
Distinct marker subsets make Alice’s types distinct, and $z$ separates them from Bob’s types. The mass sum satisfies
$$
W=\frac{1}{12}\left(1-4^{-r}\right)<\frac{1}{12}.
$$
The inequalities $0<D<W$ ensure positivity of Bob’s masses, which complete the total mass to $1$.
The geometric tail satisfies
$$
T<\frac{w_t}{3}.
$$
Consequently, the score difference has the stated sign, with deficit greater than $w_t/6$ in the zero case and at least $w_t/2$ in the one case.
All other candidates remain far below the two queried contenders. Under
$$
\epsilon<\frac{w_r}{12},
$$
their deficits and the queried loser’s deficit exceed $2\epsilon$. Corollary 2 therefore forces the claimed decoding.
The information lower bound follows with the stated number of encoded bits.
The chosen accuracy is correct:
$$
\frac{w_r}{32}=2^{-2r-7}.
$$
Under the detailed restriction $m\geq16$ and $r\leq m$, the number of signal candidates is at least $m/2$. With fixed $\delta<1/2$, this gives $\Omega(mr)$.
The characteristic vectors contribute $\Theta(mr)$ bits, and the mass encodings contribute $O(r^2)$. Since $r\leq m$, the total is indeed $\Theta(mr)$. Exact storage supplies the matching upper bound.
This establishes the claimed tight family, not a bound for arbitrary support size and accuracy.
The anchor construction is valid.
The singleton masses and all-anchor mass total $1-\alpha$. The inequality
$$
(k-1)\left(\frac1k-\alpha\right)\leq 1-k\alpha
$$
correctly establishes that all anchor quotas can be filled with approved mass.
A committee containing every anchor and one signal candidate has exactly the stated score. A committee omitting an anchor satisfies the stated upper bound because its present anchors contribute at most $(k-2)/k$, while all signal types together contribute at most $\alpha$.
The condition
$$
\epsilon<\frac{\alpha w_r}{12}
$$
excludes both an incorrect signal choice and an omitted anchor. The candidate count, support bound, and accuracy-precision identity are consistent.
Section 6 is correct.
The inequalities
$$
a_i<\frac32\beta,\qquad n\beta\leq\frac1{64}
$$
ensure that the filler mass is positive. Alice’s total mass is always $W$, independently of her encoded bits.
Bob’s threshold uses only the supplied prefix. The geometric-tail argument gives the required score separation. Other candidates have approval probability at most $W$ and cannot provide unintended successful outputs.
The support count is exactly $m+1$.
The numerator congruence modulo $4$ is also correct. It prevents cancellation of the power-of-two denominator in each $a_i$, justifying the claimed mass-encoding lengths.
Thus
$$
L=\Theta(m^2+mr).
$$
For $r\geq m$, the claimed tight $\Theta(mr)$ family and its equivalent accuracy-dependent expression follow.
The two records are always distinct because Alice’s type contains $d$ and Bob’s does not.
When the queried bit is one, the queried candidate is uniquely best. When it is zero, its deficit is $1/4$. Therefore $\epsilon<1/8$ gives exactly the required decoding distinction, even if other candidates tie with $d$.
The anchored extension has the claimed scaled deficits and valid accuracy threshold.
The universal perturbation bound and sharpness proof are correct.
For the upper bound, the proposed assignment to $S$ is feasible. Every different committee satisfies the stated upper score bound, so ties correctly suffice.
For sharpness, replacing a least-contributing committee member preserves the other approved assignments. Those assignments consume no mass of $\{b\}$. Both inequalities needed for a strict improvement hold:
$$
1-t>\frac{t}{k},
\qquad
\frac1k>\frac{t}{k}.
$$
Thus the universal radius is sharp for $m>k$. The unique-committee case $k=m$ is handled separately.
The point-mass comparison is correct:
$$
M_\mu^*-M_\mu(S)=\frac1k,
$$
while the winner distance is $k/(k+1)$. The stated necessary factor for a universal linear conversion follows.
The three-candidate example also checks out. Its initial committee scores, the successful move from the empty type to $\{c\}$, and the four cut values under singleton mixing are all correct. Each listed difference is strictly positive for $0\leq t<1/6$.
This example establishes the failure of that particular mixing procedure. The prover correctly avoids claiming that it disproves other perturbation constructions.
Major incompleteness relative to the task: The output does not determine the asymptotically minimum space for general parameter tuples. The dependence on support size, committee size, accuracy, input length, and confidence is not matched outside the specified families.
This is a missing result, not an error in the proved constructions. A further round would need matching bounds with explicit parameter ranges, or an explicitly narrower target. Resolving only the denominator-choice wording would leave this substantive limitation unchanged.
⟨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.