Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets
Abstract
We study noninteractive simulation from a finite correlated source. Alice and Bob observe independent copies of the source and generate outputs without communication. We give a quantitative construction for arbitrary finite output alphabets: for every fixed source, a joint law that is simulable with arbitrarily many samples can be approximated using a number of samples polynomial jointly in the output alphabet sizes and the inverse accuracy. We first study binary outputs. A one-sided Wright--Fisher comparison gives a source-dependent explicit exponent and a finite-head Gaussian-threshold representation. We then handle arbitrary finite output alphabets through averaged influence regularity, simplex-preserving Gaussian moment lifting, and a common Gaussian projection for all correlated-prefix states. The sample exponent is independent of the output alphabet sizes. For a concrete biased binary source we certify an explicit exponent below $19$.
Related
- On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Polynomial complexity, random graphs, and strict ergodicity
- Fatou Components of Attracting Skew Products: From Polynomial Classification to Transcendental Complexity
- Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
BibTeX
@misc{wang2026polynomial,
title = {{Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets}},
author = {Haoran Wang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.11974},
eprint = {2611.11974},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.11974},
}
RIS
TY - UNPB
TI - Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets
AU - Haoran Wang
PY - 2026
DA - 2026/11/09
PB - arXiv
DO - 10.48550/arxiv.2611.11974
UR - https://arxiv.org/abs/2611.11974
AB - We study noninteractive simulation from a finite correlated source. Alice and Bob observe independent copies of the source and generate outputs without communication. We give a quantitative construction for arbitrary finite output alphabets: for every fixed source, a joint law that is simulable with arbitrarily many samples can be approximated using a number of samples polynomial jointly in the output alphabet sizes and the inverse accuracy. We first study binary outputs. A one-sided Wright--Fisher comparison gives a source-dependent explicit exponent and a finite-head Gaussian-threshold representation. We then handle arbitrary finite output alphabets through averaged influence regularity, simplex-preserving Gaussian moment lifting, and a common Gaussian projection for all correlated-prefix states. The sample exponent is independent of the output alphabet sizes. For a concrete biased binary source we certify an explicit exponent below $19$.
ER -