Friedhelm Meyer auf der Heide

TCS Journal 2023 Journal Article

Gathering a Euclidean closed chain of robots in linear time and improved algorithms for chain-formation

• Jannik Castenow
• Jonas Harbig
• Daniel Jung
• Till Knollmann
• Friedhelm Meyer auf der Heide

We consider formation problems for chains of disoriented, mobile robots with limited visibility operating in asynchronous rounds ( A sync). More precisely, we study the Chain-Formation and the Gathering problem. Chain-Formation considers a chain of robots between two stationary outer robots: Each inner robot has two identifiable neighbors, and the goal is to arrange the robots on the line segment connecting the outer robots. The Gathering problem considers a closed chain (without outer robots) and demands all robots to gather on a single, not predefined point. The robots move in the Euclidean plane and are luminous, i. e. , equipped with a light visible to the neighboring robots. At each point in time, the light can have one out of a constant number of colors. We introduce a family of algorithms inspired by the Hopper algorithm [1]. For the Chain-Formation problem, we modify the Hopper algorithm so that we can guarantee a ( 1 + ε ) -approximation to the optimal chain length (instead of a 2 -approximation). Our main result is an asymptotically optimal algorithm for Gathering of a closed chain of disoriented, luminous robots with limited visibility in the Euclidean plane. All algorithms have a worst-case optimal runtime of O ( n ).

I&C Journal 2022 Journal Article

A discrete and continuous study of the Max-Chain-Formation problem

• Jannik Castenow
• Peter Kling
• Till Knollmann
• Friedhelm Meyer auf der Heide

We introduce and study the Max-Chain-Formation problem, where n robots are ordered along a winding chain and must form a connected, straight line of maximal length connecting its two endpoints. We propose and analyze strategies in a discrete and a continuous time model. In the discrete case, we give a complete analysis if the positions of all robots are initially collinear, showing that the worst-case time to reach an ε-approximation is upper bounded by O ( n 2 ⋅ log ⁡ ( n / ε ) ) and lower bounded by Ω ( n 2 ⋅ log ⁡ ( 1 / ε ) ). In the non-collinear case, we identify a family of instances whose runtime is unbounded. The picture in the continuous case is different: we propose a strategy with an optimal runtime of Θ ( n ). Avoiding an unbounded runtime similar to the discrete case relies crucially on a counter-intuitive aspect: slowing down the endpoints while all other robots move at full speed.

TCS Journal 2022 Journal Article

Online facility location with mobile facilities

• Björn Feldkord
• Till Knollmann
• Friedhelm Meyer auf der Heide

We examine the Online Facility Location problem in an extended version. Fotakis showed a lower bound of Ω ( log ⁡ n log ⁡ log ⁡ n ) for the original Online Facility Location problem, where n is the number of clients. This bound holds even on the real line and for randomized algorithms against oblivious adversaries. We propose randomized online algorithms in the following setting: We consider the Euclidean space of arbitrary dimension and allow the facilities to either move arbitrarily or to move at most a constant distance m in each time step. The costs for moving a facility from a to b is D ⋅ d ( a, b ) where D ≥ 1 is a constant. Clients are assigned to facilities instantly and irreversibly. The cost for serving the clients is either calculated as soon as a client arrives or at the end of the computation. The algorithms for these two cost models achieve the same competitiveness on the line, which, in contrast to the original Online Facility Location problem, is independent of n. In the case of arbitrary movement, it only depends on D. In the case of a limited movement distance m, it additionally depends on m and the opening costs of the facilities. We show that our results are asymptotically tight on the real line. For the Euclidean space of higher dimensions, we give an algorithm for the model where costs for clients are evaluated immediately. The competitive ratio of our algorithm depends on the above parameters and additionally on the number of optimal facilities.

TCS Journal 2021 Journal Article

A continuous strategy for collisionless gathering

• Shouwei Li
• Christine Markarian
• Friedhelm Meyer auf der Heide
• Pavel Podlipyan

Over the past decades, the Gathering problem, which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O ( n d ) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i. e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art.

TCS Journal 2021 Journal Article

The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots

• Shouwei Li
• Friedhelm Meyer auf der Heide
• Pavel Podlipyan

In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O ( n 2 ) for gathering in two dimensions Euclidean space, and Θ ( n ) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i. e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this “collisionless property” of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the “collisionless property” holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center algorithms.

