Pall Melsted

I'm a sixth year (and final) 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 less 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

• Average-Case Analysis of Vickrey Costs
  Preprint.
  [Co-authors: P. Chebolu, A. Frieze, G. Sorkin]
• An Analysis of Random-Walk Cuckoo Hashing
  Preprint.
  [Co-authors: A. Frieze, M. Mitzenmacher]
• Randomly Colouring Simple Hypergraphs
  Preprint (Arxiv: [0901.3600])
  [Co-author: A. Frieze]
• Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
  Proceedings of ICALP 2008
  [Co-authors: P. Chebolu, A. Frieze]
• PageRank and the Random Surfer Model
  Proceedings of SODA 2008, 1010-1018
  [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:

• Spring 2009: 21-27 - Models & Methods for Optimization
• Fall 2008: 21-127 - Concepts of Mathematics
• 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