Pith. sign in

REVIEW 2 major objections 5 minor 54 references

Pseudorandom bits for non-commutative programs

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that an explicit pseudorandom generator with seed length $c_G \log(n/\varepsilon)$ fools read-once group products over any finite p-group, in any input order, and that the same techniques give near-optimal generators for…

desk verdict Real advance on p-groups, with a localized fixable flaw in the mixing-group definition. read the letter →

arxiv 2506.01832 v2 pith:UUMS6LXS submitted 2025-06-02 cs.CC

Chin Ho Lee , Emanuele Viola This is my paper
classification cs.CC
keywords pseudorandomgeneratorp-groupsread-oncegroupproductsblockmixinggroupsDedekindpolynomialsrepresentationtheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that an explicit pseudorandom generator with seed length $c_G \log(n/\varepsilon)$ fools read-once group products over any finite p-group, even when the input bits may be permuted arbitrarily before the product is evaluated. Earlier, every non-commutative group forced seed length at least $\log n \log(1/\varepsilon)$, so this closes the gap to the optimum for a large class of non-commutative programs. The proof shows that such products are just constant-degree polynomials over $\mathbb{F}_p$, and then derandomizes the noise that previous work left random. A second line of results transfers these ideas to block products and read-once polynomials over any finite field, again with nearly optimal seed length. A third, representation-theoretic construction gives optimal seed length for constant error over mixing groups, such as the quaternion group.

What carries the argument

The central object is the polynomial normal form for p-groups (Lemma 13): after identifying a p-group of order $p^k$ with $\mathbb{F}_p^k$, every read-once product becomes a $k$-tuple of polynomials over $\mathbb{F}_p$ whose degrees are bounded by a constant depending only on the group. This reduces fooling the product to fooling low-degree polynomials over $\mathbb{F}_p$; for $p=2$ known sum-of-small-bias generators apply, and for $p>2$ the paper uses the standard field-element generator converted to biased bits and then derandomizes the noise. The second mechanism is representation theory: a group is called mixing when, for every non-trivial irreducible representation $\rho$ and non-identity element $g$, $\rho(g)$ has no eigenvalue 1. For such groups the averaging operator $(I+\rho(g))/2$ has operator norm bounded away from 1, so along any coordinate where the program uses a non-identity group element the expectation contracts; pseudorandom restrictions with hashing are then used to reduce block products to width-one products with a small spill, which are handled by the width-one generators.

What would settle it

Check the eigenvalue condition in Definition 6 on the one-dimensional irreducible characters of the quaternion group $Q_8$: the nontrivial character that sends $-1$ to 1 gives $\rho(-1) = [1]$, so under the literal printed definition $Q_8$ is not mixing even though it is Dedekind. This would falsify the stated equivalence and the reduction's coverage of $Q_8$ unless the definition is weakened to non-identity matrices.

Watch

Extended reading notes

Core claim

The paper's central claim is that the bottleneck for non-commutative group programs is not non-commutativity itself but the prime structure of the group order. For a p-group $G$, a length-$n$ program computes $\prod_{i=1}^n g_i^{x_i}$, and Lemma 13 rewrites this as a tuple of constant-degree polynomials over $\mathbb{F}_p$. Combining that normal form with a sum-of-small-bias generator for low-degree polynomials and a derandomized biased-noise distribution gives an explicit generator of seed length $c_G \log(n/\varepsilon)$ that fools every such program in any order; the same generator also fools constant-width block products over p-groups. The paper further proves a reduction that lifts a width-one generator over a mixing group to block products over that group, yielding near-optimal generators for block products over commutative groups and over Dedekind 2-groups $G = Q_8 \times \mathbb{Z}_2^t$, and hence for read-once polynomials over any finite field. Finally, a representation-theoretic argument gives a generator for products over any mixing group with seed length $c_G \log(n/\varepsilon) \log(1/\varepsilon)$, which is optimal for constant error.

Load-bearing premise

The block-product and mixing-group results rest on the claimed equivalence between the representation-theoretic mixing condition and Dedekind groups; if that equivalence fails for a group like $Q_8 \times \mathbb{Z}_2^t$, the reduction does not apply to it.

Editorial extensions

