Research map / Learning theory and algorithms / Prediction and decision losses
Fast Channel Simulation via Error-Correcting Codes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PolarSim, which uses polar codes to simulate i.i.d. copies of binary-output channels with near-optimal rate and pseudolinear complexity in block length.
Problem
Channel simulation (generating channel outputs with a specified conditional distribution using minimal communication) has schemes whose complexity grows exponentially with the block length, preventing amortization gains from many channel uses.
Approach
Applies polar codes (via the duality between channel coding and simulation) to simulate symmetric binary-output channels; polarization makes the subchannels nearly deterministic so a simple toy scheme with prefix-free compression achieves rate approaching mutual information with O(n log n) complexity.
Key results
- PolarSim at block length 2^12 achieves rates close to the mutual information lower bound for BSC, binary erasure, and binary Gaussian channels, with redundancy decreasing as block length grows.
- PolarSim outperforms GPRS in rate for BSC simulation, and runs over four orders of magnitude faster at block length 2^12 (median 0.009 s vs about 192-246 s for GPRS scaled from n=8).
- Theorem 1 shows PolarSim simulates the channel exactly and is asymptotically rate optimal (rate approaches I(X;Y)) under symmetry conditions with a prefix-free compressor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PolarSim instead of GPRS | BSC simulation · BSC simulation, p = 0.00 | execution time: 0.009 vs 192.0 | Helped |
| Use PolarSim instead of GPRS | BSC simulation · BSC simulation, p = 0.25 | execution time: 0.009 vs 246.1 | Helped |
| Use PolarSim instead of GPRS | BSC simulation · BSC simulation, p = 0.49 | execution time: 0.009 vs 227.7 | Helped |
| Increase block length | PolarSim · BSC, binary Gaussian, and binary erasure channels | rate | Helped |
| Increase block length | PolarSim · BSC, binary Gaussian, and binary erasure channels | variance in rate | Helped |
| Use PolarSim rather than GPRS | BSC simulation · BSC simulation | communication rate | Helped |
Surprising findings
- A simple linear-code-based alternative (randomized frozen bits with post-correction) achieves performance comparable to PolarSim for BSC simulation.
Limitations
- Basic polar codes only handle symmetric binary-output channels, so general channels are not covered.
- Redundancy of PolarSim grows at large block lengths relative to some prior schemes, a consequence of polar code finite-length performance.
- Trellis-coded quantization extension gives only approximate, not exact, simulation of the Gaussian channel.
Experimental setup
Metrics: communication rate (bits per dimension) redundancy relative to mutual information execution time
Baselines: Greedy Poisson Rejection Sampling (GPRS) Harsha et al. rejection sampler
Builds on: polar codes Li and El Gamal strong Poisson functional representation Greedy Poisson Rejection Sampling Zamir and Feder dithered quantization
Closest papers by meaning
- DeepPolar: Inventing Nonlinear Large-Kernel Polar Codes via Deep Learning (ICML 2024 · similarity 0.81)
- Channel Simulation and Distributed Compression with Ensemble Rejection Sampling (NeurIPS 2025 · similarity 0.81)
- Learning Linear Block Error Correction Codes (ICML 2024 · similarity 0.81)
- A Communication-Theoretic Framework for LLM Agents: Cost-Aware Adaptive Reliability (NeurIPS 2026 · similarity 0.80)
- Universal Sample Coding (NeurIPS 2024 · similarity 0.80)
- Friendly Attacks to Improve Channel Coding Reliability (AAAI 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.