Explicit two-source extractors and resilient functions.

*(English)*Zbl 1419.05109Given a positive integer \(k\) and a positive real number \(\varepsilon\), let \(K = 2^{k}\). A (balanced) bipartite graph containing \(N\) “left” vertices and \(N\) “right” vertices is called a \((k, \varepsilon)\)-two-source extractor if every subgraph with \(K\) left vertices and \(K\) right vertices contains \((1/2 \pm \varepsilon)K^{2}\) edges.

The main result of this work is the following.

Theorem 1. There is a positive constant \(C\) such that for any natural number \(n\), there is an explicit construction of a \((k, \varepsilon)\)-two-source extractor on two sets of \(2^{n}\) vertices with \(k = \log^{C}(n/\varepsilon)\). The construction is explicit in the sense that there is an algorithm which runs in polynomial time \(\mathrm{poly}(n/\varepsilon)\) that determines whether there is an edge between two nodes.

This result is applied in the proof of the following result.

Theorem 2. There is a positive constant \(C\) such that for any natural number \(n\), there is an explicit construction of bipartite \(K\)-Ramsey graphs on \(2N\) vertices and a Ramsey graph on \(N\) vertices where \(N = 2^{n}\) and \(K = 2^{(\log \log N)^{C}}\).

The proof utilizes a variety of tools from the theory of extractors and probability along with two technical “key lemmas”. The proof of the main result is completed by first using non-malleable extractors to reduce the construction of a two-source extractor to the problem of constructing resilient functions. Such a function is constructed to be computable by a polynomial sized constant depth monotone circuit.

The main result of this work is the following.

Theorem 1. There is a positive constant \(C\) such that for any natural number \(n\), there is an explicit construction of a \((k, \varepsilon)\)-two-source extractor on two sets of \(2^{n}\) vertices with \(k = \log^{C}(n/\varepsilon)\). The construction is explicit in the sense that there is an algorithm which runs in polynomial time \(\mathrm{poly}(n/\varepsilon)\) that determines whether there is an edge between two nodes.

This result is applied in the proof of the following result.

Theorem 2. There is a positive constant \(C\) such that for any natural number \(n\), there is an explicit construction of bipartite \(K\)-Ramsey graphs on \(2N\) vertices and a Ramsey graph on \(N\) vertices where \(N = 2^{n}\) and \(K = 2^{(\log \log N)^{C}}\).

The proof utilizes a variety of tools from the theory of extractors and probability along with two technical “key lemmas”. The proof of the main result is completed by first using non-malleable extractors to reduce the construction of a two-source extractor to the problem of constructing resilient functions. Such a function is constructed to be computable by a polynomial sized constant depth monotone circuit.

Reviewer: Colton Magnant (Morrow)

PDF
BibTeX
XML
Cite

\textit{E. Chattopadhyay} and \textit{D. Zuckerman}, Ann. Math. (2) 189, No. 3, 653--705 (2019; Zbl 1419.05109)

Full Text:
DOI

##### References:

[1] | Ajtai, Mikl\'os; Linial, Nathal, The influence of large coalitions, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 13, 129-145, (1993) · Zbl 0807.90148 |

[2] | Alon, Noga, The Shannon capacity of a union, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 18, 301-310, (1998) · Zbl 0921.05039 |

[3] | Alon, Noga; Goldreich, Oded; Mansour, Yishay, Almost \(k\)-wise independence versus \(k\)-wise independence, Inform. Process. Lett.. Information Processing Letters, 88, 107-110, (2003) · Zbl 1178.68251 |

[4] | Alon, Noga; Spencer, Joel H., The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, xvi+254 pp., (1992) · Zbl 0767.05001 |

[5] | Arora, Sanjeev; Barak, Boaz, Computational Complexity. A Modern Approach, xxiv+579 pp., (2009) · Zbl 1193.68112 |

[6] | Barak, Boaz, A Simple Explicit Construction of an \(n^{\tilde{O}(\log n)}\)-Ramsey graph, (2006) |

[7] | Barak, Boaz; Halevi, S., A model and architecture for pseudo-random generation with applications to /dev/random. Proceedings of the 12th ACM Conference on Computer and Communications Security, 203-212, (2005) |

