Abstract
Let V ⊆ [n] be a k-element subset of [n]. The uniform distribution on the 2k strings from {0, 1}n that are set to zero outside of V is called an (n, k)-zero-fixing source. An ϵ-extractor for (n, k)-zero-fixing sources is a mapping F: {0, 1}n → {0, 1}m, for some m, such that F(X) is ϵ-close in statistical distance to the uniform distribution on {0, 1}m for every (n, k)-zero-fixing source X. Zero-fixing sources were introduced by Cohen and Shinkar in [7] in connection with the previously studied extractors for bit-fixing sources. They constructed, for every μ > 0, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., Ω(k) bits, from (n, k)-zero-fixing sources where k ≥ (log log n)2+μ.
In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for k substantially smaller than log log n. The first extractor works for k ≥ C log log log n, for some constant C. The second extractor extracts a positive fraction of entropy for k ≥ log(i)n for any fixed i ∈ ℕ, where log(i) denotes i-times iterated logarithm. The fraction of extracted entropy decreases with i. The first extractor is a function computable in polynomial time in n; the second one is computable in polynomial time in n when k ≤ α log log n/log log log n, where α is a positive constant.
Our results can also be viewed as lower bounds on some Ramsey-type properties. The main difference between the problems about extractors studied here and the standard Ramsey theory is that we study colorings of all subsets of size up to k while in Ramsey theory the sizes are fixed to k. However it is easy to derive results also for coloring of subsets of sizes equal to k. In Corollary 3.1 of Theorem 5.1 we show that for every l ∈ ℕ there exists β < 1 such that for every k and n, n ≤ expl (k), there exists a 2-coloring of k-tuples of elements of [n], \(\psi :\left({\matrix{{[n]} \cr k \cr}} \right) \to \left\{{- 1,1} \right\}\) such that for every V ⊆ [n], |V| = 2k, we have \(\left| {\sum\nolimits_{X \subseteq V,\left| X \right| = k} {\psi (X)}} \right| \le {\beta ^k}\left({\matrix{{2k} \cr k \cr}} \right)\) (Corollary 3.1 is more general — the number of colors may be more than 2).
Similar content being viewed by others
References
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov and A. Wigderson: Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, J. ACM 57 (2010), 1–52.
B. Barak, A. Rao, R. Shaltiel and A. Wigderson: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, Annals of Mathematics 173 (2012), 1483–1543.
C. H. Bennett, G. Brasard and J. M. Robert: How to reduce your enemy’s information, in: Advances in Cryptography (CRYPTO), vol. 218, 468–476.
B. Bollobás, I. Leader and C. Malvenuto: Daisies and other Turán problems, Combinatorics, Probability and Computing 20 (2011), 743–747.
B. Chor, O. Goldreich, J. Håstad, J. Friedman, S. Rudich and R. Smolensky: The Bit Extraction Problem of t-Resilient Functions (Preliminary Version), Proc. FOCS (1985), 396–407.
G. Cohen: private communication.
G. Cohen and I. Shinkar: Zero-fixing extractors for sub-logarithmic entropy, Proc. ICALP (1), 343–354, 2015.
D. Duffus, H. Lefmann and V. Rödl: Shift graphs and lower bounds on Ramsey numbers rk(l, r), Discrete Math. 137 (1995), 177–187.
P. Erdős and A. Hajnal: On chromatic number of infinite graphs, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, Academic Press, New York, 83–98, 1968.
P. Erdős, A. Hajnal and R. Rado: Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196.
A. Gabizon, R. Raz and R. Shaltiel: Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed, SIAM J. Comput. 36 (2006), 1072–1094.
R. L. Graham, B. L. Rothschild and J. H. Spencer: Ramsey Theory, 2nd edition, Wiley, 1990.
C. C. Harner and R. C. Entringer: Arc colorings of digraphs, J. Combinatorial Theory Ser. B 13 (1972), 219–225.
S. Janson, T. Luczak and A. Rucinski: Random Graphs, Wiley, 2000.
J. Kamp and D. Zuckerman: Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, SIAM J. Comput. 36 (2007), 1231–1247.
S. Poljak: Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolin. 32 (1991), 209–212.
J. Schmerl: Unpublished, D. Duffus oral communication 1986.
U. V. Vazirani: Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract), Proc. STOC (1985), 366–378.
Author information
Authors and Affiliations
Corresponding author
Additional information
Partiallly supported by grant EXPRO 19-27871X of the Czech Grant Agency and the institute grant RVO: 67985840; part of this work was done while visiting Simons Institute, Berkeley, California, in fall 2018.
Partially supported by NSF grant DMS 1764385.