Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
In prior work, Gupta et al.(SPAA 2022) presented a distributed algorithm for multiplying
sparse $ n\times n $ matrices, using $ n $ computers. They assumed that the input matrices …
sparse $ n\times n $ matrices, using $ n $ computers. They assumed that the input matrices …
Oblivious parallel tight compaction
In tight compaction, one is given an array of balls some of which are marked 0 and the rest
are marked 1. The output of the procedure is an array that contains all of the original balls …
are marked 1. The output of the procedure is an array that contains all of the original balls …
Connected components on a PRAM in log diameter time
We present an O (log d+ log logm/nn)-time randomized PRAM algorithm for computing the
connected components of an n-vertex, m-edge undirected graph with maximum component …
connected components of an n-vertex, m-edge undirected graph with maximum component …
Optimal convex hull algorithms on enhanced meshes
S Olariu, JL Schwing, J Zhang - BIT Numerical Mathematics, 1993 - Springer
In this paper we propose time-optimal convex hull algorithms for two classes of enhanced
meshes. Our first algorithm computes the convex hull of an arbitrary set of n points in the …
meshes. Our first algorithm computes the convex hull of an arbitrary set of n points in the …
[PS][PS] Mathematical techniques for the analysis of Boolean functions
A Bernasconi - BULLETIN-EUROPEAN ASSOCIATION FOR …, 1998 - pages.di.unipi.it
Any attempt to nd connections between mathematical properties of functions and their
computational complexity has a strong relevance to theory of computation. Indeed, there is …
computational complexity has a strong relevance to theory of computation. Indeed, there is …
Parallel shortcutting of rooted trees
M Thorup - Journal of Algorithms, 1997 - Elsevier
First it is shown that for any rooted treeTwithnvertices, and parameterm≥ n, there is a
“shortcutting” setSof at mostmarcs from the transitive closureT* ofTsuch for any (v, w)∈ T …
“shortcutting” setSof at mostmarcs from the transitive closureT* ofTsuch for any (v, w)∈ T …
The complexity of parallel sorting
FM auf der Heide, A Wigderson - 26th Annual Symposium on …, 1985 - ieeexplore.ieee.org
We consider PRAM's with arbitrary computational power for individual processors, infinitely
large shared memory and" priority" writeconflict resolution. The main result is that sorting n …
large shared memory and" priority" writeconflict resolution. The main result is that sorting n …
Simple concurrent connected components algorithms
We study a class of simple algorithms for concurrently computing the connected components
of an n-vertex, m-edge graph. Our algorithms are easy to implement in either the …
of an n-vertex, m-edge graph. Our algorithms are easy to implement in either the …
Flexibility of boolean network reservoir computers in approximating arbitrary recursive and non-recursive binary filters
Reservoir computers (RCs) are biology-inspired computational frameworks for signal
processing that are typically implemented using recurrent neural networks. Recent work has …
processing that are typically implemented using recurrent neural networks. Recent work has …
Efficient self-simulation algorithms for reconfigurable arrays
Y Benasher, D Gordon, A Schuster - Journal of Parallel and Distributed …, 1995 - Elsevier
There are several reconfiguring-network models of parallel computation that are considered
in the published literature, depending on their switching capabilities. Can these …
in the published literature, depending on their switching capabilities. Can these …