|
|
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.
|
|
|
Muirhead-Rado inequality for compact groups. Positivity,
to appear.
|
|
|
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. 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. Discrete and
Computational Geometry 40(4): 537-560, 2008. Preliminary version: 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. 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. 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]
|
|
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.
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.
|
