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

Abstract

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
Pages338-347
Number of pages10
DOIs
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

Conference

Conference15th Annual International Conference on Computing and Combinatorics, COCOON 2009
CountryUnited States
CityNiagara Falls, NY
Period13/07/0915/07/09

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

Cite this