TCS Journal 2020 Journal Article

Gathering Anonymous, Oblivious Robots on a Grid

• Jannik Castenow
• Matthias Fischer
• Jonas Harbig
• Daniel Jung
• Friedhelm Meyer auf der Heide

We consider a swarm of n autonomous mobile robots distributed on a 2-dimensional grid. A basic task for such a swarm is to perform the gathering process: All robots have to gather at one not predefined place. On the grid there are configurations which, due to symmetry, cannot be gathered at a single point. Such configurations are 2 × 2 squares. Therefore, we say that the swarm is gathered if all robots are located inside of a 2 × 2 square. We assume the fully synchronous FSYNC time model and the following very simple so-called Basic&Plain robot model: The robots are oblivious, only have a constant viewing radius, are autonomous and indistinguishable, do not have a common compass, and cannot communicate. This implies that a robot's decision about its next action can only be based on the current relative positions of the robots in its viewing range. We consider connected swarms. We say two robots are connected if they are located in horizontally or vertically neighboring grid cells. We present the first gathering algorithm on the grid for this simple robot model and show that it gathers in time O ( n 2 ). Known algorithms for gathering on the grid need much stronger robot models: Either they have a common compass, or they have a finite memory and can communicate (via lights or flags) with robots in their viewing range. Finally, we extend our algorithm to the case where one of the robots is stationary, i. e. does not move.

TCS Journal 2019 Journal Article

Efficient parallel algorithms for parameterized problems

• Faisal N. Abu-Khzam
• Shouwei Li
• Christine Markarian
• Friedhelm Meyer auf der Heide
• Pavel Podlipyan

A parameterized problem is fixed-parameter parallelizable (FPP) if it can be solved in O ( f ( k ) ⋅ ( log ⁡ N ) α ) time using O ( g ( k ) ⋅ N β ) processors, where N is the input size, k is the parameter, f and g are arbitrary computable functions, and α, β are constants independent of N and k. We re-examine the k-vertex cover problem from a parameterized parallel complexity standpoint and present a parallel algorithm that outperforms the previous known algorithm: using O ( m ) instead of O ( n 2 ) processors, the running time improves from O ( k k ) to O ( k 3 log ⁡ n + 1. 2738 k ), where n and m are the number of vertices and edges of the input graph, respectively. This is achieved by first showing that vertex cover kernelization that is based on crown decomposition is in FPP as well. Finally, we consider the use of the recently introduced modular-width parameter. In particular, we show that the weighted maximum clique problem is FPP when parameterized by this auxiliary parameter.

TCS Journal 2013 Journal Article

Energy-efficient strategies for building short chains of mobile robots locally

• Philipp Brandes
• Bastian Degener
• Barbara Kempkes
• Friedhelm Meyer auf der Heide

We are given a winding chain of n mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. The goal is to let the robots converge to the line between the stations. The robots are modeled as points in the plane which cannot collide. We use a discrete and synchronous time model, but we restrict the movement of each mobile robot to a distance of δ in each round. This restriction fills the gap between the previously used discrete time model with an unbounded step length and the continuous time model which was introduced in [Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide, A continuous, local strategy for constructing a short chain of mobile robots, in: SIROCCO’10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, 2010, pp. 168–182]. We adapt the Go-To-The-Middle strategy by Dynia, Kutylowski, Lorek and Meyer auf der Heide (BICC 2006): In each round, each robot first observes the positions of its neighbors and then moves towards the midpoint between them until it reaches the point or has moved a distance of δ. The main energy consumers in this scenario are the number of observations of positions of neighbors, which equals the number of rounds, and the distance to be traveled by the robots. We analyze the strategy with respect to both quality measures and provide asymptotically tight bounds. We show that the best choice for δ for this strategy is δ ∈ Θ ( 1 n ), since this minimizes (up to constant factors) both energy consumers, the number of rounds as well as the maximum traveled distance, at the same time.

TCS Journal 2009 Journal Article

Optimal strategies for maintaining a chain of relays between an explorer and a base camp

• Jarosław Kutyłowski
• Friedhelm Meyer auf der Heide

