课题基金 / 基金详情

AF: Small: Studies in Randomness Extraction

AF: Small: Studies in Randomness Extraction
AF:小:随机性提取的研究
批准号:
1016158
负责人:
Marius Zimand
金额:
$22.39万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2010
资助国家:
美国
项目状态:
已结题
起止时间:
2010-08-01 至 2014-07-31

项目摘要

项目成果

Marius Zimand的其他基金

相似基金

相关文献

中文摘要
翻译
随机性提取是将低质量随机性对象转化为高质量随机性对象的算法过程。对象(通常称为源)可以是有限概率分布、有限二进制字符串和无限二进制序列,随机质量分别通过最小熵、Kolmogorov复杂度和建设性Hausdorff维数来衡量。在这三种情况下都存在大量关于随机性提取的工作。我们的项目将通过研究超出当前主要技术和工具开发的一些基本假设的情况下的随机性提取来扩展该领域。在某些应用中,假设所涉及的概率分布是独立的是有问题的。因此,试图修复缺陷源的算法应该能够处理具有有限独立性的偶数源。与目前只考虑完全独立来源的文献相比,该项目将研究从两个或多个具有有限独立性的来源中随机提取的问题。扩展一些部分结果,目标是建立可以从这些来源获得的随机性质量的上界,并设计在上界附近执行的有效提取器。该项目的另一条研究路线是致力于暴露弹性提取器,这是一种有效的程序,可以设法提取看起来随机的比特,即使对具有自适应访问输入源的对手来说也是如此。目的是设计出适合密码学应用的参数提取器。随机抽取是一个非常活跃的领域,甚至在该领域之外也产生了重大影响。提出的研究开辟了新的研究方向,是自然的和具有挑战性的。它为随机抽取的研究增加了新的维度,具有扩大抽取器应用范围的潜力。随机抽取在计算复杂性、随机算法、构造组合学、密码学、纠错码和其他领域都有应用。该项目试图使这些应用程序更加实用和健壮。该项目将在计算复杂性、Kolmogorov复杂性和算法信息理论之间建立新的联系。该项目将允许本科生和研究生参与具有强烈理论风味和现实应用前景的研究活动。
英文摘要
Randomness extraction is an algorithmical process that transforms objects with low-quality randomness into objects with high-quality randomness. The objects (usually called sources) can be finite probability distributions, finite binary strings, and infinite binary sequences, and the randomness quality is measured, respectively, by min-entropy, Kolmogorov complexity, and constructive Hausdorff dimension. There exists a vast amount of work on randomness extractions in all three settings. Our project will extend the field by investigating randomness extraction in situations that go beyond some of the basic assumptions for which the main current techniques and tools have been developed. In some applications, the assumption that the involved probability distributions are independent is problematic. Therefore, an algorithm that attempts to remedy defective sources should be able to handle even sources with bounded independence. The project will study the issue of randomness extraction from two or more sources with bounded independence, in contrast with the current literature that has only considered the case of fully independent sources. Extending some partial results, the objective is to establish upper bounds on the quality of randomness that can be obtained from such sources and to design efficient extractors that perform in the vicinity of the upper bounds. Another research line of the project is dedicated to exposure-resilient extractors, which are efficient procedures that manage to extract bits that look random even to an adversary that has adaptive access to the input sources. The objective is to design such extractors with parameters suitable for applications in cryptography.Randomness extraction is a very active field and has been an incubator of ideas with a significant impact even outside the area. The proposed research opens new directions of study that are natural and challenging. It adds new dimensions in the study of randomness extraction and has the potential of enlarging the range of applications of extractors. Randomness extraction has applications in computational complexity, randomized algorithms, constructive combinatorics, cryptography, error-correcting codes, and other areas. The project attempts to make many of these applications more practical and more robust. The project will establish new connections between computational complexity, Kolmogorov complexity, and algorithmical information theory. The project will allow undergraduate and graduate students to participate in research activities that have a strong theoretical flavor and the promise of real-world applications.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: RUI: New Directions in Kolmogorov Complexity and Network Information Theory
  • 批准号:
    1811729
  • 项目类别:
    Standard Grant
  • 资助金额:
    $23.62万
  • 财政年份:
    2018
  • 负责人:
    Marius Zimand
  • 依托单位:
New Directions in the Study of Randomness Extractors
  • 批准号:
    0634830
  • 项目类别:
    Standard Grant
  • 资助金额:
    $12.53万
  • 财政年份:
    2006
  • 负责人:
    Marius Zimand
  • 依托单位:
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: