AF: Small: Rare Events - New Probabilistic and Algorithmic Techniques

AF:小:罕见事件 - 新的概率和算法技术

基本信息

  • 批准号:
    1614023
  • 负责人:
  • 金额:
    $ 45万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2016
  • 资助国家:
    美国
  • 起止时间:
    2016-07-01 至 2020-06-30
  • 项目状态:
    已结题

项目摘要

Randomness is a powerful tool in mathematics and computer science. In mathematics, it underlies the "probabilistic method," a method to prove that certain mathematical objects with desired properties exist, by simply picking an object at random, and arguing that with a positive probability, the object has the required properties. In computer science, randomness is a powerful tool in algorithm design. Randomized algorithms are often simpler or perform better than their deterministic counterparts, and have found applications in many fields such as graph algorithms, linear programming, routing algorithms, coding theory, communication protocols, approximation algorithms, cryptography, and many more.One of the main reasons that randomness is ubiquitous in algorithm design, is that typically the probabilistic method shows that the desired events, which control the success of the algorithm, not only occur with a positive probability (which would be sufficient to prove existence), but that they in fact occur with overwhelming probability. As such, it immediately lends itself to the design of randomized algorithms.The focus of this project is on regimes where this is not the case. There are several probabilistic techniques which can prove the existence of "rare events." That is, they show that the desired events occur with a positive (yet tiny) probability. Although we do not have many such techniques, they have proven to be extremely valuable, with applications in many domains: combinatorial optimization, learning theory, approximation algorithms, distributed algorithms, computational geometry, numerical analysis, and more. The main reason is that such techniques, and more importantly, their algorithmic realizations, provide algorithm designers with new sets of tools that they can apply that go beyond "vanilla" probabilistic techniques.This project will focus both on the development of new mathematical and algorithmic tools and techniques, as well as on their assimilation by students and researchers. This involves mentoring students, creating and teaching relevant classes, writing expository surveys, and organizing workshops.On the technical side, the project focuses on two main domains. The first is discrepancy theory. Discrepancy theory studies irregularities within distributions, and has intimate relations with rounding techniques for integer programs, and more generally with combinatorial optimization. There are several important open problems in discrepancy theory (most notably the Komlos conjecture), which this project sets a concrete plan to resolve.The second domain is pseudo-randomness. Pseudo-randomness is the study of deterministic objects which attain certain properties satisfied by random objects. As such, this is a wide area of study, with many applications both in mathematics and computer science. In this project, we focus on pseudorandom objects which, for some bounded family of tests, behave exactly like random objects. While in some settings such objects are deeply understood and widely applied (for example, k-wise independence, which has applications in coding theory, data structures, de-randomization, and more), in many other settings they are much less understood. This project explores new approaches to better understand such objects and to develop new algorithmic applications of them.
随机性是数学和计算机科学中的一个强大工具。在数学中,它是“概率方法”的基础,这是一种证明某些具有所需属性的数学对象存在的方法,通过简单地随机选择一个对象,并论证具有正概率的对象具有所需属性。在计算机科学中,随机性是算法设计的有力工具。随机算法通常比确定性算法更简单或性能更好,并且已经在许多领域中找到了应用,例如图算法、线性规划、路由算法、编码理论、通信协议、近似算法、密码学等等。随机性在算法设计中无处不在的主要原因之一是,通常概率方法表明期望的事件,控制算法的成功,不仅以正概率发生(这将足以证明存在),而且它们实际上以压倒性的概率发生。因此,它立即适合于随机算法的设计。这个项目的重点是在政权,这是不是这样的情况。有几种概率技术可以证明“罕见事件”的存在。也就是说,它们表明所期望的事件以正(但很小)的概率发生。虽然我们没有太多这样的技术,但它们已被证明是非常有价值的,在许多领域的应用:组合优化,学习理论,近似算法,分布式算法,计算几何,数值分析,等等。主要原因是这些技术,更重要的是,它们的算法实现,为算法设计者提供了一套新的工具,他们可以应用,超越“香草”概率技术。这个项目将集中在新的数学和算法工具和技术的发展,以及他们的同化的学生和研究人员。这包括指导学生,创建和教授相关课程,撰写简要调查,并组织研讨会。在技术方面,该项目侧重于两个主要领域。第一个是差异理论。离散理论研究分布中的不规则性,与整数规划的舍入技术有着密切的关系,更广泛地说,与组合优化有着密切的关系。在差异理论中有几个重要的开放问题(最著名的是Komlos猜想),本项目制定了具体的解决方案。第二个领域是伪随机性。伪随机性是对确定性对象的研究,这些确定性对象获得了随机对象所满足的某些属性。因此,这是一个广泛的研究领域,在数学和计算机科学中都有许多应用。在这个项目中,我们专注于伪随机对象,对于一些有界族的测试,行为完全像随机对象。虽然在某些设置中,这些对象被深入理解并广泛应用(例如,k-wise独立性,它在编码理论,数据结构,去随机化等方面都有应用),但在许多其他设置中,它们的理解要少得多。该项目探索新的方法来更好地理解这些对象,并开发新的算法应用程序。

