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）（例如，任何此类系统的一般性瓶颈都可以通过以下构成的型号进行构成的型号来抽象，以构成型号的范围：一个计算的量计算。输入分配给处理器的任务。我们不需要关心计算时间，而是对处理器进行执行以执行任务的处理器的通信感兴趣。除了BigData之外，这个问题及其许多变体在实践中经常出现在许多措施和不同级别的抽象级别中 - 在网络方面 - 协议中的目标是使两个网络中心之间的沟通（从而使vlsi枢纽之间的通信（从而使eCommunication in thecommunication in thecommunication in thecommunication）在VLSI电路之间的电路设计，以最大程度地降低电路，并降低一定程度的数据，并通过逐渐降低数据，并在逐渐降低数据。过去广泛使用的许多有趣的研究领域。对于此类分布式系统的实践中，经过广泛使用的序列算法变得效率低下。拟议的研究的主要目标是设计（或证明）基本网络算法的硬度及其在此类分布式模型中的概括。其中，两党沟通和查询性的模型突出了在访问信息上访问信息的不同挑战，可以在此大型网络上处理数据，在这些大型网络上，完整的信息无法明确访问，因此，我们在此项目中专注于它们。我们的目标是在这些模型中研究这些模型中的基本型号tothorly Communaly commuement commoce complemence volsice offormic offormic offormic offormic cottsmowers offormic offormic offormic cottemend offormic cottemecks complece formece offsemen comploce挑战。我们将在经典环境（确定性的雄性/随机化）以及量子设置中研究它们，因为量子计算无疑是未来计算的模型。由于对现代日常生活中有效的网络算法的良好依赖，因此这种研究最终会对计算机科学和工程的其他领域产生重大影响，并且在整个社会中，这是英国政府RD Rocking of Supportinglong-Range，基础，基础，基础科学和研究的动画成分。我们计划研究的图形Ornetwork问题分为两个广泛的类别：与连接相关的问题和与流动有关的问题。在半个多世纪的时间里，这两个类别的问题已经进行了深入的研究，并且可以毫无疑问，在其他研究领域（例如，运营研究，计划，计划，图像细分，网络聚类，网络聚类）和现代社会的两个基本网络问题和无数范围内的网络问题类别。这些良好的图形问题的新方法是：从以前的经验来看，从研究这些问题的沟通和查询复杂性中获得的见解将使我们在分布式，顺序和底型算法设计等多样化的研究领域中获得我们的意识。该项目可以看作是迈向系统地研究这种通用和跨范围算法设计技术技术的第一步。