Hard-to-Sample Distributions from Robust Extractors

Anthony Ostuni; Daniel M. Kane; Farzan Byramji; Jackson Morris

arxiv: 2604.26179 · v2 · submitted 2026-04-28 · 💻 cs.CC

Hard-to-Sample Distributions from Robust Extractors

Farzan Byramji , Daniel M. Kane , Jackson Morris , Anthony Ostuni This is my paper

Pith reviewed 2026-05-11 00:42 UTC · model grok-4.3

classification 💻 cs.CC

keywords robust extractorssampling hardnessmin-entropy extractorslow-depth circuitspolynomial sourcesstatistical distancerestricted samplers

0 comments

The pith

Robust extractors yield explicit distributions at distance 1-o(1) from any output of low-depth circuits, small-space sources, and low-degree polynomial sources.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces robust extractors, which are extractors that stay sound even if a few input points violate the min-entropy condition. These objects are used to build explicit target distributions that restricted sampling models cannot approximate. For low-depth circuits, small-space sources, and similar models, every possible output lies at statistical distance 1-o(1) from the target. The same technique produces the first explicit hardness result for low-degree F2-polynomial sources. A reader cares because the argument unifies many earlier separate proofs that simple computational models cannot generate certain distributions.

Core claim

What carries the argument

Robust extractors: extractors that remain sound even when a small number of points violate the min-entropy constraint, allowing the construction of hard target distributions for restricted samplers.

If this is right

No low-depth circuit can sample the constructed distribution with error o(1).
No small-space source can sample it with error o(1).
No low-degree F2-polynomial source can sample it with error o(1).
The same framework recovers all prior sampling hardness results for the listed models in a single argument.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If better robust extractors are found, the same method could rule out sampling for additional circuit classes such as AC0[oplus].
The approach may extend to other extractor-based separations in complexity theory where small violations of entropy conditions occur.
Concrete parameters from the Chattopadhyay et al. construction determine the exact entropy thresholds at which the hardness holds for polynomial sources.

Load-bearing premise

Explicit robust extractors with the required parameters exist for the min-entropy regimes of the models under consideration.

What would settle it

An explicit low-depth circuit, small-space source, or low-degree F2-polynomial source whose output distribution has statistical distance o(1) from the paper's constructed target would falsify the central claim.

read the original abstract

