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
  • Local Monotonicity Reconstruction (with C. Seshadhri) (To appear in SICOMP) . (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
  • Tight lower bounds for the online labeling problem (with J. Bulanek and M. Koucky) SICOMP, to appear
  • On online labeling with polynomially many labels (With M. Babka, J. Bulanek, V. Cunat, and M. Koucky) July 2015 revision
  • On randomized online labeling with polynomially many labels (with J. Bulanek and M. Koucky), ICALP 2013
  • Clustering is difficult only when it does not matter (With A. Daniely and N. Linial) preliminary version
  • On the practically interesting instances of MAXCUT (With Y. Bilu, A. Daniely and N. Linial) preliminary version
  • A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity (with T. Naumovitz.) SODA 2015
  • A communication game related to the sensitivity conjecture (With J. Gilmer and M. Koucky) Submitted for jounnal publication , ITCS 2015