Uses and Simulation of Randomness: Applications to Cryptography,Program Checking and Counting Problems.

随机性的使用和模拟:在密码学、程序检查和计数问题中的应用。

基本信息

  • 批准号:
    9016468
  • 负责人:
  • 金额:
    $ 6.35万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    1991
  • 资助国家:
    美国
  • 起止时间:
    1991-03-01 至 1993-08-31
  • 项目状态:
    已结题

项目摘要

Randomized algorithms consume a valuable resource: uniformly distributed random bits. One of the primary focuses of this work is to develop general techniques for designing algorithms which do not use as many random bits. A pseudo-random generator stretches a short random string into a much longer string that looks totally random to any polynomial time adversary. A pseudo-random generator is the central component in a secure private key cryptosystem, and can be used to conserve on the number of random bits used by Monte Carlo algorithms. Having shown how to construct a pseudo-random generator from any one way function, the investigator plans to develop constructions for even more efficient pseudo-random generators. A typical and important example of a counting problem is to estimate the number of truth assignments that satisfy a given boolean formula. A polynomial time randomized algorithm has been designed for this problem, and a polynomial time deterministic algorithm will be sought. Recently, the theory of program checking has developed which is a useful supplement to program verification and program testing. This theory, which provides a way of computing a function f and verifying the correctness of the answer using a possibly partially faulty program P that supposedly computes f. This theory, which has been successfully applied to a variety of algebraic problems, will be extended to other applications. //
随机化算法消耗了一种宝贵的资源:均匀分布的随机比特。这项工作的主要重点之一是开发通用技术来设计不使用太多随机比特的算法。伪随机生成器将一个短的随机字符串拉伸成一个长得多的字符串,对于任何多项式时间的对手来说,这看起来都是完全随机的。伪随机生成器是安全私钥密码系统的核心组件,可用于节省蒙特卡罗算法使用的随机比特数。在展示了如何从任何单向函数构造伪随机生成器之后,研究人员计划开发更有效的伪随机生成器的构造。计数问题的一个典型且重要的例子是估计满足给定布尔公式的真值分配的数量。针对该问题设计了一个多项式时间随机化算法,并将寻求一个多项式时间确定性算法。近年来,程序检查理论得到了发展,它是对程序验证和程序测试的有益补充。这一理论提供了一种计算函数f和使用可能部分有缺陷的程序P来验证答案的正确性的方法,该程序被认为是计算f的。该理论已经成功地应用于各种代数问题,将被扩展到其他应用。//

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

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

{{ 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 Luby其他文献

Real-Time Liquid Wireless Transport for Video Streaming in Rural and Agricultural Applications
用于农村和农业应用中视频流的实时液体无线传输
  • DOI:
    10.1145/3638036.3640806
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    E. K. A. Permatasari;Evan Gossling;Md Nadim;Sarath Babu;Daji Qiao;Hongwei Zhang;Michael Luby;John W. Byers;L. Minder;P. Aggrawal
  • 通讯作者:
    P. Aggrawal
An Efficient Monte-carlo Algorithm for the Ml-type Ii Parameter Estimation of Non-linear Diffusions (an Extended Abstract)
非线性扩散 Ml 型 Ii 参数估计的高效蒙特卡罗算法(扩展摘要)
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Paul Dagum;Richard M. Karp;Michael Luby;Sheldon M. Ross
  • 通讯作者:
    Sheldon M. Ross
FLID-DL: congestion control for layered multicast
FLID-DL:分层组播的拥塞控制
  • DOI:
    10.1109/jsac.2002.803998
  • 发表时间:
    2002
  • 期刊:
  • 影响因子:
    0
  • 作者:
    John W. Byers;Gavin B. Horn;Michael Luby;Michael Mitzenmacher;William Shaver
  • 通讯作者:
    William Shaver

Michael Luby的其他文献

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

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

Collaborative Research: CNS Core: Medium: Real-Time Liquid Wireless Networking for Data-Intensive Rural Applications
合作研究:CNS 核心:媒介:数据密集型农村应用的实时液体无线网络
  • 批准号:
    2212574
  • 财政年份:
    2022
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
EAGER: Liquid Foundation Internet
EAGER:互联网粉底液
  • 批准号:
    1936572
  • 财政年份:
    2019
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
Efficient Algorithms for Encoding and Decoding Asymptotically Good Error Correcting Codes
用于编码和解码渐近良好纠错码的高效算法
  • 批准号:
    9800452
  • 财政年份:
    1998
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
Workshop at ICSI: On Randomized Algorithms and Computation, December 17-22, l995, Berkeley, California
ICSI 研讨会:随机算法和计算,1995 年 12 月 17 日至 22 日,加利福尼亚州伯克利
  • 批准号:
    9531792
  • 财政年份:
    1995
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
Efficient Algorithm Design Using Randomness Parsimoniously
简约地利用随机性的高效算法设计
  • 批准号:
    9304722
  • 财政年份:
    1993
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Continuing Grant

相似国自然基金

Simulation and certification of the ground state of many-body systems on quantum simulators
  • 批准号:
  • 批准年份:
    2020
  • 资助金额:
    40 万元
  • 项目类别:

相似海外基金

CAREER: Advances to the EMT Modeling and Simulation of Restoration Processes for Future Grids
职业:未来电网恢复过程的 EMT 建模和仿真的进展
  • 批准号:
    2338621
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Continuing Grant
Collaborative Research: Material Simulation-driven Electrolyte Designs in Intermediate-temperature Na-K / S Batteries for Long-duration Energy Storage
合作研究:用于长期储能的中温Na-K / S电池中材料模拟驱动的电解质设计
  • 批准号:
    2341994
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
EAGER: Liutex-based Sub-Grid Model for Large Eddy Simulation of Turbulent Flow
EAGER:基于 Liutex 的湍流大涡模拟子网格模型
  • 批准号:
    2422573
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
Global spatially explicit gridded transport model coupled with an integrated assessment model: a new-generation simulation framework for transport decarbonization strategy
全球空间明确网格交通模型与综合评估模型相结合:新一代交通脱碳战略模拟框架
  • 批准号:
    23K28290
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
Molecules for Quantum simulation
量子模拟分子
  • 批准号:
    MR/X033430/1
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Fellowship
International Collaboration Towards Net Zero Computational Modelling and Simulation (CONTINENTS)
实现净零计算建模和仿真的国际合作(大陆)
  • 批准号:
    EP/Z531170/1
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Research Grant
DXに基づく急性期病院の認知症ケア専門職連携を促進するSimulation Platformの開発
基于DX开发促进急症医院痴呆护理专业协作的模拟平台
  • 批准号:
    23K27913
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
CAREER:HCC: Using Virtual Reality Gaming to Develop a Predictive Simulation of Human-Building Interactions: Behavioral and Emotional Modeling for Public Space Design
职业:HCC:使用虚拟现实游戏开发人类建筑交互的预测模拟:公共空间设计的行为和情感建模
  • 批准号:
    2339999
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Continuing Grant
Travel: NSF Student Travel Grant for 2024 ACM SIGSIM Principles of Advanced Discrete Simulation (PADS)
旅行:2024 年 ACM SIGSIM 高级离散仿真原理 (PADS) 的 NSF 学生旅行补助金
  • 批准号:
    2416160
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
RAPID: Enhancing WUI Fire Assessment through Comprehensive Data and High-Fidelity Simulation
RAPID:通过综合数据和高保真模拟增强 WUI 火灾评估
  • 批准号:
    2401876
  • 财政年份:
    2024
  • 资助金额:
    $ 6.35万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了