A taxonomy of problems with fast parallel algorithms

Equivalence classes and conditional hardness in massively parallel computations

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the one cycle versus two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., P ≠ NP ), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems. In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by MPC ( o ( log N ) ) , and the standard space complexity classes L and NL , and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model. Specifically, our main results are as follows.Lower bounds conditioned on the one cycle versus two cycles conjecture can be instead argued under the L ⊈ MPC ( o ( log N ) ) conjecture: these two assumptions are equivalent, and refuting either of them would lead to o ( log N ) -round MPC algorithms for a large number of challenging problems, including list ranking, minimum cut, and planarity testing. In fact, we show that these problems and many others require asymptotically the same number of rounds as the seemingly much easier problem of distinguishing between a graph being one cycle or two cycles.Many lower bounds previously argued under the one cycle versus two cycles conjecture can be argued under an even more robust (thus harder to refute) conjecture, namely NL ⊈ MPC ( o ( log N ) ) . Refuting this conjecture would lead to o ( log N ) -round MPC algorithms for an even larger set of problems, including all-pairs shortest paths, betweenness centrality, and all aforementioned ones. Lower bounds under this conjecture hold for problems such as perfect matching and network flow.

Resilient Capacity-Aware Routing

To ensure a high availability, communication networks provide resilient routing mechanisms that quickly change routes upon failures. However, a fundamental algorithmic question underlying such mechanisms is hardly understood: how to verify whether a given network reroutes flows along feasible paths, without violating capacity constraints, for up to k link failures? We chart the algorithmic complexity landscape of resilient routing under link failures, considering shortest path routing based on link weights as e.g. deployed in the ECMP protocol. We study two models: a pessimistic model where flows interfere in a worst-case manner along equal-cost shortest paths, and an optimistic model where flows are routed in a best-case manner, and we present a complete picture of the algorithmic complexities. We further propose a strategic search algorithm that checks only the critical failure scenarios while still providing correctness guarantees. Our experimental evaluation on a benchmark of Internet and datacenter topologies confirms an improved performance of our strategic search by several orders of magnitude.

Automatic acoustic classification of insect species based on directed acyclic graphs

This work presents the design of a directed acyclic graph (DAG) scheme, the nodes of which incorporate hidden Markov models (HMMs) for classifying insect species. Such a DAG scheme is able to limit the problem space, while having the HMMs capture the temporal evolution of Mel-scaled spectrograms extracted out of wingbeat sounds. Interestingly, the proposed approach offers interpretability of the classification process by inspecting the sequence of edges activated in the DAG (path). The dataset encompasses 50 000 wingbeat sounds representing six species, i.e., Ae. aegypti (male and female), Cx. quinquefasciatus (male and female), Cx. stigmatosoma (male and female), Cx. tarsalis (male and female), Musca domestica, and Drosophila simulans, and is publicly available at https://sites.google.com/site/insectclassification/. Thorough species classification experiments showed that the proposed solution outperforms state-of-the-art approaches.