nucleation

QUESTION-103: Is computational indistinguishability the bounded-observer form of signal detection's chance ROC, and is ideal-observer efficiency its empirical measure, so that the record's formal results on bounded observers can be tested on real ones?

4 min read

Properties4
StatusOpen
Tagsprobabilistic-modeling, information-theory, cognition
Lineformal-apparatus
BearingTHEORY-336 — An ideal observer is optimal relative to the information it is given, so a constrained ideal is the optimal decoder of a degraded input, not a restricted decoder of the full one; comparing real observers with ideals taken at successive stages of the visual system places losses by stage, and in early-vision tasks human performance is reported often to parallel the retinal-stage ideal across conditions while falling well below it, THEORY-357 — Computational indistinguishability is strictly coarser than statistical closeness: without any assumption there are ensembles on at most 2^(n/2) strings that no circuit of size 2^(n/8) tells from uniform, though none of them is efficiently samplable, and an efficiently samplable pair of this kind exists if a pseudorandom generator does, since its output covers at most 2^n of the 2^l(n) strings; all of it is about ensembles indexed by n, not single pairs of distributions, THEORY-349 — For binary outcomes and a fixed representation of individuals, a predictor can pass every test in a bounded class without being close to nature: outcome indistinguishability to tests that see the sampled prediction is equivalent, with stated losses, to multicalibration over a closely related class of sets, a predictor meeting it exists at size polynomial in the tests' size and the tolerance whatever nature's complexity, and learning one is as hard as weak agnostic learning of the class

Graph View

Why it is a question

The owner, 2026-10-15: “I’m wondering if maybe material downstream of the computational indistinguishability work might be helpful as well. or maybe we can connect that angle to the signal detection literature?”

The formal link. For a test f between two hypotheses, the distinguishing advantage |Pr[f = 1 | x] − Pr[f = 1 | x′]| is hit rate minus false-alarm rate, one point on f’s ROC. Over all tests its maximum is the total variation distance, attained by thresholding the likelihood ratio. The record holds that half: THEORY-031 (from Peterson and Birdsall, LIT-364) says the likelihood-ratio detector is optimal and performance is an ROC. CLAIM-302 says that for a restricted class of observers the best ROC can sit near the chance diagonal while the ideal one is near perfect. So the record’s formal results on bounded observers are statements about the gap between the ideal ROC and the best ROC in a class.

The empirical side. Vision science measures that gap: efficiency, the squared ratio of human to ideal d′ (Burgess et al. 1981; Pelli and Farell 1999, neither held), says how much of the information a real observer uses; Geisler 2011 (LIT-1055) reviews the ideal-observer method without giving the formula. If the link holds, the bounded- observer questions (QUESTION-111, QUESTION-104) have a measure that can be taken on people and models, not only constructed.

Downstream of indistinguishability.

  • Pseudoentropy (Håstad, Impagliazzo, Levin and Luby 1999, LIT-1051): information content as efficient observers can tell, a candidate for the quantity QUESTION-110 asks for.
  • Outcome indistinguishability and multicalibration (Dwork et al. 2021, LIT-1068; Hébert-Johnson et al. 2018, LIT-1052): a predictor is adequate relative to a class of distinguishers if none of them can tell its outcomes from nature’s. That is individuation by sufficiency (CLAIM-152) with the observer’s resources explicit.

What would answer it. A statement of the correspondence precise enough to fail: which SDT quantity corresponds to advantage, whether a criterion shift has a counterpart (indistinguishability is criterion-free, as d′ is only in the equal-variance case, THEORY-031), and whether efficiency is well defined for a class of observers rather than one. A second part would test it: a case where the record’s formal gap is measured as an efficiency. A possible use for CLAIM-298, speculative: SDT separates a change in the evidence (d′) from a change in criterion (bias), which may be the split that claim needs between what is retrieved and how it is weighed.

Note of 2026-10-15: what the four readings found

All four were read the same day. The bridge is narrower than first stated.

  • Ideal-observer analysis bounds a different observer. Geisler (LIT-1055, NOTE-870) constrains the ideal observer by degrading its input, a garbling that loses information. CLAIM-302 keeps the input and restricts the class of tests. These are the two receivers CLAIM-199 already separates, Blackwell’s ceiling and a rule class. So efficiency measures the first gap, and computational indistinguishability describes the second; a measure of the second on real observers is still wanting. The review also gives no formula for efficiency: the squared ratio of d′ above is from Burgess et al. 1981 and Pelli and Farell 1999, neither held.
  • Pseudoentropy (LIT-1051, NOTE-880). Håstad et al. define computational entropy with Shannon entropy and call indistinguishability “the computationally restricted adversary definition of statistical distance”. The claims’ G(Uₙ) is, in their terms, a false entropy generator. Their time–success ratio is a worked recovery-cost measure for QUESTION-110.
  • Outcome indistinguishability (LIT-1068, NOTE-885) is the paper that frames adequacy as indistinguishability to a class, not multicalibration (LIT-1052, NOTE-879), as first attributed above. Its finding for QUESTION-104: the observer’s access matters as much as its budget, and with oracle or code access a cheap observer can force a model as complex as nature.
  • None of the four mentions signal detection. The link to ROC and d′ is the record’s, and the criterion question is open.

Backlinks