## 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