Prasad Chebolu
Department of Computer Science
University of Liverpool
Office: Ashton Building 314
Phone: +44 151 795 4281
Fax: +44 151 795 4235
Mailing Address:
Department of Computer Science
University of Liverpool
Ashton Building, Ashton Street
Liverpool, L69 3BX
United Kingdom
email:prasadcATliverpoolDOTacDOTuk

Background
I am a research associate in the Department of Computer Science at the University of Liverpool
working with
Dr. Russell Martin .
I obtained my Ph.D in Mathematics from
Carnegie Mellon University under the guidance of
Alan Frieze .
Research
My research interest is in Probabilistic Combinatorics and its applications in
Theoretical Computer Science. My research during my Ph.D primarily involved
studying properties like Hamiltonicity and Matchings of various random graph models.
I am currently working on counting( and sampling) Stable Matchings,
Euler Tours in Graphs and Tilings of Polygons.
Publications
 Hamilton Cycles in Random Lifts of Graphs
European Journal of Combinatorics 27, 12821293 (2006).
[Coauthors: K. Burgin, P. Chebolu, C. Cooper]  PageRank and The Random Surfer Model
Proceedings of ACMSIAM Symposium on Discrete Algorithms, SODA (2008).
[Coauthors: P.Melsted]
 Hamilton cycles in random lifts of Complete Directed Graphs
SIAM Journal on Discrete Math, Vol.22, No.2, 520540 (2008).
[Coauthor: A. Frieze]
 Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
Journal of the Association for Computing Machinery, Volume 57,
Issue 4, April 2010. Preliminary version appeared in the
Proceedings of International Colloquium on Automata, Languages and Programming, ICALP(2008)
[Coauthors: A. Frieze and P. Melsted]
 AverageCase Analyses of Vickrey Costs
Proceedings of 13th International Workshop on Randomization and Computation, RANDOM(2009)
[Coauthors: A. Frieze, P. Melsted, G. Sorkin]
 The Complexity of Approximately Counting Stable Matchings
[Coauthors: L.A. Goldberg and R. Martin] to appear in the Proceedings of 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX (2010)
 Exact
counting of Euler tours for generalized seriesparallel graphs
[Coauthors: M. Cryan and R. Martin] submitted
 Multiprocessor Deadline Scheduling
of Unitsized Jobs
[Coauthors: P. Bell, R. Martin, P. Wong and F.C.C. Yung] manuscript
 The Complexity of Approximately Counting Stable Roommate Assignments
[Coauthors: L.A. Goldberg and R. Martin] manuscript under preparation
 Exact Counting of Euler Tours and Euler
Orientations for bounded treewidth graphs
[Coauthors: M. Cryan and R. Martin] manuscript under preparation
 Average Performance of the Greedy Matching Algorithm in Sparse Random Uniform Hypergraphs
[Coauthors: P. Melsted] manuscript under preparation
Teaching Experience
Instructor:
 Summer 2006: 21112 CalculusII
 Summer 2005: 21260 Differential Equations
 Summer 2004: 21259 Calculus in Three Dimensions
 Summer 2003: 21260 Differential Equations
Teaching Assistant:
 Spring 2008: 21257 Models and Methods of Optimization
 Fall 2007: 21127 Concepts of Mathematics
 Spring 2007: 21112 CalculusII
 Fall 2006: 21257 Models and Methods of Optimization
 Spring 2006: 21260 Differential Equations
 Fall 2005: 21127 Concepts of Mathematics
 Spring 2005: 21112 CalculusII
 Fall 2004: 21259 Calculus in Three Dimensions
 Spring 2004: 21260 Differential Equations
 Fall 2003: 21259 Calculus in Three Dimensions
 Spring 2003: 21260 Differential Equations
 Fall 2002: 21127 Concepts of Mathematics
Useful Links
ACO Homepage