[8] | Barak, Boaz; Impagliazzo, Russell; Wigderson, Avi, Extracting randomness using few independent sources, SIAM J. Comput.. SIAM Journal on Computing, 36, 1095-1118, (2006) · Zbl 1127.68030 |

[9] | Barak, Boaz; Kindler, G.; Shaltiel, R.; Sudakov, B.; Wigderson, A., Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors, J. ACM. Journal of the ACM, 57, 20-52, (2010) · Zbl 1327.68172 |

[10] | Barak, Boaz; Rao, Anup; Shaltiel, Ronen; Wigderson, Avi, 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction, Ann. of Math. (2). Annals of Mathematics. Second Series, 176, 1483-1543, (2012) · Zbl 1256.05146 |

[11] | Ben-Aroya, A.; Cohen, G.; Doron, D.; Ta-Shma, A., Two-source condensers with low error and small entropy gap via entropy-resilient functions, Electronic Colloq. Computational Complexity (ECCC), 25, 66 pp., (2018) |

[12] | Ben-Aroya, Avraham; Doron, Dean; Ta-Shma, Amnon, An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 1185-1194, (2017) · Zbl 1370.68082 |

[13] | Ben-Aroya, Avraham; Doron, Dean; Ta-Shma, Amnon, Near-optimal strong dispersers, erasure list-decodable codes and friends, Electron. Colloq. Computational Complexity (ECCC), 25, 65 pp., (2018) |

[14] | Ben-Aroya, Avraham; Linial, N., Collective coin flipping, robust voting schemes and minima of Banzhaf values. 26th Annual Symposium on Foundations of Computer Science, 408-416, (1985) |

[15] | Boppona, Ravi; Spencer, Joel, A useful elementary correlation inequality, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 50, 305-307, (1989) · Zbl 0663.60007 |

[16] | Bourgain, J., More on the sum-product phenomenon in prime fields and its applications, Int. J. Number Theory. International Journal of Number Theory, 1, 1-32, (2005) · Zbl 1173.11310 |

[17] | Braverman, Mark, Polylogarithmic independence fools \({\rm AC}^0\) circuits, J. ACM. Journal of the ACM, 57, 28-10, (2010) · Zbl 1327.68108 |

[18] | Chattopadhyay, Eshan; Goyal, Vipul; Li, Xin, Non-malleable extractors and codes, with their many tampered extensions. STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 285-298, (2016) · Zbl 1377.94042 |

[19] | Chattopadhyay, Eshan; Li, Xin, Explicit non-malleable extractors, multi-source extractors and almost optimal privacy amplification protocols. 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, 158-167, (2016) |

[20] | Chattopadhyay, Eshan; Li, Xin, Extractors for sumset sources. STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 299-311, (2016) · Zbl 1377.94014 |

[21] | Chor, Benny; Goldreich, Oded, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM J. Comput.. SIAM Journal on Computing, 17, Special issue on cryptography, 230-261, (1988) · Zbl 0644.94008 |

[22] | Cohen, Gil, Local correlation breakers and applications to three-source extractors and mergers. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, 845-862, (2015) |

[23] | Cohen, Gil, Making the most of advice: new correlation breakers and their applications. 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, 188-196, (2016) |

[24] | Cohen, Gil, Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 278-284, (2016) · Zbl 1376.05086 |

[25] | Cohen, Gil, Towards optimal two-source extractors and Ramsey graphs. STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 1157-1170, (2017) · Zbl 1370.68084 |

[26] | Cohen, Gil; Raz, Ran; Segev, Gil, Nonmalleable extractors with short seeds and applications to privacy amplification, SIAM J. Comput.. SIAM Journal on Computing, 43, 450-476, (2014) · Zbl 1302.94040 |

[27] | Dodis, Yevgeniy; Oliveira, Roberto, On extracting private randomness over a public channel. Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci., 2764, 252-263, (2003) · Zbl 1279.68350 |

[28] | Dodis, Yevgeniy; Li, Xin; Wooley, Trevor D.; Zuckerman, David, Privacy amplification and nonmalleable extractors via character sums, SIAM J. Comput.. SIAM Journal on Computing, 43, 800-830, (2014) · Zbl 1302.94043 |

