- Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems, with Edo Liberty, Submitted.
- An efficient reduction of ranking to classification, with Mehryar Mohri, to appear in COLT 2008
- Dense fast random projections and Lean Walsh Transforms, with Edo Liberty and Amit Singer, to appear in RANDOM 2008
- Fast dimension reduction using Rademacher series on dual BCH codes, with Edo Liberty
To appear in proceedings of SODA'08
- Aggregation of partial rankings, p-ratings and top-m lists
In proceedings of SODA'07 - Lower bounds for linear degeneracy testing, with Bernard Chazelle
In proceedings of STOC'04 and Journal of the ACM
52(2) (2005), 157-171 - Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, with Bernard Chazelle
In proceedings of STOC'06; full version to appear in SICOMP - Aggregating inconsistent information: Ranking and clustering, with Moses Charikar and Alantha Newman
In proceedings of STOC'05; proofs of conjectures can be found here - Fitting tree metrics: Hierarchical clustering and phylogeny, with Moses Charikar
In proceedings of FOCS'05 - Hardness of fully dense problems, with Noga Alon
To appear in Information and
Computation - Property preserving data reconstruction, with Bernard Chazelle, Seshadhri Comandur and Ding Liu
In proceedings of ISAAC'04; Full version to appear in Algorithmica . - Estimating the distance to a monotone function, with Bernard Chazelle, Seshadhri Comandur and Ding Liu
In proceedings of RANDOM'04 and Random
Structures and Algorithms 31(3) (2007), 371--383
- Torsion points on curves and common divisors of ak - 1 and
bk - 1, with Ze'ev Rudnick
Acta Arithmetica 113 (2004),
31-38