AF: Small: Challenges in Unconditional Pseudorandomness for Boolean Computation

AF:小:布尔计算无条件伪随机性的挑战

基本信息

  • 批准号:
    1814788
  • 负责人:
  • 金额:
    $ 35万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2018
  • 资助国家:
    美国
  • 起止时间:
    2018-06-01 至 2022-05-31
  • 项目状态:
    已结题

项目摘要

The performance of modern computers can be measured on several axes, such as the time or memory consumed. Another axis is the amount of randomness used, as many common algorithms (such as opinion polls) use randomness as a key resource. However, true randomness (such as that derived from physical phenomena) can be a scarce resource, and as such significant research has explored how the use of randomness can be minimized while still efficiently solving key algorithmic problems. One prominent algorithmic challenge is to compute the volume of geometric objects. While this problem is simple in low dimensions, it is significantly more difficult in the higher number of dimensions often required for applications. While randomized algorithms have been developed for (approximately) computing volumes, comparable deterministic algorithms have yet to be developed. This project will study techniques for the design of such algorithms. It will also promote the study of pseudorandomness in general through course design, organization of workshops, and training of undergraduate and graduate students.In particular, this project will design pseudorandom generators, which are maps that stretch a short seed of (true) randomness to a longer output of pseudorandomness, where this output is indistinguishable from random (from the perspective of the relevant algorithm). The construction of suitable pseudorandom generators is a well-known avenue to the derandomization of algorithms. However, existing constructions of pseudorandom generators fall short of derandomization even for simple algorithmic problems. This project will study new paradigms for the construction of pseudorandom generators, especially for those which can derandomize algorithms for geometric problems such as (approximately) computing volumes. This study will be facilitated by combining existing tools, such as those from communication complexity and cryptographic pseudorandomness, in novel ways.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
现代计算机的性能可以在几个轴上测量,例如消耗的时间或内存。 另一个轴是随机性的使用量,因为许多常见的算法(如民意调查)使用随机性作为关键资源。 然而,真正的随机性(例如来自物理现象的随机性)可能是一种稀缺资源,因此重要的研究已经探索了如何在有效解决关键算法问题的同时最大限度地减少随机性的使用。 一个突出的算法挑战是计算几何对象的体积。 虽然这个问题在低维度中很简单,但在应用程序通常需要的更高数量的维度中,它明显更困难。 虽然随机算法已经被开发用于(近似地)计算量,但是类似的确定性算法尚未被开发。 本项目将研究设计这种算法的技术。 该项目还将通过课程设计、组织讲习班、培训本科生和研究生来促进对伪随机性的一般性研究,特别是将设计伪随机发生器,这是一种映射,它将(真)随机性的短种子延伸为较长的伪随机性输出,其中该输出与随机性无法区分(从相关算法的角度来看)。构造合适的伪随机发生器是去随机化算法的一个众所周知的途径。 然而,现有的伪随机发生器的结构达不到去随机化,即使是简单的算法问题。 这个项目将研究伪随机生成器的构造的新范例,特别是对于那些可以去随机化几何问题的算法,如(近似)计算量。 这项研究将通过结合现有的工具,如从通信复杂性和密码伪随机性,以新颖的方式促进。这个奖项反映了NSF的法定使命,并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

期刊论文数量(5)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
即使在量子世界中,空间隔离也意味着零知识
An improved derandomization of the switching lemma
改进的切换引理去随机化
Random Restrictions and PRGs for PTFs in Gaussian Space
高斯空间中 PTF 的随机限制和 PRG
Pseudorandom Generators for Read-Once Branching Programs, in Any Order
用于以任意顺序读取一次的分支程序的伪随机生成器
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Michael Forbes其他文献

Benders Decomposition with Delayed Disaggregation for the Active Passive Vehicle Routing Problem
主动被动车辆路径问题的延迟分解 Benders 分解
The Value of Drilling—A Chance-Constrained Optimization Approach
  • DOI:
    10.1007/s42461-024-01061-8
  • 发表时间:
    2024-08-22
  • 期刊:
  • 影响因子:
    2.000
  • 作者:
    Rick Jeuken;Michael Forbes
  • 通讯作者:
    Michael Forbes
Pupil-sparing third nerve palsies and hemiataxia: Claude’s and reverse Claude’s syndrome
  • DOI:
    10.1016/j.jocn.2015.12.010
  • 发表时间:
    2016-06-01
  • 期刊:
  • 影响因子:
  • 作者:
    James R. Bateman;Pavan Murty;Michael Forbes;Kisha Young Collier;Danoushka Tememe;Octavio de Marchena;William J. Powers
  • 通讯作者:
    William J. Powers
