### Abstract

In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence of n independent symbols from {0, 1}^{d}. The only randomness guarantee on such a source is that the whole source has min-entropy k. We give an explicit deterministic extractor which can extract Ω(log k -log d-log log(1/ε)) bits with error ε, for any n, d, k ∈ ℕ and ε ∈ (0, 1). For sources with a larger min-entropy, we can extract even more randomness, When k ≥ n ^{1/2+γ}, for any constant γ ∈ (0, 1/2), we can extract m = k - O(d log (1/ε)) bits with any error ε ≥ 2 ^{Ωnγ}, When k ≥ log^{c} n, for some constant c > 0, we can extract m = k -d(1/ε)^{O(1)} bits with any error ε ≥ k^{-Ω(1)}. Our results generalize those of Kamp & Zuckerman and Gabizon et al. which only work for bit-fixing sources (with d = 1 and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a non-explicit deterministic extractor which can extract m = k-O(log(1/ε)) bits whenever k = w(d+log(n/ε)), Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy loss k -m = ω(log(1/ε)). This generalizes a lower bound of Radhakrishnan & Ta-Shma with respect to general sources.

Original language | English |
---|---|

Title of host publication | Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings |

Publisher | Springer Verlag |

Pages | 84-95 |

Number of pages | 12 |

ISBN (Print) | 3540359044, 9783540359043 |

DOIs | |

State | Published - 1 Jan 2006 |

Event | 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 - Venice, Italy Duration: 10 Jul 2006 → 14 Jul 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4051 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 |
---|---|

Country | Italy |

City | Venice |

Period | 10/07/06 → 14/07/06 |

## Fingerprint Dive into the research topics of 'Deterministic extractors for independent-symbol sources'. Together they form a unique fingerprint.

## Cite this

*Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings*(pp. 84-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4051 LNCS). Springer Verlag. https://doi.org/10.1007/11786986_9