We envision a scenario with robots moving on a terrain represented by a plane. A mobile robot, called explorer is connected by a communication chain to a stationary base camp. The chain is expected to pass communication messages between the explorer and the base camp. It is composed of simple, mobile robots, called relays. We are investigating strategies for organizing and maintaining the chain, so that the number of relays employed is minimized and nevertheless the distance between neighbored relays in the chain remains bounded. We are looking for local and distributed strategies employed by restricted relays that have to base their decision (“Where should I go? ”) solely on the relative positions of its neighbors in the chain. We present the Manhattan–Hopper and the Hopper strategy which improve the performance of all known solutions to this problem significantly. They are the first such strategies that are optimal in this setting, i. e. , that allow the explorer to move with constant speed, independent of the length of the chain, and keep this length minimum up to a constant factor.

MFCS Conference 2006 Conference Paper

Smart Robot Teams Exploring Sparse Trees

• Miroslaw Dynia
• Jaroslaw Kutylowski
• Friedhelm Meyer auf der Heide
• Christian Schindelhauer

Abstract We consider a tree which has to be completely explored by a group of k robots, initially placed at the root. The robots are mobile and can communicate using radio devices, but the communication range is bounded. They decide based on local, partial knowledge, and exchange information gathered during the exploration. There is no central authority which knows the graph and could control the movements of the robots – they have to organize themselves and jointly explore the tree. The problem is that at every point of time the remaining unknown part of the tree may appear to be the worst case setting for the current deployment of robots. We present a deterministic distributed algorithm to explore T and we use a parameter of a tree called density. We compare the performance of our algorithm with the optimal algorithm having a-priori knowledge of the same tree. We show that the above ratio is influenced only by the density and the height of the tree. Since the competitive ratio does not depend on the number of robots, our algorithm truly emphasizes the phenomena of self-organization. The more robots are provided, the faster the exploration of the terrain is completed.

MFCS Conference 2005 Invited Paper

Page Migration in Dynamic Networks

• Marcin Bienkowski
• Friedhelm Meyer auf der Heide

Abstract In the last couple of decades, network connected systems have gradually replaced centralized parallel computing machines. To provide smooth operation of network applications, the underlying system has to provide so-called basic services. One of the most crucial services is to provide a transparent access to data like variables, databases, memory pages, or. les, which are shared by the instances of programs running at nodes of the network.

SODA Conference 2000 Conference Paper

Caching in networks (extended abstract)

• Friedhelm Meyer auf der Heide
• Berthold Vöcking
• Matthias Westermann

STOC Conference 1998 Conference Paper

Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks

• Richard Cole 0001
• Bruce M. Maggs
• Friedhelm Meyer auf der Heide
• Michael Mitzenmacher
• Andréa W. Richa
• Klaus Schröder
• Ramesh K. Sitaraman
• Berthold Vöcking

TCS Journal 1998 Journal Article

Routing on networks of optical crossbars

• Friedhelm Meyer auf der Heide
• Klaus Schröder
• Frank Schwarze

We describe routing algorithms on networks composed of optical busses. Using networks with short busses and small degree we are able to give very fast routing algorithms. First, we describe a leveled optical network and a routing algorithm for it. Next, we show how to simulate this network on high-dimensional meshes of optical busses (MOBs). We present algorithms for routing, e. g. , h-relations with runtime being linear in h, doubly logarithmic in size and polynomial in the dimension of the mesh. Previous results are exponential in the dimension. E. g. , routing an h-relation on a d-dimensional MOB of size N requires O (d 5 log d log log N + d 3 h) steps, with high probability.

TCS Journal 1998 Journal Article

Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model

• Armin Bäumker
• Wolfgang Dittrich
• Friedhelm Meyer auf der Heide

In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP∗, that rewards blockwise communication, and use Valiant's notion of 1-optimality. Intuitively, a 1-optimal parallel algorithm for p processors achieves speed-up close to p. We consider the Multisearch Problem: Assume a strip in 2D to be partitioned into m segments. Given n query points in the strip, the task is to locate, for each query, its segment. For m ⩽n⩾ p we present a deterministic BSP∗ algorithm that is 1-optimal, if n p ⩾log2n. For m>n⩾p, we present a randomized BSP∗ algorithm that is l-optimal with high probability, if m⩽2 p and n/p⩾log 3 n. Both results hold for a wide range of BSP∗ parameters where the range becomes larger with growing input size n. We further report on implementation work. Previous parallel algorithms for Multisearch were far away from being 1-optimal in our model and did not consider blockwise communication.

FOCS Conference 1997 Conference Paper

