David Abraham Ph.D. candidate, Computer Science Department, Carnegie Mellon University, expected graduation 2009 M.Sc., Computer Science Department, Carnegie Mellon University, 2009 M.Sc., Department of Computing Science, University of Glasgow, 2003 B.Sc (Hons I)., School of Information Technologies, University of Sydney, 2002 Office: Doherty Hall 4301a Phone: (412) 268 1845 Email: dabr...@cs.cmu.edu

About Me:

My PhD thesis is on algorithm and mechanism design for real-world matching markets. Here is my thesis proposal. The main markets I have looked at involve kidney exchanges, keyword auctions, and online DVD rental.

Kidney Exchanges: In these markets, patients with terminal kidney disease try to swap their incompatible donors with each other in order to get a compatible donor. My main contribution in this area is an algorithm for finding the best set of swaps. This algorithm was recently selected by the UNOS for use in their upcoming nationwide kidney exchange, where it is expected to save thousands of lives and hundreds of millions of dollars a year in health care costs.

Keyword Auctions: Microsoft, Yahoo and Google use these auctions to sell the advertising space next to their search results. I came up with a new decomposition tool that leads to a simple technique for designing and analyzing keyword auction mechanisms. I used this tool to design a new mechanism that enables Microsoft to bid in its own auctions (e.g. when a user searches for xbox) without a conflict of interest. We have two patents pending on this work.

Publications:

• reCAPTCHA: Human-Based Character Recognition via Web Security Measures, with Luis von Ahn, Benjamin Maurer, Colin McMillen, and Manuel Blum.
  Science, 14 August 2008. [DOI: 10.1126/science.1160379]
• The stable roommates problem with globally-ranked pairs, with Ariel Levavi, David Manlove, and Gregg O'Malley.
  In Proceedings of WINE 2007: the 3rd International Workshop on Internet and Network Economics.
  Accepted to Internet Mathematics.
• Clearing Algorithms for Barter-Exchange Markets: Enabling Nationwide Kidney Exchanges, with Avrim Blum and Tuomas Sandholm.
  In Proceedings of ACM-EC 2007: the Eighth ACM Conference on Electronic Commerce.
• Assignment problems in rental markets, with Ning Chen, Vijay Kumar and Vahab Mirrokni.
  In Proceedings of WINE 2006: the 2nd International Workshop on Internet and Network Economics.
• Dynamic matching markets and voting paths, with Kavitha Telikepalli.
  In Proceedings of SWAT 2006: the 10th Scandinavian Workshop on Algorithm Theory
• Two algorithms for the student-project allocation problem, with Rob W. Irving and David F. Manlove.
  In Journal of Discrete Algorithms, 5 (1):73-90, 2007
• "Almost stable" matchings in the roomates problem, with Péter Biró and David F. Manlove.
  In Proceedings of WAOA 2005: the 3rd Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science, pages 1-14, Springer-Verlag, 2006.
• Popular matchings, with Rob W. Irving, Kurt Mehlhorn and Kavitha Telikepalli.
  In Proceedings of SODA 2005: the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 424-432, 2005.
  In SIAM Journal on Computing vol. 37, pp. 1030-1045, 2007.
• Pareto optimality in house allocation problems, with Katarína Cechlárová, David F. Manlove and Kurt Mehlhorn.
  In Proceedings of ISAAC 2004: the 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 3-15, Springer-Verlag, 2004.
• Pareto optimality in the roommates problem, with David F. Manlove.
  Technical Report no. TR-2004-182 of the Computing Science Department of Glasgow University, 2004.
• The student-project allocation problem, with Rob W. Irving and David F. Manlove.
  In Proceedings of ISAAC 2003: the 14th Annual International Symposium on Algorithms and Computation, volume 2906 of Lecture Notes in Computer Science, pages 474-484, Springer-Verlag, 2003.
• Generalizing edge colouring to solve real instances of the timetabling problem, with Jeffrey H. Kingston.
  In selected revised papers from the 4th international conference on the Practice and Theory of Automated Timetabling (PATAT 2002), Springer Lecture Notes in Computer Science Vol 2740, pp. 289-299, 2003.
• XMLTutor: an Authoring Tool for Factual Domains, with Kalina Yacef.
  In Proceedings of Workshop on Concepts and Ontologies in Web-based Educational Systems, held in conjunction with International Conference on Computers in Education (ICCE), CS-Report 02-15 Technische Universiteit Eindhoven, Auckland, New Zealand.
• Adaptation in the Web-Based Logic-ITA, with Kalina Yacef.
  In Proceedings of AH2002: the Second International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems, volume 2347 of Lecture Notes in Computer Science, Springer-Verlag, 2002.
• The Logic Tutor: A Multimedia Presentation, with Elisabeth Crawford, Leanna Lesta, Agathe Merceron and Kalina Yacef.
  In Interactive Multimedia Electronic Journal on Computer Enhanced Learning, 3(2), 2001.
• A tool to practice formal proofs, with Elisabeth Crawford, Leanna Lesta, Agathe Merceron and Kalina Yacef.
  In the Proceedings EDMEDIA 2001: the World Conference on Educational Multimedia, Hypermedia and Telecommunications 2001(1), 7-8.

In Submission/Preparation:

• Layerable mechanisms for keyword auctions, with Arash Asadpour and Kamal Jain.
• Online directed cycle cover, with R. Ravi and Viswanath Nagarajan.
• Fair matchings, with R. Ravi.

Dissertations:

• Algorithmics of two-sided matching problems, MSc thesis, Department of Computing Science, University of Glasgow, 2003.

• The high school timetable construction problem, Honours thesis, School of Information Technologies, University of Sydney, 2002.