|
|
Clustering Affine Subspaces: Hardness and
Algorithms, with E. Lee.
Proc. 24th SODA 810-827, 2013.
|
|
|
Dimension-free L2 maximal inequality for spherical
means in the hypercube, with A. W. Harrow and A. Kolla.
Preprint on the ArXiv, 2012.
|
|
|
Allocation of Divisible Goods under Lexicographic
Preferences, with V. Vazirani.
Preprint on the ArXiv, 2012.
|
|
|
Optimal Coding for Streaming Authentication and
Interactive Communication, with M. Franklin, R. Gelles
and R. Ostrovsky.
Preprint on the ECCC, 2012. Crypto 2013, to appear.
|
|
|
Data reduction for weighted and
outlier-resistant clustering, with D. Feldman.
Proc. 23rd SODA 1343-1354, 2012.
|
|
|
The quantifier semigroup for bipartite
graphs. The Electronic
Journal of Combinatorics 18(1) P123, 2011.
|
|
|
Dimensionality reduction: beyond the
Johnson-Lindenstrauss bound, with Y. Bartal and
B. Recht.
Proc. 22nd SODA 868-887, 2011. (Correction)
|
|
|
Volume in general metric spaces, with
I. Abraham, Y. Bartal and O. Neiman. Proc. 18th ESA,
II:87-99 (Springer LNCS 6347), 2010.
|
|
|
Clustering lines in high dimensional space:
classification of incomplete data, with J. Gao and
M. Langberg. ACM
Trans. Algorithms 7(1) Article 8, November 2010.
|
|
|
Universal epsilon-approximators for
integrals, with M. Langberg. Proc.
21st SODA 598-607, 2010.
|
|
|
Variation on a theorem by
Carathéodory. Mathematika
56(1):169-172, 2010.
|
|
|
Universal immersion spaces for edge-colored graphs
and nearest-neighbor metrics, with Y. Bartal. SIAM
J. Discrete Math. 23(2):1110-1115, 2009.
|
|
|
Solvency games, with N. Berger, N. Kapur and V.
Vazirani. Proc. FSTTCS 61-72, 2008. Updated version,
2010: [pdf]
|
|
|
Muirhead-Rado inequality for compact groups.
Positivity
13:559-574, 2009.
|
|
|
Learning Mixtures of Arbitrary Distributions over
Large Discrete Domains, with Y. Rabani and C. Swamy.
Preprint on the ArXiv,
2012. Earlier
preprint (for k=2), 2008.
|
|
|
On a capacitated multivehicle routing problem,
with X. Gao. Proc. 27th PODC 175-184, 2008.
|
|
|
On partitioning graphs via single commodity flows,
with L. Orecchia, U. V. Vazirani and N. K. Vishnoi. Proc. 40th STOC
461-470, 2008.
|
|
|
Approximation algorithms for labeling hierarchical
taxonomies, with Y. Rabani and C. Swamy. Proc.
19th SODA 671-680, 2008 .
|
|
|
Contraction and expansion of convex sets, with
M. Langberg. Short version: Proc. 19th Canadian
Conf. Computational Geometry 25-28, 2007. Long
version: Discrete
and Computational Geometry 42(4):594-614, 2009.
|
|
|
Quantum algorithms for hidden nonlinear structures,
with A. M. Childs and U. V. Vazirani. Proc. 48th FOCS 395-404, 2007. [pdf]
Preliminary version: [quant-ph]
|
|
|
Imaging geometry through dynamics: the observable
representation, with B. Gaveau and L. S. Schulman. J. Physics A
39(33):10307-10321, 2006.
|
|
|
The effectiveness of Lloyd-type methods for the
k-means problem, with R. Ostrovsky, Y. Rabani and C. Swamy. Proc.
47th FOCS 165-174, 2006. J. ACM 59(6) Art. 28, 2012. Computing Reviews Notable Paper in Computing 2012
|
|
|
Convergence of matrices under random conjugation:
wave packet scattering without kinematic entanglement, with L. S.
Schulman. J. Physics A
39(7):1717-1728, 2006.
|
|
|
Analysis of incomplete data and an
intrinsic-dimension Helly theorem, with J. Gao and M. Langberg. Discrete and
Computational Geometry 40(4): 537-560, 2008 . Proc.
17th SODA 464-473, 2006.
|
|
|
Error-correcting codes for automatic control,
with R. Ostrovsky and Y. Rabani.
IEEE
Trans. Information Theory 55(7):2931-2941, 2009.
Proc.46th FOCS 309-316, 2005.
|
|
|
Real-time coding for multiple access channels,
with X. Gao. Proc. ISIT 67-71, 2005.
|
|
|
Feedback control for router congestion resolution,
with X. Gao. Proc.
24th PODC 218-226, 2005.
|
|
|
Physical limits of heat-bath algorithmic cooling,
with T. Mor and Y. Weinstein. Short version: Physical
Review Letters 94:120501, 2005. (Corrected
example.) Also in the Virtual
J. Nanoscale Science & Technology 11(14)
4/11/2005 and the Virtual
J. Quantum Information April 2005. Long
version: SIAM
J. Computing 36(6) 1729-1747, 2007.
|
|
|
The symmetric group defies strong Fourier sampling,
with C. Moore and A. Russell. SIAM J. Computing 37(6)
1842-1864, 2008. Proc. 46th
FOCS 479-488, 2005. Tech report: [quant-ph]
|
|
|
Improved expansion of random Cayley graphs,
with P.-S. Loh. Discrete
Mathematics and Theoretical Computer Science 6(2):523-528, 2004.
|
|
|
Deterministic clustering with data nets, with
M. Effros. Research announcement in Proc. ISIT, 2004: Rapid
near-optimal VQ design with a deterministic data net. ECCC
TR04-050, 2004.
|
|
|
Wave packet scattering without kinematic
entanglement: convergence of expectation values, with
L. S. Schulman.
IEEE
Trans. Nanotechnology 4(1):8-13, 2005.
|
|
|
Fair and efficient router congestion control,
with X. Gao and K. Jain. Proc. 15th SODA
1043-1052, 2004.
|
|
|
The power of strong Fourier sampling: quantum
algorithms for affine groups and hidden shifts, with C. Moore, D.
Rockmore and A. Russell. SIAM
J. Computing 37(3):938-958, 2007. Preliminary
version: The Power of Basis Selection in
Fourier Sampling: Hidden Subgroup Problems in
Affine Groups, Proc. 15th SODA 1106-1115,
2004. Tech report: [quant-ph]
|
|
|
On the maximum tolerable noise of k-input gates for
reliable computation by formulas, with
W. Evans. IEEE Transactions on Information Theory
49(11):3094-3098, 2003. [abstract/ps/pdf]
|
|
|
Reconstruction from subsequences, with M. Dudik.
J. Combinatorial Theory Series A
103:337-348, 2003.
|
|
|
A random walk model of wave propagation,
with M. Franceschetti and J. Bruck. IEEE Transactions on Antennas and
Propagation 52(5):1304-1317, 2004; received the 2004 S. A. Schelkunoff
Transactions Prize Paper Award. Preliminary version: IEEE AP-S
Antennas and Propagation Society Symposium 2002.
|
|
A random stacking process,
Special issue of Discrete Mathematics dedicated to
Daniel J. Kleitman 257(2):541-547, 2002.
|
|
|
Lower Bounds for Linear Locally Decodable Codes and
Private Information Retrieval, with O. Goldreich,
H. Karloff and L. Trevisan. Computational
Complexity 15(3):263-296, 2006. Preliminary
version: Proc. 17th Conference on Computational
Complexity 175-183, 2002. ECCC
TR01-080, 2001.
|
|
Quantum Mechanical Algorithms for the
Nonabelian Hidden Subgroup Problem, with
M. Grigni, M. Vazirani and
U. Vazirani. Combinatorica 24(1):137-154,
2004. Preliminary version: Proc. 33rd STOC 68-74,
2001.
|
|
The Vector Partition Problem for Convex
Objective Functions, with S. Onn. Mathematics
of Operations Research 26(3):583-590, 2001. [abstract/ps/pdf]/journal
|
|
A Probabilistic Analysis of EM for
Mixtures of Separated, Spherical Gaussians,
with S. Dasgupta. J.
Machine Learning Research 8:203-226,
2007. Preliminary version: A two-round
variant of EM for Gaussian mixtures,
Proc. 16th UAI (Conference on Uncertainty in
Artificial Intelligence) 152-159, 2000. [abstract/ps/pdf]
|
|
Computing with highly mixed states,
with A. Ambainis and U. Vazirani. J. ACM
53(3):507-531, 2006. Preliminary version: Proc. 32nd
STOC 697-704, 2000. [ps]
|
|
Broadcasting on Trees and the Ising
Model, with W. Evans, C. Kenyon and
Y. Peres. Annals of Applied Probability
10(2):410-433, 2000. [ps/pdf]
|
|
Clustering for Edge-Cost Minimization.
ECCC TR99-035, 1999. Proc. 32nd STOC 547-555, 2000.
[Updated: abstract/ps/pdf]
|
|
Molecular Scale Heat Engines and Scalable
Quantum Computation, with U. Vazirani. Proc. 31st
STOC 322-329, 1999. [abstract/ps/pdf
Preliminary version:
quant-ph, Scalable NMR Quantum
Computation.]
|
|
A computationally motivated definition of
parametric estimation and its applications to the
Gaussian distribution, with
V. Vazirani. Combinatorica 25(4):465-486,
2005. Preliminary version: Proc. 31st STOC
288-294, 1999. [ps/pdf].
|
|
The quantum communication complexity of
sampling, with A. Ambainis, A. Ta-Shma,
U. Vazirani and A. Wigderson. SIAM J. Computing
32:1570-1585, 2003. Preliminary version:
Proc. 39th FOCS 342-351, 1998. [ps/pdf]
|
|
Pattern Matching for Spatial Point
Sets, with D. Cardoze. Proc. 39th FOCS
156-165, 1998. [Updated: abstract/ps/pdf]
|
|
A three-party communication problem.
J. Computer and System Sciences 57:399-401,
1998.
|
|
Asymptotically good codes correcting
insertions, deletions and transpositions, with
D. Zuckerman. IEEE Transactions on Information
Theory 45(7):2552-2557, 1999. [abstract/ps/pdf]
Preliminary version: Proc. 8th SODA 669-674,
1997.
|
|
Verification of Identities, with
S. Rajagopalan. SIAM J. Computing 29(4):1155-1163,
2000. Preliminary version: Proc. 37th FOCS 612-616,
1996.
|
|
Bounds on the Chromatic Polynomial and on
the Number of Acyclic Orientations of a Graph,
with N. Kahale. Combinatorica 16(3):383-397,
1996. [ps/pdf]
|
|
Splitters and near-optimal
derandomization, with M. Naor and
A. Srinivasan. Proc. 36th FOCS 182-191, 1995. [abstract/ps/pdf]
|
|
Fairness in Scheduling, with
M. Ajtai, J. Aspnes, M. Naor, Y. Rabani and
O. Waarts. J. of Algorithms 29(2):306-357, 1998. [ps/pdf]
Preliminary version: Proc. 6th SODA 477-485,
1995.
|
|
A Coding Theorem for Distributed
Computation, with S. Rajagopalan. Proc. 26th
STOC 790-799, 1994. [ps/pdf]
|
|
A product theorem for intersection
families. European J. of Combinatorics
15:579-586, 1994.
|
|
Signal propagation and noisy
circuits, with W. Evans. IEEE Transactions on
Information Theory 45(7) 2367-2373,
1999. Preliminary version: Proc. 34th FOCS
594-603, 1993.
|
|
Coding for Interactive Communication.
Special issue on Codes and Complexity of the IEEE
Transactions on Information Theory 42(6) Part
I:1745-1756, 1996. [ps/pdf]
Preliminary versions: Proc. 33rd FOCS 724-733,
1992 and Proc. 25th STOC 747-756, 1993.
Postscript of 21 September 2003.
|
|
Minimally distant sets of lattice
points, with D. J. Kleitman. Special issue of
the European J. of Combinatorics dedicated to
Bernt Lindström 14:231-240, 1993.
|
|
An equipartition of planar sets.
Discrete and Computational Geometry 9:257-266,
1993.
|
|
Sample spaces uniform on
neighborhoods. Proc. 24th STOC 17-25,
1992.
|
|
The Maintenance of Common Data in a
Distributed System, with B. Awerbuch.
J. ACM 44(1):86-103, 1997. [ps/pdf]
Preliminary version: Proc. 32nd FOCS 505-514,
1991.
|
|
Crossing families, with B. Aronov,
P. Erdös, W. Goddard, D. J. Kleitman,
M. Klugerman and J. Pach. Combinatorica
14(2):127-134, 1994. Preliminary version:
Proc. 7th ACM Symp. Comp. Geom. 351-356,
1991.
|
|
Optimal randomized algorithms for local
sorting and set-maxima, with W. Goddard,
C. Kenyon and V. King.
SIAM J. Computing
22(2):272-283, 1993. Preliminary version:
Proc. 22nd STOC 45-53, 1990.
|
|
Sorting on a ring of processors, with
Y. Mansour. J. of Algorithms 11:622-630,
1990.
|