Exploiting Locality for Data Management in Systems of Limited Bandwidth

• Bruce M. Maggs
• Friedhelm Meyer auf der Heide
• Berthold Vöcking
• Matthias Westermann

This paper deals with data management in computer systems in which the computing nodes are connected by a relatively sparse network. We consider the problem of placing and accessing a set of shared objects that are read and written from the nodes in the network. These objects are, e. g. , global variables in a parallel program, pages or cache lines in a virtual shared memory system, shared files in a distributed file system, or pages in the World Wide Web. A data management strategy consists of a placement strategy that maps the objects (possibly dynamically and with redundancy) to the nodes, and an access strategy that describes how reads and writes are handled by the system (including the routing). We investigate static and dynamic data management strategies.

I&C Journal 1997 Journal Article

Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures

• Artur Czumaj
• Friedhelm Meyer auf der Heide
• Volker Stemann

We consider randomized simulations of shared memory on a distributed memory machine (DMM) where thenprocessors and thenmemory modules of the DMM are connected via a reconfigurable architecture. We first present a randomized simulation of a CRCW PRAM on a reconfigurable DMM having a complete reconfigurable interconnection. It guarantees delay O (log*n), with high probability. Next we study a reconfigurable mesh DMM (RM-DMM). Here thenprocessors andnmodules are connected via ann×nreconfigurable mesh. It was already known that ann×mreconfigurable mesh can simulate in constant time ann-processor CRCW PRAM with shared memory of sizem. In this paper we present a randomized step by step simulation of a CRCW PRAM with arbitrarily large shared memory on an RM-DMM. It guarantees constant delay with high probability, i. e. , it simulates in real time. Finally we prove a lower bound showing that sizeΩ(n 2) for the reconfigurable mesh is necessary for real time simulations.

STOC Conference 1996 Conference Paper

A Lower Bound for Randomized Algebraic Decision Trees

• Dima Grigoriev
• Marek Karpinski
• Friedhelm Meyer auf der Heide
• Roman Smolensky

FOCS Conference 1996 Conference Paper

Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols

• Friedhelm Meyer auf der Heide
• Christian Scheideler

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of size n, the routing number of H is defined as the maximum over all permutations /spl pi/ on [n] of the minimal number of steps to route /spl pi/ offline in H. We can show that for any network H of size n with routing number R our protocol needs O(log/sub R/ n/spl middot/R) time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular our result yields optimal deterministic routing protocols for arbitrary networks with diameter /spl Omega/(n/sup /spl epsiv//) or bisection width O(n/sup 1-/spl epsiv//), /spl epsiv/>0 constant. Furthermore we can extend our result to deterministic compact routing. This yields, e. g. , a deterministic routing protocol with runtime O((log n)/(log log n) R) for arbitrary bounded degree networks if only O(log n) bits are available at each node for storing routing information. Our proofs use a new protocol for routing arbitrary r/spl middot/s-relations in r-replicated s-ary Multibutterflies in optimal time O(log, n).

TCS Journal 1996 Journal Article

Exploiting storage redundancy to speed up randomized shared memory simulations

• Friedhelm Meyer auf der Heide
• Christian Scheideler
• Volker Stemann

Assume that a set U of memory locations is distributed among n memory modules, using some number a of hash functions h 1, …, h a, randomly and independently drawn from a high-performance universal class of hash functions. Thus, each memory location has a copies. Consider the task of accessing b out of the a copies for each of given keys x 1, …, x n ∈ U, b < a. The paper presents and analyses a simple process executing the above task on distributed memory machines (DMMs) with n processors. Efficient implementations are presented, implying - a simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n), - a simulation as above on an arbitrary-DMM with delay O( log log n log log log n ), - an implementation of a static dictionary on an arbitrary-DMM with parallel access time O( log∗ n + log log n log a ), if a hash functions are used. In particular, an access time of O(log∗ n) can be reached if (log n) 1 log∗ n hash functions are used. We further prove a lower bound for executing the above process by any so-called simple access protocol, showing that our implementations are optimal.

STOC Conference 1996 Conference Paper

Universal Algorithms for Store-and-Forward and Wormhole Routing

• Robert Cypher
• Friedhelm Meyer auf der Heide
• Christian Scheideler
• Berthold Vöcking

STOC Conference 1992 Conference Paper

Efficient PRAM Simulation on a Distributed Memory Machine