项目成果

期刊论文数量(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 }}

Shachar Lovett其他文献

A proof of the GM-MDS conjecture
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits
决策树的大偏差范围和 AC0 电路的采样下界
Torus polynomials: an algebraic approach to ACC lower bounds
环面多项式:ACC 下界的代数方法
  • DOI:
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Abhishek Bhrushundi;Kaave Hosseini;Shachar Lovett;Sankeerth Rao
  • 通讯作者:
    Sankeerth Rao
The Complexity of Boolean Functions in Different Characteristics
  • DOI:
    10.1007/s00037-010-0290-4
  • 发表时间:
    2010-05-12
  • 期刊:
  • 影响因子:
    1.000
  • 作者:
    Parikshit Gopalan;Amir Shpilka;Shachar Lovett
  • 通讯作者:
    Shachar Lovett
Probabilistic existence of rigid combinatorial structures
刚性组合结构的概率存在

Shachar Lovett的其他文献

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

{{ truncateString('Shachar Lovett', 18)}}的其他基金

AF: Small: Intermediate models between communication complexity and query complexity
AF:小:通信复杂度和查询复杂度之间的中间模型
  • 批准号:
    2006443
  • 财政年份:
    2020
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
The Sunflower Conjecture, Disjunctive Normal Forms, and Beyond
向日葵猜想、析取范式及其他
  • 批准号:
    1953928
  • 财政年份:
    2020
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
CAREER: Algebraic and Combinatorial Structures In Complexity Theory
职业:复杂性理论中的代数和组合结构
  • 批准号:
    1350481
  • 财政年份:
    2014
  • 资助金额:
    $ 45万
  • 项目类别:
    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 万元
  • 项目类别:
    重大研究计划

相似海外基金

Small molecules combination therapy using polypharmacology approach as a novel treatment paradigm for rare bone disease
使用多药理学方法的小分子联合疗法作为罕见骨病的新型治疗范例
  • 批准号:
    10759694
  • 财政年份:
    2023
  • 资助金额:
    $ 45万
  • 项目类别:
III: Small: RareXplain: A Computational Framework for Explainable Rare Category Analysis
III:小:RareXplain:可解释稀有类别分析的计算框架
  • 批准号:
    2117902
  • 财政年份:
    2021
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
CIF: Small: Statistically Optimal Subsampling for Big Data and Rare Events Data
CIF:小:大数据和稀有事件数据的统计最佳子采样
  • 批准号:
    2105571
  • 财政年份:
    2021
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
High throughput small molecule screening with 3D lung-mimetic hydrogels in the rare lung disease Lymphangioleiomyomatosis
使用 3D 拟肺水凝胶对罕见肺部疾病淋巴管平滑肌瘤病进行高通量小分子筛选
  • 批准号:
    411850
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
Reduced Small Carbocyclic pi-Complexes of Rare-Earth Metals
稀土金属的还原小碳环π配合物
  • 批准号:
    516479-2017
  • 财政年份:
    2017
  • 资助金额:
    $ 45万
  • 项目类别:
    Canadian Graduate Scholarships Foreign Study Supplements
Characterization of rare conformational states of proteins by combination of high-pressure X-raycrystallography with high-pressure NMR spectroscopy. Application to the small GproteinRas, its oncogenic mutants and its drug complexes.
通过高压 X 射线晶体学与高压核磁共振波谱相结合来表征蛋白质的稀有构象状态。
  • 批准号:
    390275479
  • 财政年份:
    2017
  • 资助金额:
    $ 45万
  • 项目类别:
    Research Grants
Luminescence as a Structural Probe of Ultra-Small Rare Earth Oxide Nanoparticles
发光作为超小稀土氧化物纳米粒子的结构探针
  • 批准号:
    1402298
  • 财政年份:
    2013
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
Luminescence as a Structural Probe of Ultra-Small Rare Earth Oxide Nanoparticles
发光作为超小稀土氧化物纳米粒子的结构探针
  • 批准号:
    1209371
  • 财政年份:
    2012
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
Development of Catalytic Synthetic Reactions with High Clark Number Elements (Without A small Amounts of Rare Metals)
高克拉克数元素(不含少量稀有金属)催化合成反应的进展
  • 批准号:
    22590008
  • 财政年份:
    2010
  • 资助金额:
    $ 45万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
A Core Western Australian Cell Sorting Facility - Ultra-Small Objects and Rare Cell Populations
西澳大利亚核心细胞分选设施 - 超小物体和稀有细胞群
  • 批准号:
    LE0989782
  • 财政年份:
    2009
  • 资助金额:
    $ 45万
  • 项目类别:
    Linkage Infrastructure, Equipment and Facilities
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了