Hiring!

I am looking for a motivated and mathematically inclined PhD student with previous experience in courses/modules in theoretical computer science. This position is based in the Department of Computer Science in the University of Sheffield and comes with full tuition fee and stipend. Travel support is also available. The potential candidate will be expected to support algorithms teaching in the department (which will be paid additionally).

A strong interest in graph algorithms, complexity theory, distributed and streaming algorithms and/or combinatorial optimization will be a plus. Starting date is negotiable. Please see below for a brief motivation and papers of interest.

Motivation

After a long-drawn war, two nations, Oceania and Eurasia, are now at peace but in not much of talking terms. However, they will have to figure out how much shipment their combined rail network can carry from the capital city of Oceania to that of Eurasia. Both Oceania and Eurasia know about their own rail networks in detail, but none of them knows anything about other nation’s network plans. Because of the political situation, they want to keep communication between them to a minimum. You are the chief researcher of Eurasia, in contact with Winston Smith, the chief researcher of Oceania. How much communication do you need to do to figure it out?

The aim of this project is to investigate such fundamental network problems where the network data is distributed between multiple processors. Such problems appear in countless guises in modern life: The transportation problem mentioned before is inspired by actual logistic difficulties that kept the US and Russia busy during the first half of the 20th century (see https://tinyurl.com/2p844c2y for a fun read). In the modern realm of data explosion, these network questions are more topical than ever: The network data (think of the friendship network of Facebook or the follower network of Twitter or the hyperlink network of Google) is usually too large to be stored in a single computational processor and hence is generally distributed among a large number of processors/servers who need to communicate with each other via a network in order to perform various computational tasks. This problem is generally addressed via different storage architectures for fast access and efficient software paradigms such as MapReduce, Hadoop, and Spark.

Many traditional algorithms that were widely used in the past have become greatly inefficient in practice for such distributed systems. The main goal of the proposed research is to design (or prove the hardness of) fundamental network algorithms and their generalisations in such distributed models of computation. To be concrete, we will mainly be interested in the following two models in this project.

• Two-party communication protocols: The graph data is distributed to two machines, namely Alice and Bob. Machines can access their local data for free, but it costs for them to communicate.
• Query protocols: The graph data is stored in external memory (e.g., among many external servers or cloud) and the local machine is allowed to access the data only by query accesses which can be answered quickly.

The project will lead to major advances in our understanding of “distributed network algorithms”, which is an important research area within theoretical computer science that is concerned with addressing precisely the question described above.

A few papers of interest

• Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva Maximum Flow and Minimum-Cost Flow in Almost-Linear Time PDF: https://arxiv.org/abs/2203.00671

• Haotian Jiang: Minimizing Convex Functions with Integral Minimizers. SODA 2021: 976-985 PDF: https://arxiv.org/abs/2007.01445

• Nicholas J. A. Harvey: Matroid intersection, pointer chasing, and Young’s seminormal representation of Sn. SODA 2008: 542-549 PDF: https://dl-acm-org.focus.lib.kth.se/citation.cfm?id=1347142

• Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg: New Query Lower Bounds for Submodular Function Minimization. ITCS 2020: 64:1-64:16 PDF: https://arxiv.org/abs/1911.06889

• Yu Chen, Sanjeev Khanna, Ansh Nagda: Near-linear Size Hypergraph Cut Sparsifiers. FOCS 2020: 61-72 PDF: https://arxiv.org/abs/2009.04992

• Chandra Chekuri, Chao Xu: Minimum Cuts and Sparsification in Hypergraphs. SIAM J. Comput. 47(6): 2118-2156 (2018)

• Sagnik Mukhopadhyay, Danupon Nanongkai: Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms. CoRR abs/1911.01651 (2019) PDF: https://arxiv.org/abs/1911.01651

• S. Apers and T. Lee Quantum complexity of minimum cut. PDF: https://arxiv.org/abs/2011.09823

• Noam Nisan, Avi Wigderson: Rounds in Communication Complexity Revisited. SIAM J. Comput. 22(1): 211-219 (1993)

• Noam Nisan: The Demand Query Model for Bipartite Matching: SODA 2021: 592-599