Augmentation of CFTR maturation by S-nitrosoglutathione reductase 1 2
S-亚硝基谷胱甘肽还原酶促进 CFTR 成熟 1 2
  • DOI:
  • 发表时间:
    2015
  • 期刊:
  • 影响因子:
    0
  • 作者:
    K. Zaman;Victoria Sawczak;Atiya Zaidi;Maya Butler;Deric Bennett;Paulina;Getsy;Maryam Zeinomar;Zivi Greenberg;Michael Forbes;Shagufta Rehman;Vinod;Jyothikumar;Kimberly Deronde;A. Sattar;Laura A. Smith;Deborah A. Corey;Adam;Straub;F. Sun;L. Palmer;A. Periasamy;S. Randell;T. Kelley;S. Lewis;B. Gaston
  • 通讯作者:
    B. Gaston
IN GOLF PUTTING Examining visual and attentional focus influences on golf putting performance using a dual-task paradigm
在高尔夫推杆中使用双任务范例检查视觉和注意力焦点对高尔夫推杆表现的影响
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Michael Forbes
  • 通讯作者:
    Michael Forbes

Michael Forbes的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Michael Forbes', 18)}}的其他基金

Compressible Turbulence from Quantum to Classical
从量子到经典的可压缩湍流
  • 批准号:
    2309322
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
CAREER: Algebraic and Geometric Complexity Theory
职业:代数和几何复杂性理论
  • 批准号:
    2047310
  • 财政年份:
    2021
  • 资助金额:
    $ 35万
  • 项目类别:
    Continuing Grant
Quantum Simulation of Turbulence with Cold Atoms
冷原子湍流的量子模拟
  • 批准号:
    2012190
  • 财政年份:
    2020
  • 资助金额:
    $ 35万
  • 项目类别:
    Continuing Grant
CRII: AF: Linear-Algebraic Pseudorandomness
CRII:AF:线性代数伪随机性
  • 批准号:
    1755921
  • 财政年份:
    2018
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Quantum Dynamics with Cold Atoms
冷原子的量子动力学
  • 批准号:
    1707691
  • 财政年份:
    2017
  • 资助金额:
    $ 35万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: RUI: The challenges of living small: functional tradeoffs in the vertebral bone structure of diminutive mammals
合作研究:RUI:小型生活的挑战:小型哺乳动物椎骨结构的功能权衡
  • 批准号:
    2223964
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
NSF-BSF: AF: Small: Algorithmic and Information-Theoretic Challenges in Causal Inference
NSF-BSF:AF:小:因果推理中的算法和信息论挑战
  • 批准号:
    2321079
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
  • 批准号:
    2311397
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
CPS: Small: Infusing Quantum Computing, Decomposition, and Learning for Addressing Cyber-Physical Systems Optimization Challenges
CPS:小型:融合量子计算、分解和学习来应对网络物理系统优化挑战
  • 批准号:
    2312086
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Collaborative Research: RUI: The challenges of living small: functional tradeoffs in the vertebral bone structure of diminutive mammals
合作研究:RUI:小型生活的挑战:小型哺乳动物椎骨结构的功能权衡
  • 批准号:
    2223965
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Collaborative Research: SaTC: CORE: Small: Targeting Challenges in Computational Disinformation Research to Enhance Attribution, Detection, and Explanation
协作研究:SaTC:核心:小型:针对计算虚假信息研究中的挑战以增强归因、检测和解释
  • 批准号:
    2241068
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Collaborative Research: SaTC: CORE: Small: Targeting Challenges in Computational Disinformation Research to Enhance Attribution, Detection, and Explanation
协作研究:SaTC:核心:小型:针对计算虚假信息研究中的挑战以增强归因、检测和解释
  • 批准号:
    2241070
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Collaborative Research: SaTC: CORE: Small: Targeting Challenges in Computational Disinformation Research to Enhance Attribution, Detection, and Explanation
协作研究:SaTC:核心:小型:针对计算虚假信息研究中的挑战以增强归因、检测和解释
  • 批准号:
    2241069
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
SaTC: CORE: Small: Emerging Security Challenges and a Solution Framework for FPGA-accelerated Cloud Computing
SaTC:CORE:小型:新兴安全挑战和 FPGA 加速云计算的解决方案框架
  • 批准号:
    2247059
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
CIF: Small: Impact of radiation trapping on sensing and communication systems in the THz, infrared, and optical regime - foundations, challenges, and opportunities
CIF:小:辐射捕获对太赫兹、红外和光学领域传感和通信系统的影响 - 基础、挑战和机遇
  • 批准号:
    2320937
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了