zbMATH — the first resource for mathematics

Extractors from Reed-Muller codes. (English) Zbl 1094.68036
Summary: Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, researchers had failed to build extractors directly from a good code without using other tools from pseudorandomness. We succeed in constructing an extractor directly from a Reed-Muller code. To do this, we develop a novel proof technique. Furthermore, our construction is the first to achieve degree close to linear. In contrast, the best previous constructions brought the log of the degree within a constant of optimal, which gives polynomial degree. This improvement is important for certain applications. For example, it was used [E. Mossel and C. Umans, “On the complexity of approximating the VC dimension”, J. Comput. Syst. Sci. 65, 660–671 (2002; Zbl 1059.68049)] to show that approximating VC dimension to within a factor of $$N^{1 - \delta }$$ is AM-hard for any positive $$\delta$$ .

MSC:
 94B27 Geometric methods (including applications of algebraic geometry) applied to coding theory 68W99 Algorithms in computer science
Full Text:
References:
 [1] Mossel, E.; Umans, C., On the complexity of approximating the VC dimension, J. comput. system sci., 65, 660-671, (2002) · Zbl 1059.68049 [2] Sipser, M., Expanders, randomness, or time vs. space, J. comput. system sci., 36, 379-383, (1988) · Zbl 0652.68050 [3] Santha, M., On using deterministic functions in probabilistic algorithms, Inform. and comput., 74, 3, 241-249, (1987) · Zbl 0629.68047 [4] Nisan, N.; Zuckerman, D., Randomness is linear in space, J. comput. system sci., 52, 1, 43-52, (1996) · Zbl 0846.68041 [5] D. Zuckerman, General weak random sources, in: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 534-543 [6] Zuckerman, D., Simulating BPP using a general weak random source, Algorithmica, 16, 367-391, (1996) · Zbl 0857.68121 [7] Srinivasan, A.; Zuckerman, D., Computing with very weak random sources, SIAM J. comput., 28, 1433-1459, (1999) · Zbl 0932.60008 [8] A. Ta-Shma, On extracting randomness from weak random sources, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 276-285 · Zbl 0924.68210 [9] Zuckerman, D., Randomness-optimal oblivious sampling, Random structures algorithms, 11, 345-367, (1997) · Zbl 0891.60100 [10] Trevisan, L., Extractors and pseudorandom generators, J. ACM, 48, 4, 860-879, (2001) · Zbl 1127.68403 [11] Nisan, N.; Wigderson, A., Hardness vs. randomness, J. comput. system sci., 49, 149-167, (1994) · Zbl 0821.68057 [12] R. Impagliazzo, R. Shaltiel, A. Wigderson, Near-optimal conversion of hardness into pseudo-randomness, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 181-190 [13] R. Impagliazzo, R. Shaltiel, A. Wigderson, Extractors and pseudo-random generators with optimal seed length, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 1-10 · Zbl 1296.65007 [14] O. Reingold, R. Shaltiel, A. Wigderson, Extracting randomness via repeated condensing, in: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 22-31 · Zbl 1100.68030 [15] A. Ta-Shma, C. Umans, D. Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, in: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 143-152 · Zbl 1323.68263 [16] Radhakrishnan, J.; Ta-Shma, A., Bounds for dispersers, extractors, and depth-two superconcentrators, SIAM J. discrete math., 13, 1, 2-24, (2000) · Zbl 1023.94025 [17] Wigderson, A.; Zuckerman, D., Expanders that beat the eigenvalue bound: explicit construction and applications, Combinatorica, 19, 1, 125-138, (1999) · Zbl 0929.05075 [18] C. Umans, Hardness of approximating $$\Sigma_2^p$$ minimization problems, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 465-474 [19] Russell, A.; Zuckerman, D., Perfect-information leader election in $$\log^\ast n + O(1)$$ rounds, J. comput. system sci., 63, 612-626, (2001) · Zbl 1006.68012 [20] O. Goldreich, D. Zuckerman, Another proof that BPP ⊆ PH (and more), Technical report TR97-045, Electronic Colloquium on Computational Complexity, 1997 [21] Ta-Shma, A.; Zuckerman, D., Extractor codes, IEEE trans. inform. theory, 50, 3015-3025, (2004) · Zbl 1298.94148 [22] Håstad, J., Clique is hard to approximate within $$n^{1 - \operatorname{\&z.epsi;}}$$, Acta math., 182, 105-142, (1999) · Zbl 0989.68060 [23] V. Guruswami, Better extractors for better codes?, in: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 436-444 · Zbl 1192.68363 [24] D. Zuckerman, Linear degree extractors and inapproximability, manuscript, 2005 [25] R. Shaltiel, C. Umans, Simple extractors for all min-entropies and a new pseudo-random generator, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 648-657 [26] C. Umans, Pseudo-random generators for all hardnesses, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 627-634 · Zbl 1192.68863 [27] M. Sudan, L. Trevisan, S. Vadhan, Pseudorandom generators without the XOR lemma, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 537-546 · Zbl 1345.68138 [28] Sudan, M., Decoding of Reed Solomon codes beyond the error-correction bound, J. complexity, 13, 180-193, (1997) · Zbl 0872.68026 [29] Guruswami, V.; Hastad, J.; Sudan, M.; Zuckerman, D., Combinatorial bounds for List decoding, IEEE trans. inform. theory, 48, 1021-1034, (2002) · Zbl 1061.94074 [30] Naor, J.; Naor, M., Small-bias probability spaces: efficient constructions and applications, SIAM J. comput., 22, 4, 838-856, (1993) · Zbl 0776.60014 [31] Alon, N.; Goldreich, O.; Håstad, J.; Peralta, R., Simple constructions of almost k-wise independent random variables, Random structures algorithms, 3, 3, 289-303, (1992) · Zbl 0755.60002 [32] Santha, M.; Vazirani, U.V., Generating quasi-random sequences from semi-random sources, J. comput. system sci., 33, 75-87, (1986) · Zbl 0612.94004 [33] Chor, B.; Goldreich, O., Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM J. comput., 17, 2, 230-261, (1988) · Zbl 0644.94008 [34] R. Raz, O. Reingold, S. Vadhan, Extracting all the randomness and reducing the error in Trevisan’s extractors, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 149-158 · Zbl 1345.68136
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.