d4-conf-aaai-2023-2057

The best positive case is a type-level version of the paper’s fault-estimation problem. It is a tractability case, not a hardness-dissolution case: the paper gives no named NP-hardness result to carry into a continuum.

My anchor is Theorem 6, proved in this paper. It gives an exact solution to a regularized least-squares problem: for a symmetric nonnegative pairwise-distance matrix \(D=(d_{ii'})\) on \(n\) workers and \(\lambda\ge 0\), it minimizes
\[ \sum_{i\ne i'}(\hat f_i+\hat f_{i'}-d_{ii'})^2+\lambda\|\hat{\mathbf f}\|_2^2. \]
Writing \(\pi_i=\frac{1}{n-1}\sum_{i'\ne i}d_{ii'}\) and \(\bar\mu=\frac{1}{2n}\sum_i\pi_i\), the minimizer is
\[ \hat{\mathbf f} = \frac{2(n-1)\boldsymbol\pi-\frac{8n(n-1)}{4n+\lambda-4}\bar\mu\,\mathbf 1} {2n+\lambda-4}. \]
The theorem does not label this problem “in P,” but its closed-form solution gives a polynomial-time algorithm for rational input. This is a genuine computational anchor: the paper computes the estimator, rather than merely proposing a formulation.

Here is the continuous problem I would put to a prover: Type-Aggregated Proximity Fault Recovery. The instance is a finite set \(\Theta\) of \(\tau\) worker types, rational masses \(\mu_t>0\) summing to one, and a symmetric rational matrix \(D\). A type is a complete report-noise law for the task; its fault is \(f_t=\mathbb E[d(s,z)\mid t]\). The entry \(D_{tu}\) is the mean distance between reports from two distinct workers of types \(t\) and \(u\); for \(t=u\), it is the within-type mean over distinct workers. The question is to output the type-fault estimates \(\hat f_t\) minimizing
\[ \sum_{t,u\in\Theta}\mu_t\mu_u \bigl(\hat f_t+\hat f_u-D_{tu}\bigr)^2. \]
The masses weight each type pair by its share of the population. Under the paper’s unbiased pairwise additive model, expected pairwise distance has the form \(f_t+f_u\), which is exactly the relation this estimator fits. In the continuum, same-type pairs are pairs of different agents; self-pairs have zero mass.

This is a plausible high-multiplicity regime for a large, repeated crowdsourcing task with relatively few stable worker cohorts—for example, cohorts with shared training or language profiles and hence a shared answer-noise law. There may be many workers but only \(\tau\) distinct types. That preserves the paper’s question—estimating competence from proximity to other workers—while replacing the finite worker vector with a type-level fault profile. The authors already define a proto-population distribution over worker types, so this population interpretation is close to their model.

I expect this continuous problem to be tractable. Its objective is a rational convex quadratic in \(\tau\) variables. Because every \(\mu_t\) is positive, the \(t=u\) terms contribute positive curvature in each coordinate, making the objective strictly convex. Solving its normal equations gives the unique minimizer in polynomial time in \(\tau\) and the input bit length \(L\). Theorem 6 supplies the finite-worker least-squares template; the mass-weighted system is its natural type-aggregated extension. This covers the paper’s fault estimation in Sections 3 and 4, and the fault estimates used by P-TD, not its empirical comparison of aggregation algorithms or every truth-discovery model.

The mirror’s weakest point is that this version takes the type partition and type-pair distance summaries as input. In the paper, worker types are latent and the algorithm works from individual reports. A reviewer could reasonably ask whether cohort labels are available, or whether estimating them is part of the real problem. My answer is that type-labelled cohorts are a plausible instance regime, and the mirror keeps the central proximity-based fault-recovery question. But this does not establish tractability when types are hidden, and it should not be sold as a complexity result already proved by the paper. The paper’s own proto-population distribution supports the modeling choice; it does not solve that latent-mixture question.