If this is right

  • For every finite p-group, read-once group products in any input order are fooled by an explicit generator with optimal seed length $c_G \log(n/\varepsilon)$, and the same remains true for block products of constant width.
  • Read-once polynomials over any finite field now have near-optimal generators; this was previously known only over the two-element field.
  • For any mixing group, a good width-one generator automatically lifts to a generator for block products, so future progress on width-one products transfers to a much broader class of tests.
  • Over mixing groups such as $Q_8 \times \mathbb{Z}_2^t$, the new representation-theoretic generator reaches optimal seed length when the error is constant, improving the previous any-order bound for all groups.
  • The paper identifies composite-order groups, with $S_3$ as the natural next example, as the barrier separating its p-group results from all groups.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The derandomized-noise construction is an XOR of independent small-bias generators; because conditioning a small-bias distribution on few bits preserves bias, the construction may be usable as a drop-in component wherever a robust distribution over boolean inputs is needed.
  • If the mixing condition is read with the weaker requirement that no non-identity matrix $\rho(g)$ has eigenvalue 1, the reduction extends to groups with a small mixing subset that generates the group, such as the rotations of $S_3$, which would give heuristics for the composite-order obstacle without waiting for a composite-modulus PRG.
  • The $\theta$-mixing parameter suggests a quantitative tradeoff: for a group whose irreducible representations all have eigenvalues separated from 1 by $\theta$, the seed length should scale with $\log(1/\theta)$; computing this spectral gap for concrete groups would let one benchmark the constants in the generator.
  • A direct reduction from nilpotent groups to polynomials over composite moduli is sketched but not proved; making it explicit would reduce the whole non-commutative program problem to the composite-modulus polynomial problem the paper names as its main challenge.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies explicit pseudorandom generators for read-once group products and related models. Its headline result (Theorem 5) is a generator with optimal seed length c_G log(n/epsilon) for programs of length n over any finite p-group, in any order, obtained by encoding p-groups as low-degree polynomials, using biased bits, and derandomizing noise. The paper also proves a reduction (Theorem 10) that lifts generators for width-1 products with spill to generators for width-w block products over 'mixing groups', derives near-optimal generators for block products over quaternions and commutative groups (Corollary 11), including read-once polynomials modulo any fixed m, and gives a representation-theoretic generator for products over mixing groups (Theorem 12). A separate section proves a characterization of mixing groups as Dedekind groups (Lemma 9).

Significance. If the identified issues are repaired, this is a strong paper. Theorem 5 closes the gap between the previous Omega(log n log(1/epsilon)) lower bound and the information-theoretic optimum for every finite p-group, including non-commutative groups such as the quaternions, unitriangular groups, and wreath products. The block-product reduction and the resulting generators for read-once polynomials modulo composite m are substantial advances. The proofs are largely self-contained given the cited external machinery (Vio09b, GKM15/GKM18, NN93/AGHP92, FK18/LPV22); the dependencies are external but not circular. The representation-theoretic construction for mixing groups is conceptually novel and likely to influence future work. However, the paper as printed contains a load-bearing defect in the definition and characterization of mixing groups, which affects Theorems 10 and 12 and Corollary 11.

major comments (2)
  1. [Section 9, Claim 45] Definition 6 states that a group G is mixing if for every nontrivial irreducible representation rho and every non-identity element g, the matrix rho(g) has no eigenvalue 1. Under this literal reading, Lemma 9 is false: for Q8, the nontrivial linear character with kernel {+-1} maps -1 to the 1x1 matrix [1], and for Z2 x Z2, the character rho(1,0) = [1] is a counterexample. Both groups are Dedekind. Consequently Corollary 11's invocation of Theorem 10 for Q8 x Z2^t does not follow from the stated definition. The later proofs, including Claim 23 and Theorem 30, use only the weaker condition that rho(g) has no eigenvalue 1 whenever rho(g) is not the identity matrix. The definition and Lemma 9 should be revised to this weaker condition, which is the condition actually used, and the proof of Lemma 9 for that condition should be supplied.
  2. [Section 9] The converse direction of Lemma 9 is not proved as written. From the assumption that W_g = ker(rho(g)-I) is a subrepresentation, the claim infers that if v in W_g then rho(h^{-1}gh)v = v for all v in W_g, and then concludes that <h^{-1}gh> = <g>. This conclusion is unjustified: for elements g acting trivially on an irrep, W_g is the whole space and gives no separation. The argument needs a regular-representation or all-irreps consideration to conclude that h^{-1}gh lies in <g>. As printed, the proof of Lemma 9 is incomplete.
