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
Local Monotonicity Reconstruction (with C. Seshadhri)
(To appear in SICOMP) . (This is an expanded version of
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