| paper | d4-conf-ijcai-2020-0124 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 proves high-probability identifiability under a random finite-worker model, but gives neither an algorithm nor a complexity claim. The unnumbered gradient-update discussion and empirical aggregation results do not supply a named computational result, so bit (a) fails even though the proposed support-compressed recovery problem is statable.
fails bit a — no named computational result to mirror
The proposed mirror addresses only Theorem 1's exact-constraint recovery; it leaves the relaxation, performance regularization, and experimental aggregation results without a continuous computational counterpart.
The paper has no named theorem or proposition classifying a problem as polynomial-time, NP-hard, or similar. Its only numbered anchor is Theorem 1, proved in this paper: for binary-choice questions, if worker \(i\) is correct on exactly \(p_iM\) questions chosen independently and uniformly at random, \(p_1\ne 1/2\), and \(N>M\ln M\), then the performance constraints uniquely determine the ground truths with high probability. This is an identifiability result, not a complexity bound. It is the strongest named result on which I can build a positive case.
The most plausible regime is a large crowdsourcing workforce answering a fixed batch of \(M\) questions. Workers who share the same complete response pattern and the same known qualification accuracy are indistinguishable for the paper’s exact constraint; let that pair be a type. If many workers fall into a moderate number \(\tau\) of such types, their fractions \(\mu_t\) describe the workforce and can replace a long list of repeated workers. This is plausible for recurring worker strategies and qualification scores, though it is not guaranteed: a response pattern spans the whole batch, so the number of types can grow quickly.
A precise mirror is Mass-Compressed Performance-Constraint Recovery. Its input is \(M\), a finite type set \(T\) with positive rational masses \(\mu_t\) summing to one, each type’s binary response vector \(r_t\in\{0,1\}^M\), and its known accuracy \(p_t\in\mathbb Q\), with \(Mp_t\) integral. The unknown decision is the binary ground-truth vector \(g\in\{0,1\}^M\). Define
\[ \mathcal G=\left\{g\in\{0,1\}^M: \frac{1}{M}\sum_{j=1}^M \mathbf 1[r_{tj}=g_j]=p_t \ \text{for every }t\in T\right\}. \]
The task is to return \(g\) when \(\mathcal G\) is a singleton, and otherwise report whether \(\mathcal G\) is empty or give two distinct feasible truths. For the rank-full recovery regime, promise that \(\mathcal G\ne\varnothing\) and that the matrix \(A\), with entries \(A_{tj}=2r_{tj}-1\), has column rank \(M\).
I expect this promised version to be tractable (Class A). Set \(y_j=2g_j-1\). The constraints become \(Ay=b\), where \(b_t=M(2p_t-1)\). Under the rank and consistency promises, rational Gaussian elimination recovers the unique \(y\), which can then be checked to lie in \(\{-1,1\}^M\). This takes time polynomial in \(M,\tau\), and the input bit length. Theorem 1 does not state this algorithmic bound; it supplies the random regime in which its proof’s full-rank mechanism yields unique recovery. Whether broader, unrestricted instances are tractable is a separate question, not answered by that theorem.
The mirror should be recognizable to the authors because it keeps their exact performance-constraint equation and their goal of recovering the discrete truth labels. It compresses repeated, identical worker constraints into one type, with mass recording prevalence. It covers Theorem 1’s exact-constraint recovery result only; it does not claim to mirror the performance-regularization experiments or the underlying statistical aggregation models.
The soft spot is that, under the exact per-type constraints, mass affects the population description but not feasibility: only the support types’ constraints matter. Also, the theorem’s independent random responses may produce nearly as many distinct types as workers, so the useful \(N\gg\tau\) regime is not established by the paper. This is a credible high-multiplicity recovery question, but the paper does not show that its theorem’s guarantee survives when many workers collapse into a small support. A natural next question is whether a mass-weighted approximate version, using \(\sum_t\mu_t d(\frac1M\sum_j\mathbf1[r_{tj}=g_j],p_t)\), admits better algorithms when qualification accuracies are noisy.
The proponent’s only anchor, Theorem 1, is an identifiability result, not a computational result: it gives a high probability guarantee for a finite random workforce, but no algorithm or complexity bound. The proposed mirror turns the theorem’s full rank condition into a promised recovery problem. That is a reasonable problem to formulate, but it does not make Theorem 1 a computational result about a continuous population.
The mirror’s exact constraints also reveal the deeper issue. To preserve the paper’s per-worker accuracy condition, a type must include the worker’s full response vector across the \(M\) questions and their accuracy \(p_i\). Once workers are grouped this way, feasibility depends on which types occur, not on their masses: repeated copies add no new constraint. The theorem’s \(N\) counts independently sampled response rows; replacing those workers with a distribution over types does not preserve that sampling guarantee unless a finite sampling process is put back in. And full-rank recovery requires at least \(M\) distinct types. With fewer, more mass cannot supply the missing independent constraints; with enough, recovery on the promised instances is a rank check on the support matrix. That is useful deduplication, but the population proportions do no work.
A stronger alternative would give each type a response distribution and constrain its expected accuracy, or impose a mass-weighted average accuracy condition. Those are plausible cohort models, but they replace the paper’s realized, per-worker accuracy constraints. In particular, pooling responses discards the across-question patterns that its identifiability argument uses. Adding enough detail to retain those patterns brings the model back to distinct response-profile types. This is not an objection that the continuous answer might be easy; it is that the proposed extension changes the information model before it yields a continuous-population complexity question.
The negative case has a real weak point: a large platform with many repeated, deterministic worker profiles is plausible, and the authors might recognize mass-compressed recovery as their problem. But the paper does not establish that its theorem’s guarantee is useful in that regime, and its one named theorem gives ChoCo no computational result to mirror. On the evidence here, the mirror is a possible new formulation, not a worthwhile continuization of the paper’s result.
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.