首页    期刊浏览 2024年12月05日 星期四
登录注册

文章基本信息

  • 标题:Extractors for Adversarial Sources via Extremal Hypergraphs
  • 本地全文:下载
  • 作者:Eshan Chattopadhyay ; Jesse Goodman ; Vipul Goyal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-44
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples with no entropy at all or with unwanted dependence. Motivated by this and applications from cryptography, we initiate a systematic study of randomness extraction for the class of adversarial sources defined as follows.

    A weak source X of the form X 1 X N , where each X i is on n bits, is an ( N K n k ) -source of locality d if the following hold:

    (1) Somewhere good sources: at least K of the X i 's are independent, and each contains min-entropy at least k . We call these X i 's good sources, and their locations are unknown. (2) Bounded dependence: each remaining (bad) source can depend arbitrarily on at most d good sources.

    We focus on constructing extractors with negligible error, in the regime where most of the entropy is contained within a few sources instead of across many (i.e., k is at least polynomial in K ). In this setting, even for the case of 0 -locality, very little is known prior to our work. For d 1 , essentially no previous results are known. We present various new extractors for adversarial sources in a wide range of parameters, and some of our constructions work for locality d = K (1) . As an application, we also give improved extractors for small-space sources.

    The class of adversarial sources generalizes several previously studied classes of sources, and our explicit extractor constructions exploit tools from recent advances in extractor machinery, such as two-source non-malleable extractors and low-error condensers. Thus, our constructions can be viewed as a new application of non-malleable extractors. In addition, our constructions combine the tools from extractor theory in a novel way through various sorts of explicit extremal hypergraphs. These connections leverage recent progress in combinatorics, such as improved bounds on cap sets and explicit constructions of Ramsey graphs, and may be of independent interest.

  • 关键词:cap sets ; extractors ; extremal hypergraphs ; Non;malleable extractors ; Ramsey Graphs
国家哲学社会科学文献中心版权所有