In the last decade or so we have witnessed a growing interest in processing large data sets
on large distributed clusters. The idea was pioneered by the MapReduce framework, and …

This paper resolves a long-standing open problem on whether the concurrent write
capability of parallel random access machine (PRAM) is essential for solving fundamental …

1. Introduction It is commonly agreed that the class NC contains exactly all the problems that
are amenable to parallel computation. It corresponds to the class P of the problems with …

Assume each processor in a network has some piece of information. We study how
efficiently information can be spread in a communication network. Specifically, we …

In this paper, a parallel algorithm for finding the connected components of an undirected
graph is presented. On a graph with n vertices and m edges, the algorithm runs in O (log n …

We consider the two-point query version of the fundamental geometric shortest path
problem: Given a set h of polygonal obstacles in the plane, having a total of n vertices, build …

We present a general and efficient strategy for computing mtustly on unreliable parallel
machines. The model of a parallel machine that we use is a CRCW PRAM with dynamic …

Inspired by the Elitzur-Vaidman bomb testing problem [arXiv: hep-th/9305002], we introduce
a new query complexity model, which we call bomb query complexity $ B (f) $. We …

We design an algorithm for finding counterfactuals with strong theoretical guarantees on its
performance. For any monotone model $ f: X^ d\to\{0, 1\} $ and instance $ x^\star $, our …

Sensitivity is one of the simplest, and block sensitivity one of the most useful, invariants of a
boolean function. Nisan [SIAM J. Comput. 20 (6)(1991) 999] and Nisan and Szegedy …