[29] | Dodis, Yevgeniy; Wichs, Daniel, Non-malleable extractors and symmetric key cryptography from weak secrets. STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, 601-610, (2009) · Zbl 1304.94048 |

[30] | Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu, Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, 181-190, (2009) · Zbl 1292.68119 |

[31] | Erd\Hos, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53, 292-294, (1947) · Zbl 0032.19203 |

[32] | Feige, U., Noncryptographic selection protocols. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 142-153, (1999) |

[33] | Frankl, P.; Wilson, R. M., Intersection theorems with geometric consequences, Combinatorica. Combinatorica. An International Journal of the J\'anos Bolyai Mathematical Society, 1, 357-368, (1981) · Zbl 0498.05048 |

[34] | Gabizon, Ariel; Raz, Ran; Shaltiel, Ronen, Deterministic extractors for bit-fixing sources by obtaining an independent seed, SIAM J. Comput.. SIAM Journal on Computing, 36, 1072-1094, (2006) · Zbl 1118.68096 |

[35] | Goldwasser, S.; Sudan, M.; Vaikuntanathan, V., Distributed computing with imperfect randomness. Proceedings of the 19th International Symposium on Distributed Computing DISC 2005, Lect. Notes Comput. Sci., 3724, 288-302, (2005) · Zbl 1171.68860 |

[36] | Gopalan, Parikshit, Constructing Ramsey graphs from Boolean function representations, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 34, 173-206, (2014) · Zbl 1349.05230 |

[37] | Grolmusz, Vince, Low rank co-diagonal matrices and Ramsey graphs, Electron. J. Combin.. Electronic Journal of Combinatorics, http://www.combinatorics.org/Volume_7/Abstracts/v7i1r15.html, 15-7, (2000) · Zbl 0939.05060 |

[38] | Guruswami, Venkatesan; Umans, Christopher; Vadhan, Salil, Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, J. ACM. Journal of the ACM, 56, 20-34, (2009) · Zbl 1325.68169 |

[39] | Janson, Svante, Poisson approximation for large deviations, Random Structures Algorithms. Random Structures & Algorithms, 1, 221-229, (1990) · Zbl 0747.05079 |

[40] | Jun, B.; Kocher, P., The Intel random number generator, Cryptography Research Inc. white paper, (1999) |

[41] | Kahn, J.; Kalai, G.; Linial, N., The influence of variables on Boolean functions (extended abstract). The 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, 68-80, (1988) |

[42] | Kalai, Yael Tauman; Li, Xin; Rao, Anup, 2-source extractors under computational assumptions and cryptography with defective randomness. 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, 617-626, (2009) · Zbl 1292.94088 |

[43] | Kalai, Yael Tauman; Li, Xin; Rao, Anup; Zuckerman, D., Network extractor protocols. Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 654-663, (2008) |

[44] | Li, Xin, Improved constructions of three source extractors. 26th Annual IEEE Conference on Computational Complexity, 126-136, (2011) |

[45] | Li, Xin, Design extractors, non-malleable condensers and privacy amplification. STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, 837-854, (2012) · Zbl 1286.94077 |

[46] | Li, Xin, Non-malleable extractors, two-source extractors and privacy amplification. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, 688-697, (2012) |

[47] | Li, Xin, Extractors for a constant number of independent sources with polylogarithmic min-entropy. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, 100-109, (2013) |

[48] | Li, Xin, New independent source extractors with exponential improvement. STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, 783-792, (2013) · Zbl 1293.68059 |

[49] | Li, Xin, Three-source extractors for polylogarithmic min-entropy. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, 863-882, (2015) |

[50] | Li, Xin, Improved two-source extractors, and affine extractors for polylogarithmic entropy. 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, 168-177, (2016) |

[51] | Li, Xin, Improved non-malleable extractors, non-malleable codes and independent source extractors. STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 1144-1156, (2017) · Zbl 1370.94527 |

[52] | Li, Xin, Non-malleable extractors and non-malleable codes: Partially optimal constructions, (2018) |

