Matthias Ruhl's Publications

Journals

Jon Feldman, Matthias Ruhl, The Directed Steiner Network problem is tractable for a constant number of terminals, SIAM Journal on Computing, vol. 36, no. 2, pp. 543-561, 2006.

David R. Karger, Matthias Ruhl, Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems, Theory of Computing Systems (SPAA'04 special issue), vol. 39, no. 6, pp. 787-804, November 2006.

Hannes Hartenstein, Matthias Ruhl, Dietmar Saupe, Region Based Fractal Image Compression, IEEE Transactions on Image Processing, vol. 9, no. 7, pp. 1171-1184, July 2000.
[PDF, 356KB]

Angela Rösch, Matthias Ruhl, Dietmar Saupe, Interactive Visualization of Implicit Surfaces with Singularities, Eurographics Computer Graphics Forum, vol. 16, no. 5, pp. 295-306, December 1997.
[Compressed Postscript, 895KB] [PDF, 1493KB]

Conference Proceedings

Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl, On the Streaming Model Augmented with a Sorting Primitive, Proceedings IEEE Symposium on Foundations of Computer Science (FOCS), Rome, October 2004.
[Postscript, 143KB] [Compressed Postscript, 53KB] [PDF, 102KB]

David R. Karger, Matthias Ruhl, Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems, Proceedings ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, June 2004.
[Postscript, 152KB] [Compressed Postscript, 58KB] [PDF, 79KB]

Alantha Newman, Matthias Ruhl, Combinatorial Problems on Strings with Applications to Protein Folding, Proceedings Latin American Theoretical INformatics (LATIN), Buenos Aires, pp. 369-378, April 2004.
[Postscript, 357KB] [Compressed Postscript, 153KB] [PDF, 195KB]

David R. Karger, Matthias Ruhl, Finding Nearest Neighbors in Growth-restricted Metrics, Proceedings ACM Symposium on Theory of Computing (STOC), Montréal, pp. 741-750, May 2002.
[Postscript, 165KB] [Compressed Postscript, 58KB] [PDF, 145KB]

Krishna Bharat, Bay-Wei Chang, Monika Henzinger, Matthias Ruhl, Who Links to Whom: Mining Linkage between Web Sites, Proceedings IEEE International Conference on Data Mining (ICDM), San Jose, pp. 51-58, November 2001.
[Postscript, 2321KB] [Compressed Postscript, 290KB] [PDF, 1338KB]

Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl, Parallel Processor Scheduling with Delay Constraints, Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington D.C., pp. 577-585, January 2001.
[Postscript, 154KB] [Compressed Postscript, 50KB] [PDF, 83KB]

Matthias Ruhl, Marshall Bern, David Goldberg, Secure Notarization of Paper Text Documents, Proceedings ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington D.C., pp. 437-438, January 2001.
[Postscript, 32KB] [Compressed Postscript, 14KB] [PDF, 29KB]

Jon Feldman, Matthias Ruhl, The Directed Steiner Network problem is tractable for a constant number of terminals, Proceedings IEEE Symposium on Foundations of Computer Science (FOCS), New York, pp. 299-308, October 1999.
[Postscript, 226KB] [Compressed Postscript, 76KB] [PDF, 170KB]

Matthias Ruhl, Counting and Addition cannot express Deterministic Transitive Closure, Proceedings IEEE Symposium on Logic in Computer Science (LICS), Trento, pp. 326-334, July 1999.
[Postscript, 155KB] [Compressed Postscript, 57KB] [PDF, 143KB]

Dietmar Saupe, Matthias Ruhl, Raouf Hamzaoui, Luigi Grandi, Daniele Marini, Optimal hierarchical partitions for fractal image compression, Proceedings IEEE International Conference on Image Processing (ICIP), Chicago, vol. 1, pp. 737-741, October 1998.
[Postscript, 125KB] [Compressed Postscript, 39KB] [PDF, 100KB]

Matthias Ruhl, Hannes Hartenstein, Dietmar Saupe, Adaptive partitionings in fractal image compression, Proceedings IEEE International Conference on Image Processing (ICIP), Santa Barbara, vol. 2, pp. 310-313, October 1997.
[Postscript, 2129KB] [Compressed Postscript, 347KB] [PDF, 429KB]

Dietmar Saupe, Matthias Ruhl, Animation of Algebraic Surfaces, Visualization and Mathematics, H.-C. Hege, K. Polthier (eds.), Springer Verlag, pp. 83-92, July 1997.
[Compressed Postscript, 3410KB]

Matthias Ruhl, Hannes Hartenstein, Optimal Fractal Coding is NP-Hard, Proceedings DCC'97 Data Compression Conference, James A. Storer, Martin Cohn (eds.), IEEE Computer Society Press, pp. 261-270, March 1997.
[Postscript, 225KB] [Compressed Postscript, 48KB] [PDF, 154KB]

Dietmar Saupe, Matthias Ruhl, Evolutionary fractal image compression, Proceedings IEEE International Conference on Image Processing (ICIP), Lausanne, vol. 1, pp. 129-132, September 1996.
[Postscript, 656KB] [Compressed Postscript, 271KB] [PDF, 359KB]

Workshops

David R. Karger, Matthias Ruhl, Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems, International Workshop on Peer-to-Peer Systems (IPTPS), San Diego, February 2004.
[Postscript, 237KB] [Compressed Postscript, 110KB] [PDF, 137KB]

David R. Karger, Matthias Ruhl, Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks, International Workshop on Peer-to-Peer Systems (IPTPS), San Diego, February 2004.
[Postscript, 230KB] [Compressed Postscript, 104KB] [PDF, 132KB]

David R. Karger, Matthias Ruhl, New Algorithms for Load Balancing in Peer-to-Peer Systems, IRIS Student Workshop (ISW), Cambridge, MA, August 2003.
[Postscript, 51KB] [Compressed Postscript, 21KB] [PDF, 37KB]

Matthias Ruhl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Extending the Streaming Model: Sorting and Streaming Networks, DIMACS Working Group Meeting on Streaming Data Analysis, March 2003.
[Postscript, 21KB] [Compressed Postscript, 9KB] [PDF, 12KB]

Dietmar Saupe, Matthias Ruhl, Interactive Animation of Algebraic Surfaces, Proceedings Workshop "Visualisierung - Dynamik und Komplexität", Bremen, September 1995.

Technical Reports

David R. Karger, Matthias Ruhl, New Algorithms for Load Balancing in Peer-to-Peer Systems, MIT Technical Report, LCS-TR-911, July 2003.
[Postscript, 265KB] [Compressed Postscript, 103KB] [PDF, 243KB]

Book Chapters

Hannes Hartenstein, Matthias Ruhl, Dietmar Saupe, Edward R. Vrscay, On the Inverse Problem of Fractal Compression, in: "Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems", Bernold Fiedler (ed.), Springer Verlag, pp. 617-647, August 2001.
[Compressed Postscript, 560KB]

Theses

Matthias Ruhl, Efficient Algorithms for New Computational Models, PhD Thesis in Electrical Engineering and Computer Science, Massachusetts Institute of Technology (advisor David Karger), September 2003.
[Postscript, 2249KB] [Compressed Postscript, 595KB] [PDF, 1510KB]

Matthias Ruhl, Klassen von Approximationsproblemen, MS Thesis in Computer Science, Albert-Ludwigs-Universität Freiburg (advisor Jörg Flum), April 1998.
[Postscript, 582KB] [Compressed Postscript, 207KB] [PDF, 438KB]

Matthias Ruhl, Fraktale Bildkompression - Adaptive Partitionierungen und Komplexität, MS Thesis in Mathematics, Albert-Ludwigs-Universität Freiburg (advisor Dietmar Saupe), April 1997.
[Compressed Postscript, 9939KB] [PDF, 9368KB]

Manuscripts

Matthias Ruhl, Orderings and PTIME -- On a Conjecture by Makowsky, Manuscript, August 2001.
[Postscript, 302KB] [Compressed Postscript, 138KB] [PDF, 169KB]

Zulfikar Ramzan, Matthias Ruhl, Protocols for Anonymous Subscription Services, Manuscript, November 2000.
[Postscript, 155KB] [Compressed Postscript, 58KB] [PDF, 91KB]

Yevgeniy Dodis, Matthias Ruhl, GM-Security and Semantic Security Revisited, Manuscript, February 1999.
[Postscript, 231KB] [Compressed Postscript, 108KB] [PDF, 129KB]


Back to my homepage