Communication Complexity of 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.