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:

I am a fifth-year PhD student in the Computer Science Department of Carnegie Mellon University. My advisor is R. Ravi. I am supported by a Siebel Scholar Fellowship, and by a Yahoo! Key Technical Challenge award. I also work for reCAPTCHA, a startup that uses CAPTCHAs to stop computer bots from gaining unauthorized access to websites. reCAPTCHA uses the human answers from CAPTCHAs to help digitize old books.

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.


In Submission/Preparation: