nucleation

CLAIM-304: A rendering can keep a distinction recoverable in principle and make it infeasible to recover: if pseudorandom generators exist, a uniformly random bit can be encoded so that an unbounded receiver recovers it except with probability at most 2⁻⁽ⁿ⁺¹⁾, while no efficient receiver does non-negligibly better than chance

2 min read

Properties9
StatusActive
Rolethesis
Warrantdemonstrated
Tagsinformation-theory, pragmatics, mathematics
Lineformal-apparatus, pragmatic-transport
Rests onCLAIM-302 — Equivalence under feasible tests can be much coarser than statistical equivalence: there are ensembles almost disjoint from uniform that no polynomial-size test tells apart from it, and efficiently samplable ensembles of this kind exist if pseudorandom generators do
GroundsCASE-083 — A pseudorandom generator's output against uniform strings: almost disjoint in total variation, indistinguishable to every efficient test if the generator is secure, THEORY-352 — A pseudorandom generator exists if and only if a one-way function exists, where both are secure against uniform adversaries and every reduction is an oracle Turing machine, as statements about ensembles indexed by n; the construction from an arbitrary one-way function is only weak-preserving, so security at one length is bought at a much greater one
SupportsCLAIM-401 — The conditions an effective description is commonly asked to meet are not of one kind: predictive sufficiency and approximation fidelity are adequacy relative to a declared target, metric and horizon; tractability restricts the operations under which adequacy is assessed; dynamical independence and memory closure are relations of the representation to the system, memory relative to a chosen projection; so a matrix over them as independent binary axes conflates kinds
ComplementsCLAIM-199 — Blackwell's order bounds what a rendering makes possible for any receiver, and a given receiver's access is usable information relative to the rules it can apply, which a garbling can raise for that receiver but never above what the source makes possible

Graph View

The claim

A14 §1: “A distinction may survive a transformation in principle while becoming too computationally expensive for the receiver to recover.” A18: “A suitable formal construction must specify both the transformation and the restricted decoder family.”

Construction, from CASE-083. Render a bit b as a sample from G(Uₙ) if b = 1 and from U₂ₙ if b = 0. An unbounded receiver guesses 1 exactly when the sample is in G’s image. It is never wrong when b = 1, and wrong when b = 0 with probability at most 2ⁿ/2²ⁿ = 2⁻ⁿ, so with b uniform its overall error is at most 2⁻⁽ⁿ⁺¹⁾. The rendering preserves b almost exactly. Any efficient receiver that guessed b with non-negligible advantage would be a test distinguishing G(Uₙ) from U₂ₙ, which a secure generator rules out: a receiver right with probability ½ + ε is a distinguisher with gap 2ε (Goldreich’s Definition 3.2; the guarantee is asymptotic, for the ensemble indexed by n). The construction is the record’s; the book supplies its ingredients, not it (CLAIM-302).

What it bears on

  • CLAIM-199. Its receivers are restricted by a rule class: the one-coordinate receiver gains from an XOR it cannot compute. Here they are restricted by a budget, and the rendering loses for all of them. A15 §4: “fidelity isn’t generally monotonic in either representation size or computational effort.”
  • CLAIM-117 asks whether translation preserves the dynamics of interpretation. A14: even if the dynamics correspond mathematically, a bounded receiver may not be able to recover or enact the correspondence.
  • QUESTION-111 asks where the line falls for communicative distinctions. This shows only that it can fall anywhere.

What it does not say

That ordinary renderings do this. Nothing communicative is a pseudorandom generator. The construction shows the gap between keeping a distinction and making it available is not an artefact of a chosen rule class.

Backlinks