Explicit two-source extractors and resilient functions (Q2320598)

Given 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.