minor comments (5)
  1. [Remark 7] Remark 7 and the proof of Lemma 9 refer to 'Theorem 6' when they mean 'Definition 6'; this should be corrected throughout.
  2. [Lemma 13] The proof of Lemma 13 writes g := (g1, g1, ..., gn) in the theorem statement; the second entry should be g2.
  3. [Section 4] The text refers to 'Theorem 22' in the proof of Claim 23 and in Claim 37, but the relevant statement is Claim 22 in both cases. Several other internal references (e.g., 'Theorem 42' for Claim 42) have the same mismatch.
  4. [Section 8.2] Claim 42 is labeled as a claim but is cited as 'Theorem 42' in the proof of Theorem 30; the numbering and labels should be made consistent.
  5. [Throughout] The notation c_G and O_m is used informally at times; a short remark clarifying that these hide absolute constants depending only on the group would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the construction chain rests on external published PRGs and Fourier-growth theorems; the Definition 6/Lemma 9 flaw is a correctness gap, not a circular step.

full rationale

Walking the derivation chain: Theorem 5 reduces to Lemma 13 (polynomial representation, proved directly in the paper, with [PT01] cited only as background), Lemma 15 (the field-element generator from [Vio09b], an external published result), Corollary 17 (the biased-bit reduction from [LRTV09b, MZ09a], external), and Lemma 18 (which invokes Lemma 7.2 of [FK18] plus the Fourier-growth bound of [RSV13, LPV22]). None of these are restatements of the paper's own conclusions, and none is fitted to the paper's target quantities. Even where a cited result is co-authored by one of the present authors ([LPV22] contains Lee, and [Vio09b] contains Viola), it is a published theorem with its own proof and assumptions that do not include the present results; under the review rules that counts as independent support, not circularity. The lifting machinery in Theorems 10, 26 and 30 is built from [GKM15], [GKM18], [NN93, AGHP92], [FK18] and [LPV22] in the same external way, and Corollary 11 simply feeds Theorem 5 into Theorem 10 as a component, which is forward composition rather than circularity. No equation is shown to be identical to a previous one by construction, and no fitted parameter is relabeled as a prediction. The one genuinely problematic passage is Definition 6 with Lemma 9: under the literal wording, a nontrivial linear character of Q8 sends the non-identity element -1 to the 1x1 matrix [1], and similarly for Z2 x Z2, so Q8 and Z2 x Z2 are not 'mixing' as defined even though both are Dedekind, making Lemma 9 false as printed and requiring the weaker 'non-identity matrix' reading for Theorems 10, 12 and Corollary 11. That is a localized correctness bug in a characterization, not a circular equivalence; the flagship p-group result (Theorem 5) and its proof are independent of Definition 6, and I found no internal gap in that derivation.

Assumptions & free parameters 5 free parameters · 7 assumptions · 0 invented entities

The ledger contains no fitted parameters in the empirical sense; all listed numbers are hand-chosen constants that make tail bounds and Chernoff estimates close, and they are absorbable into the group-dependent constants c_G and c_m. The axioms are mostly standard external PRG technology. The two ad hoc entries are precisely where the paper is fragile: the operative (weak) mixing condition differs from the printed Definition 6, and Claim 45's normality inference is unproved. No new physical or mathematical entities are postulated; 'mixing groups', 'θ-mixing', and 'block products with spill' are defined classes, not invented objects.

