Pall Melsted

I'm a fifth year graduate student in the ACO Program in the Department of Mathematical Sciences at CMU. I study Probabilistic Combinatorics with emphasis on its applications to Theoretical Computer Science. My advisor is Alan Frieze. I have a research blog on withhighprobability.wordpress.com which is more dynamic than this site.

Research

My research can be summarized as doing random stuff with random graphs. For those in the know, this includes

• Analysis of algorithms in random graphs (especially randomized algorithms, I mean can you ever have too much randomness?)
• Random Graphs as models of "Real World" networks
• Analysis of classical Random Graphs

Papers and Preprints

• Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
  Submitted
  [Co-authors: P. Chebolu, A. Frieze]
• PageRank and the Random Surfer Model
  To appear in SODA 2008.
  [Co-author: P. Chebolu]

Talks and Presentations

• PageRank and the Random Surfer Model
  During a visit at Microsoft Research 1/15/08 - 1/21/08
  A video of the presentation.

Teaching

Some previous courses I've TAed:

• Fall 2007: 21-122 - Integration, Differential Equations & Approximation
• Spring 2007: 21-260 - Differential Equations
• Fall 2006: 21-120 - Differential & Integral Calculus for Business Students
• Fall 2005: 21-256 - Multivariate Analysis and Approximation
• Spring 2005: 21-257 - Models & Methods for Optimization
• Fall 2004: 21-121 - Integration & Differential Equations
• Spring 2004: 21-241 - Matrix Algebra
• Fall 2003: 21-122 - Integration, Differential Equations & Approximation

Personal

I am married to Johanna Jakobsdottir, a graduate student in Biostatistics at Pitt. We have one daughter, Greta Bjorg (pictured above).

Contact

Pall Melsted
Office Phone: 8-1447 (412-268-1447 outside of CMU)
Office: Physical Plant Building - Office 342
Email: pmelsted at cmu dot edu