• Richard M. Karp
• Michael Luby
• Friedhelm Meyer auf der Heide

MFCS Conference 1990 Invited Paper

Dynamic Hashing Strategies

• Friedhelm Meyer auf der Heide

Abstract This survey paper describes new types of dynamic hashing strategies for implementing dictionaries on sequential, parallel and distributed computation models. In particular, it surveys the progress in constructing and analyzing new classes of universal hash functions.

STOC Conference 1990 Conference Paper

How to Distribute a Dictionary in a Complete Network

• Martin Dietzfelbinger
• Friedhelm Meyer auf der Heide

STOC Conference 1990 Conference Paper

Not All Keys Can Be Hashed in Constant Time (Preliminary Version)

• Joseph Gil
• Friedhelm Meyer auf der Heide
• Avi Wigderson

MFCS Conference 1990 Conference Paper

On the Complexity of Genuinely Polynomial Computation

• Marek Karpinski
• Friedhelm Meyer auf der Heide

Abstract We present separation results on genuinely (or strongly) time bounded sequential, parallel and nondeterministic complexity classes defined by RAMs with fixed set of arithmetic operations. In particular, we separate non-uniform polynomial time from non-uniform parallel polynomial time for the set of operations {+, −, *} (answering a question of [M 88]), and uniform deterministic polynomial time from uniform nondeterministic polynomial time for the set of operations {t+, −, DIV c }, where DIV c denotes a restricted integer division operation.

TCS Journal 1988 Journal Article

A tradeoff between search and update time for the implicit dictionary problem

• Allan Borodin
• Faith E. Fich
• Friedhelm Meyer auf der Heide
• Eli Upfal
• Avi Wigderson

This paper proves a tradeoff between the time it takes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time is Ω(nε) for some constant ε>0.

FOCS Conference 1988 Conference Paper

Dynamic Perfect Hashing: Upper and Lower Bounds

• Martin Dietzfelbinger
• Anna R. Karlin
• Kurt Mehlhorn
• Friedhelm Meyer auf der Heide
• Hans Rohnert
• Robert Endre Tarjan