free parameters (5)
  • Noise probability p = p = 2^{-C} (Thm 27); p = 2^{-23w}θ^3 (eq. 2)
    Hand-chosen so the tail bounds in Lemma 28 and the width-reduction probabilities in Claims 35, 38, 39 close. Not fitted to any data; absorbed into c_G.
  • Bias parameter δ = δ = (m·w)^{-k} (Thm 27); δ = θ^k (eq. 2)
    Set small enough that δ is dominated by the polynomial terms in equations (3)-(4) and Claim 38. Free choice; no data.
  • Long/short product thresholds = 2^{30w}θ^{-5} to 2^{45w}θ^{-5}; m^5·2^{30w} to m^5·2^{45w}
    Separate 'long' from 'short' products in Theorem 26/30 so that the bias estimates of Claim 33 and the restriction estimates of Claim 34 both hold with slack. Hand-chosen exponents.
  • Independence degrees k, ℓ', 5ℓ', 10ℓ' = k = C(log(1/ε) + w); ℓ' = c_G log(1/ε)
    Degrees of bounded independence for the hash families and noise distributions; chosen larger than the concentration needs require. Constants are free, not fitted.
  • Angle parameter θ = θ = 1/m in Definition 25; c_G from minimal eigen-angle in Thm 12
    For a finite group of order m, non-identity irrep matrices have eigenvalues at angle at least 2π/m ≥ 1/m by root-of-unity structure; group-dependent, not data-fitted.
assumptions (7)
  • domain assumption Lemma 13: p-group products are computable by degree-c_G polynomial maps over F_p (proven in-paper by induction using a normal subgroup of order p^{k-1})
    Foundation of Theorem 5. The proof is given; it builds on the known PT01 polynomialization.
  • domain assumption FK18 Lemma 7.2 / LPV22 Fourier growth: small-bias X plus noise N_p fools group products; extension from p=4 to any p is asserted 'immediate'
    Load-bearing for Theorem 5; cited, not re-proven in the text.
  • standard math Existence of (δ,k)-almost k-wise independent distributions with the stated seed lengths (NN93, AGHP92, Vad12 Cor 3.34)
    Used in Lemmas 27, 32, and the Theorem 12 construction.
  • domain assumption Vio09b polynomial generators over F_p (Lemma 15) and the biased-bits conversion (Corollary 17, from LRTV09b/MZ09a)
    External PRG results that derandomize N_p in Theorem 5.
  • domain assumption GKM18/GKM15 generator for modular sums with O(log(m/ε) polylog) seed (Lemma 43)
    Base PRG P1 for commutative groups in Theorem 10 and Corollary 11.
  • ad hoc to paper Weak mixing condition: every non-identity matrix ρ(g) in every irrep has no eigenvalue 1 (the intended reading of Definition 6)
    Definition 6 as printed states the strong condition; the proofs of Claims 22-23 and Theorem 26 need the weak version, and the text never reconciles the two.
  • ad hoc to paper Claim 45's inference: W_g ⊆ W_{h^{-1}gh} for all irreps implies ⟨h^{-1}gh⟩ = ⟨g⟩
    The stated proof of Lemma 9 depends on this step; as written it is unjustified without a regular-representation argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pseudorandom bits for non-commutative programs." pith.science (2026). https://pith.science/paper/UUMS6LXS

@misc{pith2026250601832,
  author       = {Pith},
  title        = {Pith review of: Pseudorandom bits for non-commutative programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UUMS6LXS}},
  note         = {Machine review of arXiv:2506.01832}
}
abstract

We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1. We consider read-once group-products over a finite group $G$, i.e., tests of the form $\prod_{i=1}^n g_i^{x_i}$ where $g_i\in G$, a special case of read-once permutation branching programs. We give generators with optimal seed length $c_G \log(n/\varepsilon)$ over any $p$-group. The proof uses the small-bias plus noise paradigm, but derandomizes the noise to avoid the recursion in previous work. Our generator works when the bits are read in any order. Previously for any non-commutative group the best seed length was $\ge\log n\log(1/\varepsilon)$, even for a fixed order. 2. We give a reduction that "lifts" suitable generators for group products over $G$ to a generator that fools width-$w$ block products, i.e., tests of the form $\prod g_i^{f_i}$ where the $f_i$ are arbitrary functions on disjoint blocks of $w$ bits. Block products generalize several previously studied classes. The reduction applies to groups that are mixing in a representation-theoretic sense that we identify. 3. Combining (2) with (1) and other works we obtain new generators for block products over the quaternions or over any commutative group, with nearly optimal seed length. In particular, we obtain generators for read-once polynomials modulo any fixed $m$ with nearly optimal seed length. Previously this was known only for $m=2$. 4. We give a new generator for products over "mixing groups." The construction departs from previous work and uses representation theory. For constant error, we obtain optimal seed length, improving on previous work (which applied to any group). This paper identifies a challenge in the area that is reminiscent of a roadblock in circuit complexity -- handling composite moduli -- and points to several classes of groups to be attacked next.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

