Note: This page has long been under construction. Someday I'll put more
things on it.
Selected recent papers
Weak monotonicity suffices for truthfulness (with Lan Yu), preliminary version.
To appear in Proceedings of 6th ACM Conference on Electronic Commerce, 2005.
Rounds vs. Queries Trade-off in Noisy
Computation (with Navin Goyal) Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 2005.
On a parallel search game (with Navin Goyal),
To appear in Random Structures and Algorithms.
Lower bounds for tounds for the noisy broadcast problem (with Navin Goyal and Guy Kindler), FOCS 2005 and
Journal submission
Distributed Monotonicity Reconstruction (with C. Seshadhri)
Journal submission . (This is an expanded version of
Parallel Monotonicity
Reconstruction from SODA 2008.)
Online Multicast with Egalitarian Cost Sharing (With M. Charikar,
H. Karloff, C. Mathieu and J. Naor) SPAA 2008
A recent survey talk
Decision Trees: Problems and Results, Old and New