Partitionierungen Und Komplexität, Matthias Ruhl, Mathematische Fakultät, Prof Dr, Dietmar Saupe, ...
Optimal Fractal Coding is NP-Hard 1 (Extended Abstract) (2008)
Matthias Ruhl, Hannes Hartenstein
In fractal compression a signal is encoded by the parameters of a contractive transformation whose fixed point (attractor) is an approximation of the original data. Thus fractal coding can be viewed...
Optimal Fractal Coding is NP-Hard 1 (Extended Abstract) (2008)
Matthias Ruhl, Hannes Hartenstein
In fractal compression a signal is encoded by the parameters of a contractive transformation whose fixed point (attractor) is an approximation of the original data. Thus fractal coding can be viewed...
Abstract Parallel Processor Scheduling with Delay Constraints (2008)
Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on...
Abstract Secure Notarization of Paper Text Documents (2008)
Matthias Ruhl, Marshall Bern, David Goldberg
We present a method to notarize a paper document. This method computes a set of features from the page, inputs these features into a hash function, digitally signs the output, and then prints the...
Extending the Streaming Model: Sorting and Streaming Networks (2008)
Matthias Ruhl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan
The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. One such model is “streaming computations...
Extending the Streaming Model: Sorting and Streaming Networks (2008)
Matthias Ruhl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan
The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. One such model is “streaming computations...
Hannes Hartenstein, Matthias Ruhl, Dietmar Saupe
EDICS number: 1-STIL Abstract: A fractal coder partitions an image into blocks that are coded via self-references to other parts of the image itself. In this paper we present a fractal coder that...
Dietmar Saupe, Matthias Ruhl, Raouf Hamzaoui, Luigi Grandi, Daniele Marini
In fractal image compression a partitioning of the image is required. In this paper we discuss the construction of rate-distortion optimal partitions. We begin with a fine scale partition which gives...
Optimal Fractal Coding is NP-Hard 1 (Extended Abstract) (2007)
Matthias Ruhl, Hannes Hartenstein
In fractal compression a signal is encoded by the parameters of a contractive transformation whose fixed point (attractor) is an approximation of the original data. Thus fractal coding can be viewed...
Abstract We consider the DIRECTED STEINER NETWORK problem, (2007)
also called the POINT-TO-POINT CONNECTION problem, where given a directed graph G and p pairs f(s 1; t 1); : : : ; (s p; t p)g of nodes in the graph, one has to find the smallest subgraph H of G that...
Hannes Hartenstein, Matthias Ruhl, Dietmar Saupe, Edward R. Vrscay
Abstract. The inverse problem of fractal compression amounts to determining a contractive operator such that the corresponding xed point approximates a given target function. The standard method...
Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems (2004)
David R. Karger, Matthias Ruhl
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give two new loadbalancing protocols whose provable performance guarantees are within a constant factor of...
Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (2004)
David R. Karger, Matthias Ruhl
In most of the P2P systems developed so far, all nodes play essentially the same role. In some applications, however, different machine capabilities or owner preferences may mean that only a subset...
Diminished Chord: A protocol for heterogeneous subgroup formation in peer-to-peer networks (2004)
David R. Karger, Matthias Ruhl
Abstract. In most of the P2P systems developed so far, all nodes play essentially the same role. In some applications, however, different machine capabilities or owner preferences may mean that only...
Combinatorial Problems on Strings with Applications to Protein Folding (2004)
Abstract. We consider the problem of protein folding in the HP model on the 3D square lattice. This problem is combinatorially equivalent to folding a string of 0’s and 1’s so that the string...
Diminished Chord: A protocol for heterogeneous subgroup formation in peer-to-peer networks (2004)
David R. Karger, Matthias Ruhl
Abstract. In most of the P2P systems developed so far, all nodes play essentially the same role. In some applications, however, different machine capabilities or owner preferences may mean that only...
Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems (2004)
David R. Karger, Matthias Ruhl
Abstract. Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give two new load-balancing protocols whose provable performance guarantees are within a constant...
Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems (2004)
David R. Karger, Matthias Ruhl
Load balancing is a critical issue for the efficient operation of peerto-peer networks. We give two new load-balancing protocols whose provable performance guarantees are within a constant factor of...
New Algorithms for Load Balancing in Peer-to-Peer Systems (2003)
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant...
New Algorithms for Load Balancing in Peer-to-Peer Systems (2003)
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant...
New Algorithms for Load Balancing in Peer-to-Peer Systems (2003)
David R. Karger, Matthias Ruhl
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant...
New Algorithms for Load Balancing in Peer-to-Peer Systems (2003)
David R. Karger, Matthias Ruhl
Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant...
Finding Nearest Neighbors in Growth-restricted Metrics (2002)
David R. Karger, Matthias Ruhl
Most research on nearest neighbor algorithms in the literature has been focused on the Euclidean case. In many practical search problems however, the underlying metric is non-Euclidean. Nearest...
Parallel processor scheduling with delay constraints (2001)
Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on...
Secure notarization of paper text documents (2001)
Matthias Ruhl, Marshall Bern, David Goldberg
We present a method to notarize a paper document. This method computes a set of features from the page, inputs these features into a hash function, digitally signs the output, and then prints the...
Orderings and PTIME – On a Conjecture by Makowsky (2001)
Immerman and Vardi showed in the early 1980s that the logic LFP, augmented with an ordering, can express all PTIME-decidable properties. In 1997, Makowsky conjectured that LFP+A, i.e. LFP augmented...
Orderings and PTIME – On a Conjecture by Makowsky (2001)
Immerman and Vardi showed in the early 1980s that the logic LFP, augmented with an ordering, can express all PTIME-decidable properties. In 1997, Makowsky conjectured that LFP+A, i.e. LFP augmented...
Parallel processor scheduling with delay constraints (2001)
Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl
We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on...
Anonymous Subscription Protocols (2000)
Zulfikar Ramzan, Matthias Ruhl
In this paper we discuss protocols that allow a user to subscribe to an electronic service, and then anonymously access the service. That is, the provider does not know who accesses the service at...
Protocols for Anonymous Subscription Services (2000)
Zulfikar Ramzan, Matthias Ruhl
In this paper we discuss protocols that allow a user to subscribe to an electronic service, and then anonymously access the service. That is, neither the service provider nor anyone else knows who...
Region-Based Fractal Image Compression (2000)
Hannes Hartenstein, Associate Member, Matthias Ruhl, Dietmar Saupe
Abstract—A fractal coder partitions an image into blocks that are coded via self-references to other parts of the image itself. In this paper we present a fractal coder that derives highly...
Protocols for Anonymous Subscription Services (2000)
Zulfikar Ramzan, Matthias Ruhl
In this paper we discuss protocols that allow a user to subscribe to an electronic service, and then anonymously access the service. That is, neither the service provider nor anyone else knows who...
The Directed Steiner Network problem is tractable for a constant number of terminals (1999)
We consider the DIRECTED STEINER NETWORK problem, also called the POINT-TO-POINT CONNECTION problem, where given a directed graph G and p pairs f(s 1 ; t 1 ); : : : ; (s p ; t p )g of nodes in the...
Counting and Addition cannot express Deterministic Transitive Closure (1999)
An important open question in complexity theory is whether the circuit complexity class TC 0 is (strictly) weaker than LOGSPACE. This paper considers this question from the viewpoint of descriptive...
GM-Security and Semantic Security Revisited (1999)
We give a simple proof that GM-security and semantic security are equivalent security notions for public key cryptosystems. By this we drastically simplify the original proof given by Goldwasser,...
The directed steiner network problem is tractable for a constant number of terminals (1999)
We consider the DIRECTED STEINER NETWORK problem, also called the POINT-TO-POINT CONNECTION problem, where given a directed graph G and p pairs s1 t1 sp tp of nodes in the graph, one has to find the...
Optimal Hierarchical Partitions For Fractal Image Compression (1998)
Dietmar Saupe, Matthias Ruhl, Raouf Hamzaoui, Luigi Grandi, Daniele Marini
In fractal image compression a partitioning of the image is required. In this paper we discuss the construction of rate-distortion optimal partitions. We begin with a fine scale partition which gives...
Optimal hierarchical partitions for fractal image compression (1998)
Dietmar Saupe, Matthias Ruhl, Raouf Hamzaoui, Luigi Gr, Daniele Marini
In fractal image compression a partitioning of the image is required. In this paper we discuss the construction of rate-distortion optimal partitions. We begin with a fine scale partition which gives...
Adaptive partitionings for fractal image compression (1997)
Matthias Ruhl, Hannes Hartenstein, Dietmar Saupe
In fractal image compression a partitioning of the image into ranges is required. In our previous work [1] we have proposed to find good partitionings by means of a split-andmerge process guided by...
Adaptive partitionings for fractal image compression (1997)
Matthias Ruhl, Hannes Hartenstein, Dietmar Saupe
In fractal image compression a partitioning of the image into ranges is required. In our previous work [1] we have proposed to find good partitionings by means of a split-andmerge process guided by...
Optimal Fractal Coding is NP-Hard (Extended Abstract) (1997)
Matthias Ruhl, Hannes Hartenstein
) Matthias Ruhl, Hannes Hartenstein Institut fur Informatik, Universitat Freiburg Am Flughafen 17, 79110 Freiburg, Germany ruhl,hartenst@informatik.uni-freiburg.de Abstract In fractal compression a...
Adaptive Partitionings for Fractal Image Compression (1997)
Matthias Ruhl, Hannes Hartenstein, Dietmar Saupe
In fractal image compression a partitioning of the image into ranges is required. In our previous work [1] we have proposed to find good partitionings by means of a split-andmerge process guided by...
Fraktale Bildkompression: Adaptive (1997)
Partitionierungen Und Komplexität, Matthias Ruhl, Mathematische Fakultät, Prof Dr, Dietmar Saupe, ...
Adaptive partitionings for fractal image compression (1997)
Matthias Ruhl, Hannes Hartenstein, Dietmar Saupe
In fractal image compression a partitioning of the image into ranges is required. In our previous work [1] we have proposed to find good partitionings by means of a split-andmerge process guided by...
Interactive visualization of implicit surfaces with singularities (1996)
Angela Rosch, Matthias Ruhl, Dietmar Saupe
This paper presents work on two methods for interactive visualization of implicit surfaces: physically-based sampling using particle systems and polygonization followed by physically-based mesh...
Evolutionary Fractal Image Compression (1996)
This paper introduces evolutionary computing to fractal image compression. In fractal image compression [1] a partitioning of the image into ranges is required. We propose to use evolutionary...
Interactive Visualization of Implicit Surfaces with Singularities (1996)
Angela Rösch, Matthias Ruhl, Dietmar Saupe
This paper presents work on two methods for interactive visualization of implicit surfaces: physicallybased sampling using particle systems and polygonization followed by physically-based mesh...
Interactive visualization of implicit surfaces with singularities (1996)
Angela Rösch, Matthias Ruhl, Dietmar Saupe
This paper presents work on two methods for interactive visualization of implicit surfaces: physically-based sampling using particle systems and polygonization followed by physically-based mesh...
Evolutionary fractal image compression (1996)
This paper introduces evolutionary computing to fractal image compression. In fractal image compression [1] a partitioning of the image into ranges is required. We propose to use evolutionary...