54 extracted references · 52 canonical work pages

  1. [1]

    Simple constructions of almost k -wise independent random variables

    Noga Alon, Oded Goldreich, Johan H stad, and Ren \'e Peralta. Simple constructions of almost k -wise independent random variables. Random Structures & Algorithms , 3(3):289--304, 1992

    work page 1992

  2. [2]

    Cryptography in NC ^0

    Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC ^0 . SIAM J. on Computing , 36(4):845--888, 2006

    work page 2006

  3. [3]

    Semi-direct product in groups and zig-zag product in graphs: Connections and applications

    Noga Alon, Alexander Lubotzky, and Avi Wigderson. Semi-direct product in groups and zig-zag product in graphs: Connections and applications. In IEEE Symp. on Foundations of Computer Science (FOCS) , pages 630--637, 2001

    work page 2001

  4. [4]

    Saks, Avi Wigderson, and Shiyu Zhou

    Roy Armoni, Michael E. Saks, Avi Wigderson, and Shiyu Zhou. Discrepancy sets and pseudorandom generators for combinatorial rectangles. In 37th IEEE Symp. on Foundations of Computer Science (FOCS) , pages 412--421, 1996

    work page 1996

  5. [5]

    Deterministic simulation of probabilistic constant-depth circuits

    Miklos Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant-depth circuits. Advances in Computing Research - Randomness and Computation , 5:199--223, 1989

    work page 1989

  6. [6]

    Mix Barrington

    David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC ^1 . J. of Computer and System Sciences , 38(1):150--164, 1989

    work page 1989

  7. [7]

    Grochow, and Chris Umans

    Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, and Chris Umans. Which groups are amenable to proving exponent two for matrix multiplication? CoRR , abs/1712.02302, 2017

    arXiv 2017

  8. [8]

    Pseudorandom bits for polynomials

    Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. on Computing , 39(6):2464--2486, 2010

    work page 2010

