权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: Graph Streaming, Communication Games, and the Quest for Optimal Algorithms

职业：图流、通信游戏和最佳算法的探索

基本信息

批准号：
2047061
负责人：
Sepehr Assadi
金额：
$ 55.82万
依托单位：
Rutgers University New Brunswick
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-03-01 至 2026-02-28
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2047061&HistoricalAwards=false
关键词：
CAREER Graph Streaming Communication Games

项目摘要

Massive graphs appear in most application domains nowadays: web-pages and hyperlinks, neurons and synapses, papers and citations, or social networks and friendship links are just a few examples. Due to the sheer size and evolving nature of these graphs, processing them via traditional algorithms is often no longer a viable option. As a result, there is a rapidly growing interest in developing algorithms that explicitly account for the restrictions of processing massive graphs. Graph streaming algorithms have been particularly successful in this regard; these are algorithms that process input graphs by making one or few passes over their edges while using a limited memory, much smaller than the input size. This project focuses on further developing the theoretical foundations of graph streaming algorithms: what graph problems can be addressed efficiently via streaming algorithms, what are the inherent limitations of streaming algorithms, and how these limitations can be mitigated through better modeling assumptions? The research directions in this project go hand-in-hand with educational initiatives such as integrating related topics in advanced courses that provide research opportunities for graduate and undergraduate students, and introducing high-school students to exciting ideas in theoretical computer science.More specifically, the focus of this project is on understanding the powers and limitations of graph streaming algorithms for several foundational problems such as coloring, matching, reachability, shortest path, and minimum cut. These are among the most studied problems in theoretical computer science with an extremely broad range of applications. However, despite significant attention, many fundamental questions regarding these problems have remained unanswered in the streaming model. This research focuses on resolving some of these questions and moving toward determining the optimal bounds on the tradeoff between space, number of passes, and approximation ratio of graph streaming algorithms for these problems. This project plans to achieve this goal by designing and analyzing better streaming algorithms as well as using communication games as a powerful tool to prove lower bounds for these problems.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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。