David Abraham

David Abraham
Ph.D. candidate, Computer Science Department, Carnegie Mellon University
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 in part by a Siebel Scholar Fellowship and a Yahoo! Key Technical Challenge award. Last summer, I interned at reCAPTCHA, a company that uses CAPTCHAs to stop computer bots from gaining unauthorized access to websites. reCAPTCHA also uses the human answers from CAPTCHAs to help digitize old books.

Research Interests: online and approximation algorithms; game theory and mechanism design; auctions; matching markets; graph theory; no-regret algorithms;
Curriculum Vitae: Available on request.

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.

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.
The never-ending altruistic donor, with M.A. Rees, J.E. Kopke, G. Hil, W. Reitsma, O.G. Pankewycz, A.L. Miller, A.M. Hawxby, R.A. Montgomery, T. Sandholm, A.E. Roth, T. Sönmez, M.U. Ünver.

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.