 |
On a capacitated multivehicle routing problem,
with X. Gao. Proc. 27th PODC 2008, to appear. |
|
On partitioning graphs via single commodity flows,
with L. Orecchia, U. V. Vazirani and N. K. Vishnoi. Proc. 40th STOC
2008, to appear. |
|
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. Proc. 19th Canadian Conf. Computational Geometry 25-28,
2007.
|
|
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. |
|
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. Proc. 17th SODA 464-473,
2006.
|
|
Error-correcting codes for automatic control,
with R. Ostrovsky and Y. Rabani. 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.
Preliminary version: 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. journal 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.
abstract
|
|
|
A random walk model of wave propagation,
with M. Franceschetti and J. Bruck.
IEEE Transactions on Antennas and
Propagation 52(5):1304-1317, 2004. 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
|
|
|
A probabilistic analysis of EM for mixtures of separated, spherical
Gaussians, with S. Dasgupta.
Journal
of 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.
abstract/ps/pdf
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. journal
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. of the 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.
|
