CounterexampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Entry queries alone do not provide Tang's sampling access

Statement refuted

Entry queries to a matrix alone imply Tang's polylogarithmic-in-dimension recommendation sampling cost.

Facts & Assumptions

Given: An integer $n \geq 2$ , an unknown index $j \in [n]$ , the one-row matrix $A^{(j)} = (e_{j})^{T}$ , and a randomized sampler required to output from the row's squared-entry distribution within total variation $1 / 3$ . Here $e_{j}$ is the $j$ th standard basis vector; an entry query costs one operation and returns $1$ at $j$ and $0$ elsewhere.

[F1]

ℓ2 sample/query access to vectors and matrices: the row sampler must output from $D_{A_{1, *}^{(j)}}$ ; entry queries alone are a different interface.

[F2]

Tang's conditional recommendation sampler: Tang's theorem assumes the stated row/column ℓ2 sample/query access and does not grant that access from entry queries.

[F3]

End-to-end channel and output error contract: total variation distance from a point mass at $j$ is one minus the probability assigned to $j$ .

Counterexample

1.1givenF1F3algebra

The squared-entry law of $A^{(j)}$ is the point mass at $j$ . By [F3], error at most $1 / 3$ requires output $j$ with probability at least $2 / 3$ .

1.2givenalgebrachoose

Fix the algorithm's internal randomness and suppose it makes at most $t < n$ distinct entry queries. If the queried set contains $j$ , it can identify $j$ ; averaged over a uniformly chosen hidden $j$ , this event has probability at most $t / n$ . If the queried set does not contain $j$ , all observed answers are zero and the fixed execution can output at most one of the $n - t$ unqueried indices, so its conditional chance to guess correctly is at most $1 / (n - t)$ . Thus average success is at most $t / n + (1 - t / n) / (n - t) = (t + 1) / n$ . Averaging over internal randomness preserves this bound.

2.1step 1.1step 1.2F2algebra∎

To achieve success at least $2 / 3$ for every hidden $j$ , the average success must be at least $2 / 3$ , so $(t + 1) / n \geq 2 / 3$ and $t \geq 2 n / 3 - 1 = Ω (n)$ . Hence the entry-query interface cannot supply the claimed sublinear sampling cost; any preprocessing that builds a sampler must also be charged. The condition of [F2] is therefore essential.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

30 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ewin Tang, A quantum-inspired classical algorithm for recommendation systems, version 3 (standard reference, not scraped)