ProCreations/repro-allocating-variance-to-maximize-expectation

Reproduction - Allocating Variance to Maximize Expectation

Independent CPU-only audit of all six registered claims. Fifteen gates test 28,944 independent discretization cells, positive-semidefinite correlated allocations, 39,270 GraphVarAlloc reference allocations, 4,096 concentration-support cells, 25.17 million n=8 Gaussian/mask cells, and destructive controls. All gates pass in two warning-strict byte-identical runs and a packaged replay. Finite searches are reported as falsification attempts, not theorem proofs.

Primary source: https://arxiv.org/pdf/2502.18463v1 OpenReview: https://openreview.net/forum?id=vqxprtjuKH Primary PDF SHA-256: 6cfa1766eb771935178e039febd987febd54e6a9e4439ec910cf1f975b82006b No competitor artifact or result was used.

Registered claims

1. 1.For the independent Gaussian variance allocation problem, the paper gives a PTAS achieving E[maxi Xi] ≥ OPT - ε in polynomial time (Theorem 1.1, Section 1.2).
2. 2.For correlated Gaussian variables, a PTAS with the same additive ε guarantee is established (Theorem 1.2, Section 1.2).
3. 3.For the GraphVarAlloc problem with multiple constraint sets (general m>1), the paper gives an O(log n) multiplicative approximation guaranteeing Ω(1/log n)·OPT (Theorem 1.3, Section 1.2).
4. 4.Theorem 1.6 proves that in the optimal allocation, only Θ(1/p) variables receive variance Ω(p), i.e., the allocation concentrates on a shrinking subset as the constraint parameter p grows (Theorem 1.6, Section 1.3).
5. 5.Lemma 2.1 bounds the contribution of small-variance variables by O(ε√ln(1/ε)), which is used to limit the number of high-variance variables to O(1/ε²) and underlies the PTAS construction (Lemma 2.1, Section 2.1).
6. 6.Monte Carlo simulations on Erdős–Rényi random graphs with n=8 nodes and edge probabilities p ranging from 1/8 to 8/8 are used to illustrate the concentration and concavity results across independent, positively, and negatively correlated settings (Figures 1-2, Section 1.3).

Reproduce

python3 -m pip install -r requirements.txt
PYTHONWARNINGS=error python3 reproduce.py --output-dir replay
diff -qr outputs replay
python3 build_manifest.py

Reference results SHA-256: 3c7ecd9c02e46357ecf669126f1711073306162cb623cfcb11c52f99c21ea2af.