Show all 54 references
  1. [9]

    Pseudorandom generators from polarizing random walks

    Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom generators from polarizing random walks. Theory Comput. , 15:1--26, 2019

    2019

  2. [10]

    Kleinberg, Bal \'a zs Szegedy, and Christopher Umans

    Henry Cohn, Robert D. Kleinberg, Bal \'a zs Szegedy, and Christopher Umans. Group-theoretic algorithms for matrix multiplication. In IEEE Symp. on Foundations of Computer Science (FOCS) , pages 379--388, 2005

    2005

  3. [11]

    Dummit and Richard M

    David S. Dummit and Richard M. Foote. Abstract Algebra . Wiley, 3rd edition, 2004

    2004

  4. [12]

    u cken, Germany (Virtual Conference) , volume 169 of LIPIcs , pages 6:1--6:36. Schloss Dagstuhl - Leibniz-Zentrum f \

    Dean Doron, Pooya Hatami, and William M. Hoza. Log-seed pseudorandom generators via iterated restrictions. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbr \" u cken, Germany (Virtual Conference) , volume 169 of LIPIcs , ...

    2020

  5. [13]

    Group representations in probability and statistics , volume 11 of Institute of Mathematical Statistics Lecture Notes---Monograph Series

    Persi Diaconis. Group representations in probability and statistics , volume 11 of Institute of Mathematical Statistics Lecture Notes---Monograph Series . Institute of Mathematical Statistics, Hayward, CA, 1988

    1988

  6. [14]

    Pseudorandomness, symmetry, smoothing: Ii, 2024

    Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, symmetry, smoothing: Ii, 2024

    2024

  7. [15]

    Boosting uniformity in quasirandom groups: fast and simple

    Harm Derksen, Chin Ho Lee, and Emanuele Viola. Boosting uniformity in quasirandom groups: fast and simple. In IEEE Symp. on Foundations of Computer Science (FOCS) , 2024

    2024

  8. [16]

    Forbes and Zander Kelley

    Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In IEEE Symp. on Foundations of Computer Science (FOCS) , 2018

    2018

  9. [17]

    Pseudorandomness via the discrete fourier transform

    Parikshit Gopalan, Daniel Kane, and Raghu Meka. Pseudorandomness via the discrete fourier transform. In IEEE Symp. on Foundations of Computer Science (FOCS) , pages 903--922, 2015

    2015

  10. [18]

    Kane, and Raghu Meka

    Parikshit Gopalan, Daniel M. Kane, and Raghu Meka. Pseudorandomness via the discrete F ourier transform. SIAM J. Comput. , 47(6):2451--2487, 2018

    2018

  11. [19]

    Better pseudorandom generators from milder pseudorandom restrictions

    Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In IEEE Symp. on Foundations of Computer Science (FOCS) , 2012

    2012

  12. [20]

    Pseudorandom generators for combinatorial shapes

    Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman. Pseudorandom generators for combinatorial shapes. SIAM J. Comput. , 42(3):1051--1076, 2013

    2013

  13. [21]

    W. T. Gowers. Generalizations of F ourier analysis, and how to apply them. Bull. Amer. Math. Soc. (N.S.) , 54(1):1--44, 2017

    2017

  14. [22]

    W. T. Gowers and Emanuele Viola. Mixing in non-quasirandom groups. In ACM Innovations in Theoretical Computer Science conf. (ITCS) , 2022

    2022

  15. [23]

    Paradigms for unconditional pseudorandom generators

    Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Foundations and Trends® in Theoretical Computer Science , 16(1-2):1--210, 2024

    2024

  16. [24]

    Bounded independence plus noise fools products

    Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput. , 47(2):493--523, 2018

    2018

  17. [25]

    Pseudorandom generators for group products: extended abstract

    Michal Kouck \' y , Prajakta Nimbhorkar, and Pavel Pudl \' a k. Pseudorandom generators for group products: extended abstract. In STOC , pages 263--272. ACM , 2011

    2011

  18. [26]

    Jack B. Kuipers. Quaternions in computer graphics and robotics. In SIGGRAPH 2002 Course Notes , San Antonio, TX, 2002. ACM SIGGRAPH

    2002

  19. [27]

    Fourier bounds and pseudorandom generators for product tests

    Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In 34th C omputational C omplexity C onference , volume 137. 2019

    2019

  20. [28]

    Pseudorandom generators for CC^0[p] and the F ourier spectrum of low-degree polynomials over finite fields

    Shachar Lovett, Partha Mukhopadhyay, and Amir Shpilka. Pseudorandom generators for CC^0[p] and the F ourier spectrum of low-degree polynomials over finite fields. In 51th IEEE Symp. on Foundations of Computer Science (FOCS) . IEEE, 2010

    2010

  21. [29]

    Unconditional pseudorandom generators for low degree polynomials

    Shachar Lovett. Unconditional pseudorandom generators for low degree polynomials. Theory of Computing , 5(1):69--82, 2009

    2009

  22. [30]

    Fourier growth of regular branching programs

    Chin Ho Lee, Edward Pyne, and Salil Vadhan. Fourier growth of regular branching programs. In Approximation, randomization, and combinatorial optimization. A lgorithms and techniques , volume 245 of LIPIcs. Leibniz Int. Proc. Inform. , pages Art. No. 2, 21. Schloss Dagstuhl. Le...

    2022

  23. [31]

    Pseudorandom bit generators that fool modular sums

    Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom bit generators that fool modular sums. In Approximation, randomization, and combinatorial optimization , volume 5687 of Lecture Notes in Comput. Sci. , pages 615--630. Springer, Berlin, 2009

    2009

  24. [32]

    Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Pseudorandom bit generators that fool modular sums. In 13th Workshop on Randomization and Computation (RANDOM) , volume 5687 of Lecture Notes in Computer Science , pages 615--630. Springer, 2009

    2009

  25. [33]

    Improved pseudorandom generators for combinatorial rectangles

    Chi-Jen Lu. Improved pseudorandom generators for combinatorial rectangles. Combinatorica , 22(3):417--433, 2002

    2002

  26. [34]

    The coin problem for product tests

    Chin Ho Lee and Emanuele Viola. The coin problem for product tests. ACM Trans. Comput. Theory , 10(3):Art. 14, 10, 2018

    2018

  27. [35]

    More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

    Chin Ho Lee and Emanuele Viola. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Theory of Computing , 16:1--50, 2020. Available at http://www.ccs.neu.edu/home/viola/

    2020

  28. [36]

    More on bounded independence plus noise: pseudorandom generators for read-once polynomials

    Chin Ho Lee and Emanuele Viola. More on bounded independence plus noise: pseudorandom generators for read-once polynomials. Theory Comput. , 16:Paper No. 7, 50, 2020

    2020

  29. [37]

    Pseudorandom generators for width-3 branching programs

    Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Moses Charikar and Edith Cohen, editors, ACM Symp. on the Theory of Computing (STOC) , pages 626--637. ACM , 2019

    2019

  30. [38]

    Pseudorandom generators for width-3 branching programs

    Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In S TOC '19--- P roceedings of the 51st A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 626--637. ACM, New York, 2019

    2019

  31. [39]

    Small-bias spaces for group products

    Raghu Meka and David Zuckerman. Small-bias spaces for group products. In 13th Workshop on Randomization and Computation (RANDOM) , volume 5687 of Lecture Notes in Computer Science , pages 658--672. Springer, 2009

    2009

  32. [40]

    Small-bias spaces for group products

    Raghu Meka and David Zuckerman. Small-bias spaces for group products. In Approximation, randomization, and combinatorial optimization , volume 5687 of Lecture Notes in Comput. Sci. , pages 658--672. Springer, Berlin, 2009

    2009

  33. [41]

    Naor and M

    J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications. In 22nd ACM Symp. on the Theory of Computing (STOC) , pages 213--223. ACM, 1990

    1990

  34. [42]

    Small-bias probability spaces: efficient constructions and applications

    Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing , 22(4):838--856, 1993

    1993

  35. [43]

    sur les langages reconnus par des groupes nilpotents

    Pierre P \' e ladeau and Denis Th \' e rien. On the languages recognized by nilpotent groups (a translation of "sur les langages reconnus par des groupes nilpotents"). Electron. Colloquium Comput. Complex. , TR01-040 , 2001

    2001

  36. [44]

    Omer Reingold, Thomas Steinke, and Salil P. Vadhan. Pseudorandomness for regular branching programs via F ourier analysis. In Workshop on Randomization and Computation (RANDOM) , pages 655--670, 2013

    2013

  37. [45]

    Iterative construction of cayley expander graphs

    Eyal Rozenman, Aner Shalev, and Avi Wigderson. Iterative construction of cayley expander graphs. Theory Comput. , 2(5):91--120, 2006

    2006

  38. [46]

    Linear Representations of Finite Groups

    Jean Pierre Serre. Linear Representations of Finite Groups . Springer, 1977

    1977

  39. [47]

    Pseudorandomness for permutation branching programs without the group theory

    Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. Electron. Colloquium Comput. Complex. , TR12-083 , 2012

    2012

  40. [48]

    Faster isomorphism for p-groups of class 2 and exponent p

    Xiaorui Sun. Faster isomorphism for p-groups of class 2 and exponent p. In STOC , pages 433--440. ACM , 2023

    2023

  41. [49]

    Fourier analysis on finite groups and applications , volume 43 of London Mathematical Society Student Texts

    Audrey Terras. Fourier analysis on finite groups and applications , volume 43 of London Mathematical Society Student Texts . Cambridge University Press, Cambridge, 1999

    1999

  42. [50]

    Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science , 7(1-3):1--336, 2012

    2012

  43. [51]

    On the power of small-depth computation

    Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science , 5(1):1--72, 2009

    2009

  44. [52]

    The sum of d small-bias generators fools polynomials of degree d

    Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d . Computational Complexity , 18(2):209--217, 2009

    2009

  45. [53]

    Pseudorandom generators for combinatorial checkerboards

    Thomas Watson. Pseudorandom generators for combinatorial checkerboards. Computational Complexity , 22(4):727--769, 2013

    2013

  46. [54]

    Representation theory of finite groups, and applications

    Avi Wigderson. Representation theory of finite groups, and applications. Available at http://www.math.ias.edu/ avi/TALKS/Green \_ Wigderson \_ lecture.pdf, 2010

    2010

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.