A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Omega (log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Omega (kn/sup 1/k/). >

I&C Journal 1988 Journal Article

On the limits of computations with the floor function

• László Babai
• Bettina Just
• Friedhelm Meyer auf der Heide

Up to now, few models of computation with the power of evaluating discontinuous functions have been analyzed and few of their lower bounds or results on the decidability of languages are known. In this paper, we present a model of an “analytic computation tree” (ACT). These trees operate on real numbers and are able to compare real numbers, to evaluate functions on real numbers, and to evaluate certain discontinuous functions like the “floor function. ” This model generalizes the model of “algebraic computation trees” introduced by Ben Or. We show by topological arguments that by ACTs one cannot decide certain classes of languages, examples of which are Q n and the set of tuples (x1, …, xn ) ∈ R n that have components which are Z -linearly or algebraically dependent.

STOC Conference 1985 Conference Paper

Fast Algorithms for N-Dimensional Restrictions of Hard Problems

• Friedhelm Meyer auf der Heide

Let M be a parallel RAM with p processors and arithmetic operations addition and subtraction recognizing L ⊂ N n in t steps. Then L can be recognized by a (sequential!) linear search algorithm (LSA) in Ο( n 4 (log( n ) + t + log( p ))) steps. Thus many n-dimensional restrictions of NP-complete problems (binary programming, traveling salesman problem, etc.) and even that of the uniquely optimum traveling salesman problem, which is Δ P 2 -complete, can be solved in polynomial time by an LSA. This result generalizes the construction of a polynomial LSA for the n-dimensional restriction of the knapsack problem previously shown by the author, and destroys the hope of proving nonpolynomial lower bounds for any problem which can be recognized by a PRAM as above with 2 poly(n) processors in poly(n) time.

FOCS Conference 1985 Conference Paper

Nondeterministic versus Probabilistic Linear Search Algorithms

• Friedhelm Meyer auf der Heide

The "component counting lower bound" known for deterministic linear search algorithms (LSA's) also holds for their probabilistic versions (PLSA's) for many problems, even if two-sided error is allowed, and if one does not charge for probabilistic choice. This implies lower bounds on PLSA's for e. g. the element distinctness problem (n log n) or the knapsack problem (n2). These results yield the first separations between probabilistic and non-deterministic LSA's, because the above problems are non-deterministically much easier. Previous lower bounds for PLSA's either only worked for one-sided error "on the nice side", i. e. on the side where the problems are even non-deterministically hard, or only for probabilistic comparison trees. The proof of the lower bound differs fundamentally from all known lower bounds for LSA's or PLSA's, because it does not reduce the problem to a combinatorial one but argues extensively about e. g. a non-discrete measure for similarity of sets in Rn. This lower bound result solves an open problem posed by Manber and Tompa as well as by Snir. Furthermore, a PLSA for n input variables with two-sided error and expected runtime T can be simulated by a (deterministic) LSA in T2n steps. This proves that the gaps between probabilistic and deterministic LSA's shown by Snir cannot be too large. As this simulation even holds for algebraic computation trees we show that probabilistic and deterministic versions of this model are polynomially related. This is a weaker version of a result due to the author which shows that in case of LSA's, even the non-deterministic and deterministic versions are polynomially related.

STOC Conference 1985 Conference Paper

One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation

• Faith Ellen
• Friedhelm Meyer auf der Heide
• Prabhakar Ragde
• Avi Wigderson

In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRIORITY PRAM. These models differ in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds.

TCS Journal 1985 Journal Article

Simulating probabilistic by deterministic algebraic computation trees

• Friedhelm Meyer auf der Heide

A probabilistic algebraic computation tree (probabilistic ACT) which recognizes L ⊂ R n in expected time T, and which gives the wrong answer with probability ⩽ ϵ < 1 2, can be simulated by a deterministic ACT in O(T 2 n) steps. The same result holds for linear search algorithms (LSAs). The result for ACTs establishes a weaker version of results previously shown by the author for LSAs, namely that LSAs can only be slightly sped up by their nondeterministic versions. This paper shows that ACTs can only be slightly sped up by their probabilistic versions. The result for LSAs solves a problem posed by Snir (1983). He found an example where probabilistic LSAs are faster than deterministic ones and asked how large this gap can be.

FOCS Conference 1985 Conference Paper

The Complexity of Parallel Sorting

• Friedhelm Meyer auf der Heide
• Avi Wigderson

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 integers with n processors requires Ω(√log n) steps in this strong model. We also show that computing any symmetric polynomial (e. g. the sum or product) of n integers requires exactly log2n steps, for any finite number of processors.

FOCS Conference 1984 Conference Paper

On the Limits to Speed Up Parallel Machines by Large Hardware and Unbounded Communication

• Friedhelm Meyer auf der Heide
• Rüdiger Reischuk

Lower bounds for sequential and parallel random access machines (RAM's, WRAM's) and distributed systems of RAM's (DRAM's) are proved. We show that, when p processors instead of one are available, the computation of certain functions cannot be speeded up by a factor p but only by a factor 0 (log(p)). For DRAM's with communication graph of degree c a maximal speedup 0 (log(c)) can be achieved for these problems. We apply these results to testing the solvability of linear diophantine equations. This generalizes a lower bond of Yao for parallel computation trees. Improving results of Dobkin/Lipton and Klein/Meyer auf der Heide, we establish large lower bounds for the above problem on RAM's. Finnaly we prove that at least log (n) + 1 steps are necessary for computing the sum of n integers by a WRAM regardless of the number of processors and the solution of write conflicts.

STOC Conference 1983 Conference Paper

A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem

• Friedhelm Meyer auf der Heide

TCS Journal 1981 Journal Article

A comparison of two variations of a pebble game on graphs

• Friedhelm Meyer auf der Heide

The number of pebbles used in the black [black-white] pebble game corresponds to the storage requirement of the deterministic [non-deterministic] evaluation of a straight line program. Suppose a distinguished vertex of a directed acyclic graph can be pebbled with k pebbles in the black-white pebble game. Then it can be pebbled with k′≤1/2k(k−1)+1 pebbles in the black pebble game.

MFCS Conference 1981 Conference Paper

Time-Processor Trade-offs for Universal Parallel Computers

• Friedhelm Meyer auf der Heide

Abstract Various kinds of simulations among parallel computers are considered. We prove that it is not possible to simulate all parallel computers by one without an additional expense of time or of processors. Then we present a parallel computer which can simulate all parallel computers with n processors and which needs c·n 2 log(n) processors and extends the time only by a factor d·log log(n).