Extracting Computational Entropy and Learning Noisy Linear Functions

檔案

日期

2011-08-01

類型

期刊名稱

IEEE TRANSACTIONS ON INFORMATION THEORY

卷期與頁次

第 57 卷第 8 期,頁 5485–5496

ISSN

0018-9448

語言

英文

摘要

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(X)vertical bar X), for some function f and some distribution X, and we say that such a source has computational min-entropy if any circuit of size 2(k) can only predict f(x) correctly with probability at most 2(-k) given input sampled from X. 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 multisource extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in computational learning theory: learning linear functions under arbitrary distribution with adversarial noise, and we provide a learning algorithm for this problem. In fact, this problem is a well-recognized one in computational learning theory and variants of this problem have been studied intensively before. Thus, in addition to its application to extractors, our learning algorithm also has independent interest of its own, and it can be considered as the main technical contribution of this paper.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Lee, C.-J., Lu, C.-J., & Tsai, S.-C. (2011). Extracting Computational Entropy and Learning Noisy Linear Functions. IEEE TRANSACTIONS ON INFORMATION THEORY, 57(8), 5485–5496. https://doi.org/10.1109/TIT.2011.2158897

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/14805