We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of robust extractors, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, we show that for a broad range of sampling models (e.g., low-depth circuits, small-space sources, etc.), every output of the model has distance $1 - o(1)$ from our target distribution, qualitatively recovering essentially all previously known hardness results. Our work extends that of Viola (SICOMP '14), who developed an earlier unified framework based on traditional extractors to rule out sampling with very small error. As a further application of our technique, we leverage a recent extractor construction of Chattopadhyay, Goodman, and Gurumukhani (ITCS '24) to present the first explicit distribution with distance $1 - o(1)$ from the output of any low-degree $\mathbb{F}_2$-polynomial source. We note that a similar bound was obtained concurrently and independently by Khodabandeh and Shinkar (ECCC '26). We also describe a potential avenue toward proving a similar hardness result for $\mathsf{AC^0}[\oplus]$ circuits.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Robust extractors give a clean unified framework for 1-o(1) sampling hardness across models and a new explicit bound for low-degree polynomial sources, though the robustness modification needs parameter checks.

read the letter

The main thing to know is that this paper defines robust extractors to get a single framework that recovers most known 1-o(1) sampling hardness results for restricted models and adds one for low-degree F2-polynomial sources. It does a good job unifying the earlier work. Viola had a framework with ordinary extractors, but this robust version handles the cases where the sampler might not always respect the entropy promise. The reduction to statistical distance 1-o(1) looks direct from the abstract. For the polynomial sources they use the recent explicit extractor from Chattopadhyay et al. and extend it to be robust, which gives the new result. Noting the concurrent work is honest. The soft spot is exactly the one in the stress test. Adding robustness might change the extractor parameters, like needing more min-entropy or allowing only weaker error. If that happens, the 1-o(1) distance may not go through for every model listed. The paper claims it works, but since it relies on modifying an external construction, the details matter. The abstract is high-level, so the body needs to show the parameters stay sufficient. The qualitative bound gives some slack, though. This is for complexity people who follow extractor constructions and hardness of sampling. A reader who knows the prior papers on Viola and the ITCS 2024 extractor will see the advance clearly. It is worth a serious referee because the new object is well-motivated and the unification is useful, even if the robustness step needs verification. The thinking seems solid and it engages the literature properly. I would send it to review.

Referee Report

2 major / 2 minor

Summary. The paper introduces robust extractors (extractors that remain sound even when a small fraction of inputs violate the min-entropy promise) and uses them to give a unified construction of explicit distributions that are at statistical distance 1-o(1) from every output of several restricted sampling models, including low-depth circuits and small-space sources. This recovers prior hardness results in a single framework extending Viola (SICOMP '14). As a new application, the authors leverage the Chattopadhyay-Goodman-Gurumukhani (ITCS '24) extractor to obtain the first explicit 1-o(1)-hard distribution for low-degree F_2-polynomial sources, noting a concurrent independent result by Khodabandeh-Shinkar; they also sketch a possible route for AC^0[oplus] circuits.

Significance. If the robust-extractor parameters carry over as stated, the work supplies a clean, modular technique that qualitatively unifies many sampling-hardness theorems and adds a concrete new result for polynomial sources. The approach is parameter-light on the target side and directly exploits recent explicit extractor constructions, which is a methodological strength.

major comments (2)

[Abstract and polynomial-source application] Abstract and the section applying Chattopadhyay et al. (ITCS '24): the claim that robustness can be added 'while retaining the original extraction guarantees' (min-entropy rate k, error ε, output length) must be accompanied by an explicit parameter calculation showing that the resulting ε is small enough relative to the support size of a degree-d polynomial source to force statistical distance 1-o(1). Without this, the new hardness result for polynomial sources does not follow.
[Unified framework] Unified-framework section: the argument that the same target distribution yields distance 1-o(1) uniformly across all listed models (low-depth circuits, small-space, etc.) relies on the robust extractor inheriting the exact quantitative bounds of the underlying non-robust constructions; a short table or lemma verifying the required min-entropy threshold and error for each model would make the recovery of prior results fully rigorous.

minor comments (2)

The definition of robustness (the precise fraction of violating inputs and how soundness is quantified) should be stated as a formal definition before the applications, to avoid any ambiguity when the same object is invoked for multiple sampler classes.
A brief comparison paragraph with the concurrent Khodabandeh-Shinkar result would help readers assess the relative novelty of the polynomial-source bound.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address the two major comments below and will revise the manuscript to strengthen the rigor of the claims.

read point-by-point responses

Referee: [Abstract and polynomial-source application] Abstract and the section applying Chattopadhyay et al. (ITCS '24): the claim that robustness can be added 'while retaining the original extraction guarantees' (min-entropy rate k, error ε, output length) must be accompanied by an explicit parameter calculation showing that the resulting ε is small enough relative to the support size of a degree-d polynomial source to force statistical distance 1-o(1). Without this, the new hardness result for polynomial sources does not follow.

Authors: We agree that an explicit parameter calculation is required to rigorously close the argument for the polynomial-source hardness result. In the revised version we will add a short calculation (in the application section) that starts from the min-entropy rate, error, and output length of the Chattopadhyay-Goodman-Gurumukhani extractor, shows how the robust-extractor transformation preserves these quantities up to negligible additive losses, and verifies that the final statistical distance to any degree-d F_2-polynomial source is 1-o(1) by comparing ε against the inverse of the source support size (at most 2^{O(d n^{1-1/d})}). This will make the new application fully self-contained. revision: yes
Referee: [Unified framework] Unified-framework section: the argument that the same target distribution yields distance 1-o(1) uniformly across all listed models (low-depth circuits, small-space, etc.) relies on the robust extractor inheriting the exact quantitative bounds of the underlying non-robust constructions; a short table or lemma verifying the required min-entropy threshold and error for each model would make the recovery of prior results fully rigorous.

Authors: We accept that an explicit verification of the quantitative parameters would improve clarity. We will insert a compact lemma (or table) in the unified-framework section that, for each sampling model, records the min-entropy threshold k(n) and error ε(n) needed to obtain statistical distance 1-o(1), and confirms that the robust extractor we construct meets these bounds by inheriting the parameters of the underlying non-robust extractor (with only o(1) degradation). This will make the recovery of prior results (including Viola SICOMP '14) completely rigorous without altering any claims. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on external extractor constructions

full rationale

The paper defines robust extractors as a new notion and proves that they yield hard-to-sample distributions for various models by showing statistical distance 1-o(1) from sampler outputs. This follows from the extractor properties applied to independently chosen target distributions, extending Viola's prior framework without any reduction of the distance bound to a fitted parameter, self-definition, or internal ansatz. The key polynomial-source case invokes the external Chattopadhyay-Goodman-Gurumukhani ITCS 2024 construction (with an assumption that robustness preserves parameters), which is independent evidence rather than a self-citation chain. No steps reduce by construction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on the standard definition of extractors and min-entropy, plus the existence of a specific recent extractor construction. No new free parameters are introduced; the only invented entity is the robust extractor itself, which is defined rather than postulated.

axioms (1)

domain assumption Standard properties of seeded extractors remain valid when a small fraction of inputs violate the min-entropy condition.
Invoked when the robust extractor is used to bound the statistical distance for arbitrary samplers.

invented entities (1)

robust extractor independent evidence
purpose: An extractor that remains sound on all but a small fraction of inputs that may violate min-entropy.
Defined in the paper to enable the unified hardness construction; independent evidence is the cited extractor construction that satisfies the robust property.

pith-pipeline@v0.9.0 · 5533 in / 1477 out tokens · 46673 ms · 2026-05-11T00:42:35.909745+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of robust extractors...
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2.5... (α, β, k)-isolator... TV distance ≥ 1−o(1)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

Sampling permutations with cell probes is hard

1 [AGM+26] Yaroslav Alekseev, Mika G¨ o¨ os, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov. Sampling permutations with cell probes is hard. InProceedings of the 58th Annual ACM Symposium on Theory of Computing (to appear), 2026. 2 [AGMR25] Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and Jo˜ ao Ribeiro. Low-degree polynomials are good extra...

work page 2026
[2]

Schulman, Amnon Ta-Shma, Umesh Vazirani, and Avi Wigderson

1, 2 [ASTS+03] Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh Vazirani, and Avi Wigderson. The quantum communication complexity of sampling.SIAM J. Comput., 32(6):1570–1585, 2003. 2, 3, 21, 22 [Bab87] L´ aszi´ o Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26(1):51–53, 1987. 2 [BIL12...

work page 2003
[3]

Tight bounds on depth- 2 QAC-circuits computing parity.arXiv preprint arXiv:2504.06433,

ECCC version:https://eccc.weizmann.ac.il/report/2021/106/. 2, 3, 5, 6, 10, 21, 25 [DH25] Dean Doron and William M. Hoza. Implications of better PRGs for permutation branching programs. InApproximation, randomization, and combinatorial optimiza- tion. Algorithms and techniques, volume 353 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 28, 20. Schloss...

work page arXiv 2021
[4]

Extractors for circuit sources.SIAM Journal on Computing, 43(2):655–672, 2014

2, 3, 8, 26 31 [Vio14] Emanuele Viola. Extractors for circuit sources.SIAM Journal on Computing, 43(2):655–672, 2014. 2, 3, 4, 12, 17, 18 [Vio16] Emanuele Viola. Quadratic maps are hard to sample.ACM Transactions on Compu- tation Theory (TOCT), 8(4):1–4, 2016. 4 [Vio20] Emanuele Viola. Sampling lower bounds: boolean average-case and permutations. SIAM Jou...

work page 2014
[5]

Separating the polynomial-time hierarchy by oracles

2 [Yao85] Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles. In26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 1–10. IEEE,

work page 1985
[6]

Affine extractors over prime fields.Combinatorica, 31(2):245–256,

1, 2 [Yeh11] Amir Yehudayoff. Affine extractors over prime fields.Combinatorica, 31(2):245–256,

work page
[7]

Sampling, flowers and communication

27 [YZ24] Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In15th Innova- tions in Theoretical Computer Science Conference (ITCS 2024), pages 100–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2024. 2, 3, 21 A A Non-Constructive Argument It is often much simpler to show the mere existence of specific objects than to provide explicit e...

work page 2024

[1] [1]

Sampling permutations with cell probes is hard

1 [AGM+26] Yaroslav Alekseev, Mika G¨ o¨ os, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov. Sampling permutations with cell probes is hard. InProceedings of the 58th Annual ACM Symposium on Theory of Computing (to appear), 2026. 2 [AGMR25] Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, and Jo˜ ao Ribeiro. Low-degree polynomials are good extra...

work page 2026

[2] [2]

Schulman, Amnon Ta-Shma, Umesh Vazirani, and Avi Wigderson

1, 2 [ASTS+03] Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh Vazirani, and Avi Wigderson. The quantum communication complexity of sampling.SIAM J. Comput., 32(6):1570–1585, 2003. 2, 3, 21, 22 [Bab87] L´ aszi´ o Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26(1):51–53, 1987. 2 [BIL12...

work page 2003

[3] [3]

Tight bounds on depth- 2 QAC-circuits computing parity.arXiv preprint arXiv:2504.06433,

ECCC version:https://eccc.weizmann.ac.il/report/2021/106/. 2, 3, 5, 6, 10, 21, 25 [DH25] Dean Doron and William M. Hoza. Implications of better PRGs for permutation branching programs. InApproximation, randomization, and combinatorial optimiza- tion. Algorithms and techniques, volume 353 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 28, 20. Schloss...

work page arXiv 2021

[4] [4]

Extractors for circuit sources.SIAM Journal on Computing, 43(2):655–672, 2014

2, 3, 8, 26 31 [Vio14] Emanuele Viola. Extractors for circuit sources.SIAM Journal on Computing, 43(2):655–672, 2014. 2, 3, 4, 12, 17, 18 [Vio16] Emanuele Viola. Quadratic maps are hard to sample.ACM Transactions on Compu- tation Theory (TOCT), 8(4):1–4, 2016. 4 [Vio20] Emanuele Viola. Sampling lower bounds: boolean average-case and permutations. SIAM Jou...

work page 2014

[5] [5]

Separating the polynomial-time hierarchy by oracles

2 [Yao85] Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles. In26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 1–10. IEEE,

work page 1985

[6] [6]

Affine extractors over prime fields.Combinatorica, 31(2):245–256,

1, 2 [Yeh11] Amir Yehudayoff. Affine extractors over prime fields.Combinatorica, 31(2):245–256,

work page

[7] [7]

Sampling, flowers and communication

27 [YZ24] Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In15th Innova- tions in Theoretical Computer Science Conference (ITCS 2024), pages 100–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2024. 2, 3, 21 A A Non-Constructive Argument It is often much simpler to show the mere existence of specific objects than to provide explicit e...

work page 2024