课题基金 / 基金详情

AF: Small: Metric Geometry for Combinatorial Problems

AF: Small: Metric Geometry for Combinatorial Problems
AF:小:组合问题的度量几何
批准号:
1217256
负责人:
James Lee
金额:
$40.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2012
资助国家:
美国
项目状态:
已结题
起止时间:
2012-08-01 至 2015-07-31

项目摘要

项目成果

James Lee的其他基金

相似基金

相关文献

中文摘要
翻译
几何空间在计算机科学中通过许多途径出现。当问题的输入数据具有固有的度量结构时,就会出现最明显的问题,比如网络中节点之间的跳距,或者基因组序列对之间的相似距离。但还有其他更微妙的例子,比如稀疏向量的几何,它在编码理论、信号恢复和量子信息中突出出现,或者电网络中节点之间的有效电阻距离,它已被证明是解决代数和组合问题的强大算法工具。也许最引人注目的是,在组合优化的设置中,高维几何常常以一种意想不到的和深刻的方式呈现出来。一个基本的例子是在各种组合问题的精确或近似解中使用凸优化。在许多情况下,具有先验纯组合结构的问题会涉及到丰富的几何现象。此外,我们现在认识到,这种结构往往是固有的和基本的,因为任何解决问题的办法都必须面对其几何核心。PI将寻求理解这些联系,并开发新的算法技术来利用它们。这项工作将采用高维几何和概率、功能分析、光谱几何和组合学等技术来解决计算机科学前沿的问题。这包括解决我们对理论问题的理解中的根本差距,以及为分析和操作大量数据集的需求所产生的实际问题制定解决方案。为了实现这些目标,研究者打算在近似算法、高维信息理论和离散渐近凸几何领域解决中心的、重要的开放问题。
英文摘要
Geometric spaces arise in computer science through a number of avenues. The most obvious of these occurs when the input data for a problem possesses an inherent metric structure, like the hop-distance between nodes in a network, or the similarity distance between pairs of genomic sequences. But there are other, more subtle examples, like the geometry of sparse vectors, which arises prominently in coding theory, signal recovery, and quantum information, or the effective resistance distance between nodes in an electrical network, which has proven to be a powerful algorithmic tool in attacking both algebraic and combinatorial problems.Perhaps most strikingly, in the setting of combinatorial optimization, high-dimensional geometry often presents itself in an unexpected and profound manner. A basic example is the use of convex optimization in the solution---exact or approximate---to a variety of combinatorial problems. In many cases, a problem with an a priori purely combinatorial structure is shown to involve rich geometric phenomenon. Furthermore, we now realize that often this structure is inherent and fundamental, in the sense that any solution to the problem must confront its geometric core.The PI will seek to understand these connections and develop new algorithmic techniques to exploit them. This work will employ techniques from high-dimensional geometry and probability, functional analysis, spectral geometry, and combinatorics to attack problems at the forefront of computer science. This includes addressing fundamental gaps in our understanding of theoretical issues, as well as developing solutions to practical problems that arise from the need to analyze and manipulate massive data sets. To achieve these goals, the investigator intends to address central, important open problems in the fields of approximation algorithms, high-dimensional information theory, and discrete asymptotic convex geometry.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
UKRI AHRC Impact Acceleration Account
  • 批准号:
    AH/X003574/1
  • 项目类别:
    Research Grant
  • 资助金额:
    $62.41万
  • 财政年份:
    2022
  • 负责人:
    James Lee
  • 依托单位:
Air quality benefits from multi-year changes in post-pandemic working and travel patterns
  • 批准号:
    NE/W00481X/1
  • 项目类别:
    Research Grant
  • 资助金额:
    $22.83万
  • 财政年份:
    2021
  • 负责人:
    James Lee
  • 依托单位:
AF: Small: Metric Information Theory, Online Learning, and Competitive Analysis
  • 批准号:
    2007079
  • 项目类别:
    Standard Grant
  • 资助金额:
    $40.0万
  • 财政年份:
    2020
  • 负责人:
    James Lee
  • 依托单位:
Atmospheric Composition and Radiative forcing effects_due to UN International Ship Emissions regulations
  • 批准号:
    NE/S004564/1
  • 项目类别:
    Research Grant
  • 资助金额:
    $17.36万
  • 财政年份:
    2019
  • 负责人:
    James Lee
  • 依托单位:
国内基金
海外基金
昼夜节律性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
  • 负责人:
    高学文
  • 依托单位: