StoqMA(2) contains NP via Õ(√n)-qubit unentangled stoquastic proofs (nearly perfect completeness) and is contained in EXP, with ETH-optimal parameters matching a refined BKS Sum-of-Squares bound.
A Survey on Distribution Testing: Your Data is Big
3 Pith papers cite this work, alongside 37 external citations. Polarity classification is still indexing.
3
Pith papers citing it
37
external citations · OpenAlex
citation-role summary
method 1
citation-polarity summary
years
2026 3roles
method 1polarities
use method 1representative citing papers
A randomized (1±ε)-approximation algorithm for TV distance between k-mixtures of product distributions runs in poly((nq)^k, 1/ε) time, with exact poly(n, 2^{O(k)}) deterministic algorithm for Boolean subcubes and #P-hardness for k=Θ(n).
Develops generator-agnostic audits for combinatorial uniformity on the hypersimplex using marginal chi-square, pair maxima, serial overlap, anchored-box discrepancy and low-dimensional geometry, with a finite-witness guarantee.
citing papers explorer
-
The power of unentanglement without destructive interference
StoqMA(2) contains NP via Õ(√n)-qubit unentangled stoquastic proofs (nearly perfect completeness) and is contained in EXP, with ETH-optimal parameters matching a refined BKS Sum-of-Squares bound.
-
On Computing Total Variation Distance Between Mixtures of Product Distributions
A randomized (1±ε)-approximation algorithm for TV distance between k-mixtures of product distributions runs in poly((nq)^k, 1/ε) time, with exact poly(n, 2^{O(k)}) deterministic algorithm for Boolean subcubes and #P-hardness for k=Θ(n).
-
Auditing Combinatorial Randomness from Finite Transcripts
Develops generator-agnostic audits for combinatorial uniformity on the hypersimplex using marginal chi-square, pair maxima, serial overlap, anchored-box discrepancy and low-dimensional geometry, with a finite-witness guarantee.