AF: Small: Shortest Paths and Distance Parameters: Faster, Fault-Tolerant and More Accurate
AF: Small: Shortest Paths and Distance Parameters: Faster, Fault-Tolerant and More Accurate
批准号:
2129139
负责人:
Virginia Williams
金额:
$50.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2021
资助国家:
美国
项目状态:
已结题
起止时间:
2021-06-01 至 2024-05-31
中文摘要
以下这些有什么共同点:发送电子邮件,使用GPS软件规划公路旅行,机器人运动规划,揭示生物调节网络的结构以及测量社交网络中的信息传播?答案是:它们都需要计算最短路径。有效地计算最短路径是计算机科学中最古老、研究最充分的问题之一,有着无数的应用。在过去的几十年里,人们设计了许多在网络中寻找最短路径的方法,并对它们的速度有各种保证。最短路径算法的运行速度取决于它所运行的网络的大小。在今天的大数据世界中,过去被认为是快速的算法可能不再是,需要新的更快的算法。在许多应用中,快速比准确更好,因此通常需要获得几乎(但不完全)最短路径的快速算法。真实的世界网络也是动态的,而不是静态的:道路可能由于施工或交通而变得不可用,互联网上的网络链接可能会中断,社交网络中的友谊链接可能会出现和消失。最短路径算法需要能够处理其所运行的网络的动态特性,为此,本项目考虑了最短路径的计算和各种最短路径参数,考虑速度和精度之间的权衡,为网络变化做好准备,并证明算法性能的严格保证。该项目的重点是开发经典计算机科学问题的算法,所有对最短路径(APSP),替换路径,图形直径和半径和介数中心,在各种设置。在n阶任意边权的图中,APSP可以在时间上精确求解,时间是n的三次。稍快的算法是已知的,但没有一个运行速度比立方时间快得多。不幸的是,立方时间对于任何现代应用都是完全不切实际的,并且人们普遍认为APSP不承认适用于所有图的更快算法。该项目的目标之一是确定何时可以实现更快的APSP算法。例如,对输入图形的哪些限制允许更快的APSP?什么样的近似保证是可实现的快速算法?该项目对其他研究问题提出了类似的问题。此外,它考虑了处理图形动态性质的方法。一种方法是构建距离敏感性预言机:存储图的数据结构,并支持最短路径查询,同时还允许为每个查询更新图的少量边。该项目考虑了速度、精度和支持的边缘故障数量之间的权衡。最后,该项目还专注于证明计算机使用细粒度复杂性解决感兴趣问题的速度的局限性。几乎所有使用计算方法的科学家都认识到NP困难对他们工作的影响。当面对NP难问题时,人们可以求助于算法或近似,但很可能不可能找到适用于所有情况的多项式时间算法。使用细粒度复杂性的技术,该项目可以对许多科学学科的研究人员如何看待他们所需要的多项式时间原语产生类似的广泛影响。细粒度的复杂性可以提供一个强有力的解释,为什么他们的计算问题似乎是“卡”在一个二次或二次时间的障碍,并指出特定的硬度假设,必须驳斥,以打破这些障碍。这个奖项反映了NSF的法定使命,并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。
英文摘要
What do the following have in common: sending an email, planning a road trip using GPS software, robot motion planning, uncovering structure in biological regulatory networks and measuring the spread of information in social networks? The answer is: they all necessitate the computation of shortest paths. Efficiently computing shortest paths is among the oldest and most well-studied problems in computer science, with myriads of applications. Many ways to find shortest paths in networks have been designed over the last several decades, with various guarantees on their speed. How fast a shortest paths algorithm runs depends on the size of the network it is run on. In today's world of big data, what was considered fast in the past may no longer be, and new faster algorithms are needed. In many applications it is better to be fast than accurate, so that fast algorithms that obtain paths that are almost (but not quite) shortest are often desired. Real world networks are also dynamic rather than static: roads can become unavailable due to construction or traffic, network links on the internet can go down, and friendship links in social networks can appear and disappear. Shortest paths algorithms need to be able to handle the dynamic nature of the networks they run on. To this end, this project considers the computation of shortest paths and a variety of shortest paths parameters, considering trade-offs between speed and accuracy, preparing for network changes, and proving tight guarantees on the performance of the algorithms.This project focuses on developing algorithms for classical computer science problems such as All-Pairs Shortest Paths (APSP), Replacement Paths, graph Diameter and Radius and Betweenness centrality, in various settings. APSP in graphs on n vertices and arbitrary edge weights, can be solved exactly in time which is cubic in n. Slightly faster algorithms are known, but none run substantially faster than cubic time. Cubic time is completely impractical for any modern application, unfortunately, and it is widely believed that APSP does not admit a substantially faster algorithm that works for all graphs. One of the goals of this project is to determine when faster algorithms for APSP are possible. For instance, what restrictions on the input graphs allow for faster APSP? What kinds of approximation guarantees are achievable with fast algorithms? The project asks similar questions for the other problems of study. In addition, it considers ways to deal with the dynamic nature of graphs. One way is to construct distance sensitivity oracles: data structures that store a graph, and support shortest paths queries while also allowing for a small number of edges of the graph to be updated for each query. The project considers the tradeoffs between speed, accuracy and the number of edge faults that will be supported. Finally, the project also focuses on proving limitations on how fast computers can solve the problems of interest, using fine-grained complexity. Nearly all scientists using computational methods appreciate the implications of NP-hardness on their work. When faced with an NP-hard problem, one can resort to heuristics or approximation, but it is likely impossible to find a polynomial-time algorithm that works for all instances. Using techniques from fine-grained complexity, this project can have a similarly broad impact on how researchers across many scientific disciplines view the polynomial-time primitives they need. Fine-grained complexity can offer a powerful explanation for why their computational problems seem to be "stuck" at a quadratic- or cubic-time barrier, and point to specific hardness conjectures that must be refuted to break those barriers.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.
期刊论文(14)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
列出、验证和计算 DAG 中的最低共同祖先:算法和细粒度下界
DOI:
--
发表时间:
2022
期刊:
and Programming (ICALP 2022
影响因子:
--
作者:
[Mathialagan, Surya, Vassilevska Williams, Virginia, Xu, Yinzhan]
通讯作者:
Xu, Yinzhan
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
更快的单调最小加产品、范围模式和单一来源替换路径
DOI:
--
发表时间:
2021
期刊:
and Programming (ICALP 2021
影响因子:
--
作者:
[Gu, Yuzhou, Polak, Adam, Vassilevska Williams, Virginia, Xu, Yinzhan]
通讯作者:
Xu, Yinzhan
DOI:
--
发表时间:
2022
期刊:
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022
影响因子:
--
作者:
[Deng, Mingyang, Vassilevska Williams, Virginia, Zhong, Ziqian]
通讯作者:
Zhong, Ziqian
DOI:
10.1109/focs54457.2022.00090
发表时间:
2022
期刊:
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
影响因子:
--
作者:
[Williams, Virginia Vassilevska, Woldeghebriel, Eyob, Xu, Yinzhan]
通讯作者:
Xu, Yinzhan
DOI:
--
发表时间:
2022
期刊:
and Programming (ICALP 2022
影响因子:
--
作者:
[Deng, Mingyang, Kirkpatrick, Yael, Rong, Victor, Vassilevska Williams, Virginia, Zhong, Ziqian]
通讯作者:
Zhong, Ziqian
共 13 条
AF:Small: Algorithms and Limitations for Matrix Multiplication
-
批准号:2330048
-
项目类别:Standard Grant
-
资助金额:$60.0万
-
财政年份:2023
-
负责人:Virginia Williams
-
依托单位:
NSF Student Travel Grant for 2019 Theoretical Computer Science (TCS) Women Meeting at Symposium on Theory of Computing (STOC)
-
批准号:1931307
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:2019
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Average-Case Fine-Grained Complexity
-
批准号:1909429
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2019
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Graphs and structures for distance estimation
-
批准号:1740525
-
项目类别:Standard Grant
-
资助金额:$21.9万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
AF: Medium: Collaborative Research: Hardness in Polynomial Time
-
批准号:1740519
-
项目类别:Continuing Grant
-
资助金额:$45.31万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
CAREER:Matrix Products: Algorithms and Applications
-
批准号:1651838
-
项目类别:Continuing Grant
-
资助金额:$40.0万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
BSF:2012338:Shortest Paths: Upper and lower bounds
-
批准号:1740501
-
项目类别:Standard Grant
-
资助金额:$0.24万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Graphs and structures for distance estimation
-
批准号:1528078
-
项目类别:Standard Grant
-
资助金额:$30.0万
-
财政年份:2015
-
负责人:Virginia Williams
-
依托单位:
AF: Medium: Collaborative Research: Hardness in Polynomial Time
-
批准号:1514339
-
项目类别:Continuing Grant
-
资助金额:$60.0万
-
财政年份:2015
-
负责人:Virginia Williams
-
依托单位:
EAGER: Formal models of intention
-
批准号:1347214
-
项目类别:Standard Grant
-
资助金额:$15.0万
-
财政年份:2013
-
负责人:Virginia Williams
-
依托单位:
BSF:2012338:Shortest Paths: Upper and lower bounds
-
批准号:1330843
-
项目类别:Standard Grant
-
资助金额:$4.5万
-
财政年份:2013
-
负责人:Virginia Williams
-
依托单位:
BSF:2012338:Shortest Paths: Upper and lower bounds
-
批准号:1417238
-
项目类别:Standard Grant
-
资助金额:$4.5万
-
财政年份:2013
-
负责人:Virginia Williams
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: