Randomness-E-cient Sampling within NC 1

Le résumé fourni par la source

We construct a randomness-e‐cient averaging sampler that is computable by uniform constantdepth circuits with parity gates (i.e., in uniform AC 0 [']). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC 1 . For example, we obtain the following results: † Randomness-e‐cient error-reduction for uniform probabilistic NC 1 ;TC 0 ;AC 0 ['] and AC 0 : Any function computable by uniform probabilistic circuits with error 1=3 using r random bits is computable by circuits of the same type with error ‐ using r + O(log(1=‐)) random bits. † An optimal bitwise †-biased generator in AC 0 [']: There exists a 1=2 ›(n) -biased generator G : f0;1g O(n) ! f0;1g 2 n for which poly(n)-size uniform AC 0 ['] circuits can compute G(s)i given (s;i) 2 f0;1g O(n) £ f0;1g n . This resolves a question raised by Gutfreund and Viola (Random 2004). † uniform BP ¢ AC 0 µ uniform AC 0 =O(n). Our sampler is based on the zig-zag graph product of Reingold, Vadhan and Wigderson (Annals of Math 2002) and as part of our analysis we give an elementary proof of a generalization of Gillman’s Chernofi Bound for Expander Walks (FOCS 1994).

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.