[53] | Lu, Chi-Jen; Reingold, Omer; Vadhan, Salil; Wigderson, Avi, Extractors: optimal up to constant factors. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, 602-611, (2003) · Zbl 1192.68859 |

[54] | Meka, Raghu, Explicit Coin Flipping Protocols, (2009) |

[55] | Meka, Raghu, Explicit resilient functions matching Ajtai-Linial. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1132-1148, (2017) · Zbl 1410.68262 |

[56] | Nisan, Noam; Zuckerman, David, Randomness is linear in space, J. Comput. System Sci.. Journal of Computer and System Sciences, 52, 43-52, (1996) · Zbl 0846.68041 |

[57] | Pudl\'ak, Pavel; R\"odl, Vojt\vech, Pseudorandom sets and explicit constructions of Ramsey graphs. Complexity of Computations and Proofs, Quad. Mat., 13, 327-346, (2004) · Zbl 1074.05088 |

[58] | Ramsey, F. P., On a Problem of Formal Logic, Proc. London Math. Soc. (2). Proceedings of the London Mathematical Society. Second Series, 30, 264-286, (1929) · JFM 55.0032.04 |

[59] | Rao, Anup, Extractors for a constant number of polynomially small min-entropy independent sources, SIAM J. Comput.. SIAM Journal on Computing, 39, 168-194, (2009) · Zbl 1185.68453 |

[60] | Rao, Anup, Extractors for low-weight affine sources. 24th Annual IEEE Conference on Computational Complexity, 95-101, (2009) |

[61] | Rao, Anup; Zuckerman, D., Extractors for three uneven-length sources. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, 5171, 557-570, (2008) · Zbl 1159.68654 |

[62] | Raz, Ran, Extractors with weak random seeds. STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 11-20, (2005) · Zbl 1192.68373 |

[63] | Raz, Ran; Reingold, Omer; Vadhan, Salil, Extracting all the randomness and reducing the error in Trevisan’s extractors, J. Comput. System Sci.. Journal of Computer and System Sciences, 65, Special issue on STOC, 1999 (Atlanta, GA), 97-128, (2002) · Zbl 1020.68029 |

[64] | Russell, Alexander; Zuckerman, David, Perfect information leader election in \({\rm log}^\ast n+O(1)\) rounds, J. Comput. System Sci.. Journal of Computer and System Sciences, 63, Special issue on FOCS 98 (Palo Alto, CA), 612-626, (2001) · Zbl 1006.68012 |

[65] | S\'antha, Mikl\'os; Vazirani, Umesh V., Generating quasi-random sequences from semi-random sources, J. Comput. System Sci.. Journal of Computer and System Sciences, 33, 75-87, (1986) · Zbl 0612.94004 |

[66] | Shaltiel, Ronen, Recent developments in explicit constructions of extractors, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS. Bulletin of the European Association for Theoretical Computer Science. EATCS, 67-95, (2002) · Zbl 1051.68070 |

[67] | Shaltiel, Ronen, How to get more mileage from randomness extractors, Random Structures Algorithms. Random Structures & Algorithms, 33, 157-186, (2008) · Zbl 1181.68170 |

[68] | Sipser, Michael, Expanders, randomness, or time versus space, J. Comput. System Sci.. Journal of Computer and System Sciences, 36, 379-383, (1988) · Zbl 0652.68050 |

[69] | Tal, Avishay, Tight bounds on the Fourier spectrum of \({\bf{AC}}^\textbf{0}\). 32nd Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., 79, 15-31, (2017) |

[70] | Trevisan, Luca, Extractors and pseudorandom generators, J. ACM. Journal of the ACM, 48, 860-879, (2001) · Zbl 1127.68403 |

[71] | Viola, Emanuele, Extractors for circuit sources, SIAM J. Comput.. SIAM Journal on Computing, 43, 655-672, (2014) · Zbl 1301.68195 |

[72] | Zuckerman, David, Randomness-optimal oblivious sampling. Proceedings of the Workshop on Randomized Algorithms and Computation, Random Structures Algorithms. Random Structures & Algorithms, 11, 345-367, (1997) · Zbl 0891.60100 |

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.