Extracting computational entropy and learning noisy linear functions

Chia Jung Lee*, Chi Jen Lu, Shi-Chun Tsai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


We study the task of deterministically extracting randomness from sources containing computational entropy. The sources we consider have the form of a conditional distribution (f(χ)| χ ), for some function f and some distribution χ, and we say that such a source has computational min-entropy k if any circuit of size 2 k can only predict f(x) correctly with probability at most 2 -k given input x sampled from χ. We first show that it is impossible to have a seedless extractor to extract from one single source of this kind. Then we show that it becomes possible if we are allowed a seed which is weakly random (instead of perfectly random) but contains some statistical min-entropy, or even a seed which is not random at all but contains some computational min-entropy. This can be seen as a step toward extending the study of multi-source extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in learning theory: learning linear functions under arbitrary distribution with adversarial noise. For this problem, we provide a learning algorithm, which may have interest of its own.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings
Number of pages10
StatePublished - 1 Dec 2009
Event15th Annual International Conference on Computing and Combinatorics, COCOON 2009 - Niagara Falls, NY, United States
Duration: 13 Jul 200915 Jul 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5609 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th Annual International Conference on Computing and Combinatorics, COCOON 2009
CountryUnited States
CityNiagara Falls, NY

Fingerprint Dive into the research topics of 'Extracting computational entropy and learning noisy linear functions'. Together they form a unique fingerprint.

Cite this