Abstract
We study the complexity of computing k-wise independent and ε-biased generators G : {0, 1}n → {0, 1}m. Specifically, we refer to the complexity of computing Gexplicitly, i.e. given x ∈ {0, 1}n and i ∈ {0, 1}log m computing the i-th output bit of G(x). [MNT90] show that constant depth circuits of size poly(n) cannot explicitly compute k-wise independent and ε-biased generators with seed length \(n \leq 2^{\log^{o(1)} m}\).
In this work we show that DLOGTIME-uniform constant depth circuits of size poly(n) with parity gates can explicitly compute k-wise independent and ε-biased generators with seed length n roughly \(\log m \ll 2^{\log^{o(1)} m}\). In some cases the seed length of our generators is optimal up to constant factors, and in general up to polynomial factors. To obtain our results, we show a new construction of combinatorial designs, and we also show how to compute, in DLOGTIME-uniform AC 0, random walks of length logc n over certain expander graphs of size 2n.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, M., Allender, E., Impagliazzo, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. Comput. Complexity 10(2), 117–138 (2001)
Alon, N., Babai, L., Itai, A.: A fast and simple randomized algorithm for the maximal independent set problem. J. of algorithms 7, 567–583 (1986)
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures Algorithms 3(3), 289–304 (1992)
Ajtai, M.: Approximate counting with uniform constant-depth circuits. In: Advances in computational complexity theory, New Brunswick, NJ,1990 pp. 1–20 (1990) Amer. Math. Soc. Providence, RI.
Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC 1. J. Comput. System Sci. 41(3), 274–306 (1990)
Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform nc1. RAIRO Theoretical Informatics and Applications 35, 259–276 (2001)
Chor, B., Goldreich, O.: On the power of two-point based sampling. Journal of Complexity 5(1), 96–106 (1989)
Chor, B., Goldreich, O., Hastad, J., Friedman, J., Rudich, S., Smolensky, R.: The bit extraction problem and t-resilient functions. In: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, October 21–23, pp. 396–407. IEEE, Los Alamitos (1985)
Gabber, O., Galil, Z.: Explicit constructions of linear size superconcentrators. JCSS 22, 407–420 (1981)
Goldreich, O.: Modern cryptography, probabilistic proofs and pseudorandomness. Algorithms and Combinatorics, vol. 17, Springer, Berlin (1999)
Hartman, T., Raz, R.: On the distribution of the number of roots of polynomials and explicit weak designs. Random Structures & Algorithms 23(3), 235–263 (2003)
Jimbo, S., Maruoka, A.: Expanders obtained from affine transformations. Combinatorica 7(4), 343–355 (1987)
Margulis, G.A.: Explicit construction of concentrator. Problems Inform. Transmission 9, 325–332 (1973)
Mansour, Y., Nisan, N., Tiwari, P.: The computational complexity of universal hashing. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 14-16, pp. 235–243. ACM Press, New York (1990)
Nepomnjščiĭ, V.A.: Rudimentary predicates and turing calculations. Soviet it Mathematics-Doklady 11(6), 1462–1465 (1970)
Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: Proceedings of the Twenty-Second Annual ACM Symposium on the Theory of Computing, pp. 213–223 (1990)
Nisan, N., Wigderson, A.: Hardness vs randomness. Journal of Computer and System Sciences 49(2), 149–167 (1994)
Sipser, M., Spielman, D.A.: Expander codes. IEEE Trans. Inform. Theory 42, 1710–1722 (1996)
Viola, E.: The complexity of constructing pseudorandom generators from hard functions. Technical Report TR04-020, Electronic Colloquium on Computational Complexity (2004), http://www.eccc.uni-trier.de/eccc to appear in Journal of Computational Complexity
van Lint, J.H.: Introduction to coding theory. Graduate Texts in Mathematics, 3rd edn., vol. 86. Springer, Berlin (1999)
Vollmer, H.: Introduction to circuit complexity. Springer, Berlin (1999)
Goldreich, O., Bar-Yossef, Z., Wigderson, A.: Deterministic amplification of space bounded probabilistic algorithms. In: Proceedings of the 14nd Annual IEEE Conference on Computational Complexity, pp. 188–198 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gutfreund, D., Viola, E. (2004). Fooling Parity Tests with Parity Gates. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2004 2004. Lecture Notes in Computer Science, vol 3122. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27821-4_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-27821-4_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22894-3
Online ISBN: 978-3-540-27821-4
eBook Packages: Springer Book Archive