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.
Google, Mountain View,
CA (June 2004-April 2013)
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
Intern in the Theory group.
Work on Finite Model Theory, On-Line and Streaming Algorithms with Ron Fagin, T.S. Jayram and Sridhar Rajagopalan.
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.
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".
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).
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.
Fluent in English and German; fair knowledge of French.
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.
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.
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.
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.
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.
Matthias Ruhl, Fraktale Bildkompression - Adaptive Partitionierungen und Komplexität, MS Thesis in Mathematics, Albert-Ludwigs-Universität Freiburg (advisor Dietmar Saupe), April 1997.
Zulfikar Ramzan, Matthias Ruhl, Protocols for Anonymous Subscription Services, Manuscript, November 2000.