we-solve (beta)

CS-435 · computer science · mathematics · Computational statistics

Efficient Verification of Distribution Properties

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

An interactive proof exchanges messages between a prover and verifier, with completeness for true assertions and soundness against dishonest provers. Here the verifier samples an unknown distribution and checks an approximate property claim.

Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.

Statement recorded in the supplied source.
Characterize the properties of an unknown distribution for which an untrusted server can generate, in polynomial time, a short interactive proof of an approximately correct assertion that a verifier can check using fewer samples and less computation than independent analysis would require. [S2]
Scope qualification.
The property distance, approximation tolerance, soundness error, server access, and resource comparison are source-specific.
Source status.
The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Characterize distribution properties whose assertions admit efficient verification using fewer resources than direct analysis.

Sources

Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30006181 and source code OWR-14299084-003 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

CS-435-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-435

Efficient Verification of Distribution Properties

Definitions and mathematical statement

Shared notation.
Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

An interactive proof exchanges messages between a prover and verifier, with completeness for true assertions and soundness against dishonest provers. Here the verifier samples an unknown distribution and checks an approximate property claim.

Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.

Statement recorded in the supplied source.
Characterize the properties of an unknown distribution for which an untrusted server can generate, in polynomial time, a short interactive proof of an approximately correct assertion that a verifier can check using fewer samples and less computation than independent analysis would require. [S2]
Scope qualification.
The property distance, approximation tolerance, soundness error, server access, and resource comparison are source-specific.
Source status.
The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Characterize distribution properties whose assertions admit efficient verification using fewer resources than direct analysis.

Sources

Preparation and review.
Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30006181 and source code OWR-14299084-003 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Research attempt

Literature, source context and scope

The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.

The workshop reports broad interactive verification results under specified access and complexity hypotheses. The catalogue question omits the precise property, tolerance and verifier access. This attempt fixes a simple labeled Bernoulli promise and tests whether an untrusted prover can remove the verifier's own statistical sample requirement. It is a restricted lower bound, not a lower bound for every label-invariant property discussed elsewhere in the report.

A sample lower bound even with interaction

Let the verifier's only access to an unknown distribution be at most $m$ independent samples. Its task is to accept $P=\operatorname{Bernoulli}(1/2)$ with probability at least $2/3$ with an honest prover, while accepting $Q=\operatorname{Bernoulli}(1/2+\varepsilon)$ with probability at most $1/3$ against every prover, where $0<\varepsilon\le1/4$. Other random coins and public parameters do not depend on the unknown distribution. The dishonest prover may simulate the honest $P$ prover, including fair-coin samples from $P$.
Proposition: Any such protocol, with arbitrary interaction, satisfies $m\ge1/(18\varepsilon^2)$.
Proof: Under $Q$ use a prover that follows the honest strategy for $P$. Predraw an array of $m$ genuine verifier samples, padding unused entries if the protocol stops earlier. Both complete experiments are obtained from these arrays by the same randomized transformation: the verifier algorithm and the fixed simulated prover strategy. Thus their acceptance-probability difference is at most $\operatorname{TV}(P^m,Q^m)$. To see the contraction directly, conditional acceptance given array $z$ is a common number $h(z)\in[0,1]$; then $|\sum_z h(z)(P^m(z)-Q^m(z))|\le\operatorname{TV}(P^m,Q^m)$ by splitting the signed differences into positive and negative parts.

For any finite distributions $U,V$ with affinity $\rho=\sum_z\sqrt{U(z)V(z)}$, Cauchy--Schwarz gives \[ \operatorname{TV}(U,V)=\frac12\sum_z|\sqrt{U(z)}-\sqrt{V(z)}|(\sqrt{U(z)}+\sqrt{V(z)})\le\sqrt{1-\rho^2}. \] Here the one-sample affinity is $\rho=(\sqrt{1+2\varepsilon}+\sqrt{1-2\varepsilon})/2$, so \[ \rho^2=\frac{1+\sqrt{1-4\varepsilon^2}}2\ge1-2\varepsilon^2. \] The inequality follows from $\sqrt{1-u}\ge1-u$ for $u\in[0,1]$, obtained by squaring its nonnegative sides. Affinities multiply for independent product distributions by expanding the product sums. Therefore \[ \operatorname{TV}(P^m,Q^m)\le\sqrt{1-\rho^{2m}}\le\sqrt{2m}\,\varepsilon, \] using $(1-v)^m\ge1-mv$ for $v\in[0,1]$, proved by induction. Completeness and soundness require an acceptance gap of at least $1/3$, giving the claim. ∎

Verification and remaining gaps

Finite exact-binomial calculations compare product total variation and the affinity bound. The failed route is accepting a claimed mean solely because a prover supplies more computation: the prover can emulate the wrong distribution until the verifier's genuine samples distinguish it. Different oracle access, trusted information, or other distribution properties can change the conclusion. This does not construct or improve the source's general doubly-efficient proof systems.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2025/3. Relevant passages read: OWR 2025/3, printed pages149--150, Rothblum verification talks.

All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.

Integration review.
Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch, read and reviewed the written mathematical arguments, independently reran the finite checks, and contributed formatting/repository review. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

A separate OpenAI gpt-6-astra, reasoning ultra, invocation also read this written argument and independently performed the finite checks specified in the local peer-review audit. The exact serving revision is not exposed. This is model peer review, not independent human verification.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch026/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.

Go to contribution →