Communication Complexity of Graph Algorithms (GraphCom)

图算法的通信复杂性（GraphCom）

• 批准号: EP/X03805X/1
• 负责人: Sagnik Mukhopadhyay
• 金额: $ 35.93万
• 依托单位: University of Sheffield
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX03805X%2F1
• 关键词: Communication; Complexity; Graph; Algorithms; GraphCom

In the realm of data explosion, it is usually the case that a singlecomputational processor is unable to store the vast amount of data needed todo any meaningful computation. The data are generally distributed among alarge number of processors/servers who need to communicate with each othervia a network in order to perform various computational tasks. The recenttrend in big data is a case in point where the rapid acquisition of a vastamount of data makes it impossible for a single processing unit to handle.This problem is generally addressed via different storage architectures forfast access and efficient software paradigms such as MapReduce, Hadoop, andSpark.The general bottleneck of any such system can be abstracted by the followingnatural computational scenario: Suppose a computational system, consisting ofseveral processors, wants to perform a task where the input is distributedamong the processors. Instead of being concerned with the computational timethat is required, we are interested in the communication that the processorsneed to do among themselves in order to perform the task. Apart from bigdata, this problem, and many of its variants, appear frequently in practicein many guises and in different levels of abstractions--in network protocolswhere the goal is to minimize the communication (and thereby error in thecommunication) between two network hubs, in VLSI circuit design where thegoal is to minimize energy used and to pack efficiently by decreasing thenumber of wires required, also in data-structures, circuit complexity,auctions and a plethora of other interesting areas of study.Many sequential algorithms that were widely used in the past have becomegreatly inefficient in practice for such distributed systems. The main goalof the proposed research is to design (or prove the hardness of) fundamentalnetwork algorithms and their generalizations in such distributed models ofcom- putation. Among them, the model of two-party communication and queryprotocols highlight different challenges in accessing information fordistributively processing data over such large networks where the completeinput is not explicitly accessible, hence we exclusively focus on them inthis project.Our goal is to study basic graph-algorithmic problems in these models tothoroughly understand how to overcome different communication bottlenecks. Wewill study them in classical setting (deterministic andrandomized/stochastic) as well as in the quantum setting as quantum computingis undoubtedly the model of computation of the future. Because of ourreliance on efficient network algorithms in modern day-to-day life, webelieve that such research will have a large eventual impact on other areasof computer science and engineering and, at large, society-this is animportant ingredient of the UK government's RD roadmap of supportinglong-range, fundamental, underpinning science and research. The graph ornetwork problems we plan to study fall into two broad categories:connectivity-related problems and flow-related problems. These two classes ofproblems have been extremely well studied for over half a century and arearguably the two fundamental classes of network problems with countlessapplications in other areas of research (e.g., operations research,scheduling, image segmentation, network clustering) and in modern society.Moreover, they have seen surprising progress in recent times. The novelty ofour approach towards these well-studied graph problems is the following: Weexpect, from previous experience, that the insights gained from studying thecommunication and query complexity of these problems will advance ourunderstanding in diverse research areas such as distributed, sequential anddynamic algorithm design. This project can be viewed as the first step towardsystematically studying such universal and cross-paradigm algorithm designtechniques.

在数据爆炸的领域，通常的情况是，一个电子计算处理器无法存储进行任何有意义的计算所需的大量数据。数据通常分布在大量的处理器/服务器中，这些处理器/服务器需要通过网络相互通信以执行各种计算任务。最近大数据的趋势就是一个很好的例子，快速获取大量数据使得单个处理单元无法处理。这个问题通常通过不同的存储架构来解决，以实现快速访问和高效的软件范例，例如MapReduce、Hadoop和Spark。任何此类系统的一般瓶颈都可以通过以下自然计算场景来抽象：假设一个计算系统，由几个处理器组成，要执行一个任务，输入是分布在处理器。我们关心的不是所需的计算时间，而是处理器之间为了执行任务而需要进行的通信。除了大数据之外，这个问题以及它的许多变体在实践中经常以多种形式出现，并出现在不同的抽象层次中-在网络协议中，目标是最小化通信在两个网络集线器之间的通信中的错误，在VLSI电路设计中，目标是通过减少所需的电线数量来最小化所使用的能量并有效地封装，在数据结构中，电路复杂性，拍卖和其他大量有趣的研究领域。过去广泛使用的许多顺序算法在实践中对于这样的分布式系统已经变得非常低效。所提出的研究的主要目标是设计（或证明的硬度）的基本网络算法和他们的推广，在这样的分布式模型的计算。其中，两方通信模型和查询协议突出了在这样的大型网络上访问信息以分布式处理数据的不同挑战，其中完整的输入是不可显式访问的，因此我们在本项目中专门关注它们。我们的目标是研究这些模型中的基本图算法问题，以彻底了解如何克服不同的通信瓶颈。我们将在经典环境（确定性和随机/随机）以及量子环境中研究它们，因为量子计算无疑是未来的计算模型。由于我们在现代日常生活中对高效网络算法的依赖，我们相信这样的研究将对计算机科学和工程的其他领域产生巨大的最终影响，并且在整个社会中，这是英国政府支持长期，基础，基础科学和研究的RD路线图的重要组成部分。我们计划研究的图或网络问题分为两大类：连通性相关问题和流相关问题。这两类问题已经被非常好地研究了超过半个世纪，并且可以说是网络问题的两个基本类别，在其他研究领域（例如，运筹学、调度、图像分割、网络聚类）和现代社会中。而且，它们在最近已经看到了令人惊讶的进展。我们对这些研究良好的图问题的方法的新奇如下：我们期望，从以前的经验，从研究这些问题的查询和查询复杂性的见解将推进我们在不同的研究领域，如分布式，顺序和动态算法设计的理解。该项目可以被看作是系统地研究这种通用的、跨范式的算法设计技术的第一步。