Shared memory models of parallel computation (eg, parallel RAMs) that allow simultaneous
read/write access are very natural and already widely used for parallel algorithm design …

We show that if a flow network haskinput/output terminals (for the traditional maximum-flow
problem, k= 2), its external flow pattern (the possible values of flow into and out of the …

Boolean network models of molecular regulatory networks have been used successfully in
computational systems biology. The Boolean functions that appear in published models tend …

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC'87 and J.
ACM'96), is a technique for hiding RAM's access pattern. That is, for every input the …

We give fast randomized and deterministic parallel methods for constructing convex hulls in
R/sup d/, for any fixed d. Our methods are for the weakest shared-memory model, the EREW …

The properties of random Boolean networks have been investigated extensively as models
of regulation in biological systems. However, the Boolean functions (BFs) specifying the …

Most complexity measures for concurrent algorithms for asynchronous shared-memory
architectures focus on process steps and memory consumption. In practice, however …

Sensitivity vs. block sensitivity of Boolean functions Page 1 COMBINATORICA Akad~miai Kiad5
- Springer-Verlag COMBINATORICA 15 (2) (1995) 297--299 NOTE SENSITIVITY VS. BLOCK …

The representative random sample is a central concept of statistics. It is often possible to
gather a great deal of information about a large population by examining a small sample …

Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding
the connected components of a graph G=(V, E) with n vertices and m edges in O (log n) time …