Matthias Ruhl

Office:

Google
1600 Amphitheatre Parkway
Mountain View, CA 94043
(650) 253-4817

Research Interests

Algorithms, Complexity Theory, Cryptography, Logic and Data Compression, including implementation issues.

Education

Massachusetts Institute of Technology, Cambridge, MA (September 1998-September 2003)
Ph.D. in Electrical Engineering and Computer Science (GPA 5.0/5.0).

Albert-Ludwigs-Universität Freiburg, Germany (October 1993-April 1998)
M.S. in Computer Science, M.S. in Mathematics (GPA 4.0/4.0).
Graduation with "highest honors" in both subjects.

Honors and Awards

World Champion ACM International Collegiate Programming Contest, 1995.

Capocelli Award (Best Student Paper), IEEE Data Compression Conference, 1997.

Master Thesis awarded prize at "Deutscher Studienpreis" (German student research competition), 1998.

Kleene Award (Best Student Paper), IEEE Symposium on Logic in Computer Science, 1999.

IBM Graduate Fellowship, 2001-2003.

Josef Raviv Memorial Postdoctoral Fellowship, 2003.

Experience

Google, Mountain View, CA (June 2004-present)
Research Scientist.

IBM Almaden Research Center, San Jose, CA (September 2003-June 2004)
Josef Raviv Memorial Postdoctoral Fellow.
Work in the "Foundations of Computer Science" group on massive data set computations, peer-to-peer networks, and network coding.

Massachusetts Institute of Technology, Cambridge, MA (September 1998-August 2003)
Research Assistant in the Theory of Computation group.
Work on network design and scheduling algorithms (with David Karger), complexity theory, cryptography.

Massachusetts Institute of Technology, Cambridge, MA (September 1999-January 2001)
Teaching Assistant for
6.046J/18.410J Introduction to Algorithms, taught by Michel Goemans and Dan Spielman (Fall 1999)
6.856J/18.416J Randomized Algorithms, taught by David Karger (Fall 2000)

IBM Almaden Research Center, San Jose, CA (June 2001-August 2001, June 2002-August 2002)
Intern in the Theory group.
Work on Finite Model Theory, On-Line and Streaming Algorithms with Ron Fagin, T.S. Jayram and Sridhar Rajagopalan.

Google, Mountain View, CA (June 2000-August 2000)
Intern in the Research group.
Work on Data Mining with Monika Henzinger.

Xerox PARC, Palo Alto, CA (June 1999-August 1999)
Research Intern in the Theory group.
Work on "Authentication of Paper Documents" with David Goldberg and Marshall Bern.

Albert-Ludwigs-Universität Freiburg, Germany (October 1997-August 1998)
Research/Teaching Assistant in the mathematics department under Professor Jörg Flum.
Worked on problems in finite model theory (logic), esp. counting quantifiers, orderings. Taught recitations for course in "Mathematical Logic".

Albert-Ludwigs-Universität Freiburg, Germany (March 1994-December 1997)
Research Assistant in the computer science department under Professor Dietmar Saupe.
Design and implementation (C/C++) of programs for image compression and visualization of algebraic surfaces. Proved NP-hardness result for constructing optimal codes for 'fractal image compression', and developed practical heuristic algorithms for the same problem. Also partly responsible for system administration (SGI, Sun).

Coursework

Computer Science: Cryptography and Cryptanalysis, Programming Languages, Topics in Theoretical Computer Science, Natural Language Processing, Complexity Theory, Graduate Algorithms and Data Structures, Recursion Theory, Information and Coding Theory, Computational Geometry, Computer Graphics, Image Processing, Artificial Intelligence, Databases, Systems Architecture, Human-Machine Interaction.

Mathematics: Logic (Model Theory, Descriptive Complexity Theory), Probability Theory (Stochastics, Measure Theory, Stochastic Processes), Algebra, Algebraic Topology, Differential Geometry, Linear Algebra, Analysis, Numerical Analysis, Non-Standard Analysis, Number Theory, Function Theory, Set Theory.

Skills

Proficient in C, C++, Scheme, Pascal, Assembly (and many other languages), UNIX system administration, DOS/Windows, LaTeX, HTML.

Fluent in English and German; fair knowledge of French.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

Dietmar Saupe, Matthias Ruhl, Evolutionary fractal image compression, Proceedings IEEE International Conference on Image Processing (ICIP), Lausanne, vol. 1, pp. 129-132, September 1996.

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.

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.

David R. Karger, Matthias Ruhl, New Algorithms for Load Balancing in Peer-to-Peer Systems, IRIS Student Workshop (ISW), Cambridge, MA, August 2003.

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.

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.

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.

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.

Matthias Ruhl, Klassen von Approximationsproblemen, MS Thesis in Computer Science, Albert-Ludwigs-Universität Freiburg (advisor Jörg Flum), April 1998.

Matthias Ruhl, Fraktale Bildkompression - Adaptive Partitionierungen und Komplexität, MS Thesis in Mathematics, Albert-Ludwigs-Universität Freiburg (advisor Dietmar Saupe), April 1997.

Manuscripts

Matthias Ruhl, Orderings and PTIME -- On a Conjecture by Makowsky, Manuscript, August 2001.

Zulfikar Ramzan, Matthias Ruhl, Protocols for Anonymous Subscription Services, Manuscript, November 2000.

Yevgeniy Dodis, Matthias Ruhl, GM-Security and Semantic Security Revisited, Manuscript, February 1999.