
The invisible hand of Laplace: the role of market structure in price convergence and oscillation, with Y. Rabani. Preprint, 2016.


Extractors for Near Logarithmic MinEntropy, with G. Cohen. Preprint, 2016.


Symbolic integration and the complexity of computing
averages, with A. Sinclair and
P. Srivastava. Proc. 56th FOCS 12311245, 2015.


OneShot Bargaining Mechanisms,
with Y. Babichenko.
Preprint, 2015.


Analysis of a classical matrix preconditioning algorithm,
with A. Sinclair. Preprint,
2015. Proc. 47th STOC 831840, 2015.


Learning Arbitrary Statistical Mixtures of
Discrete Distributions, with J. Li, Y. Rabani and
C. Swamy.
Preprint, 2015. Proc. 47th STOC 743752, 2015.


The Adversarial Noise Threshold for Distributed
Protocols, with W. M. Hoza.
Preprint, 2014. Proc. 27th SODA 240258, 2016.


Achieving Target Equilibria in Network Routing
Games without Knowing the Latency Functions,
with U. Bhaskar, K. Ligett and C. Swamy.
Preprint, 2014. Proc. 55th FOCS 3140, 2014.


Tree Codes and a Conjecture on Exponential Sums,
with C. Moore.
Preprint, 2013.
Proc. 5th ITCS 145153, 2014.


The Network Improvement Problem for Equilibrium Routing,
with U. Bhaskar and K. Ligett.
Preprint, 2013.
Proc. 17th IPCO 138149, 2014.


Clustering Affine Subspaces: Hardness and
Algorithms, with E. Lee.
Proc. 24th SODA 810827, 2013.


Dimensionfree L2 maximal inequality for spherical
means in the hypercube, with A. W. Harrow and A. Kolla.
Preprint, 2012. Theory of
Computing, Special Issue on Boolean Functions, 10(3):5575, 2014.


Allocation of Divisible Goods under Lexicographic
Preferences, with V. Vazirani.
Preprint, 2012. Proc. FSTTCS 543559, 2015.


Optimal Coding for Streaming Authentication and
Interactive Communication, with M. Franklin, R. Gelles
and R. Ostrovsky.
Preprint, 2012.
Proc. 33rd Crypto 258276, 2013. IEEE Trans. Information Theory 61(1): 133145, 2015.


Data reduction for weighted and
outlierresistant clustering, with D. Feldman.
Proc. 23rd SODA 13431354, 2012.


The quantifier semigroup for bipartite
graphs. The Electronic
Journal of Combinatorics 18(1) P123, 2011.


Dimensionality reduction: beyond the
JohnsonLindenstrauss bound, with Y. Bartal and
B. Recht.
Proc. 22nd SODA 868887, 2011. (Correction)


Volume in general metric spaces, with
I. Abraham, Y. Bartal and O. Neiman.
Proc. 18th ESA,
II:8799 (Springer LNCS 6347), 2010. Discrete and Computational Geometry 52(2):366389, 2014.


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 epsilonapproximators for
integrals, with M. Langberg. Proc.
21st SODA 598607, 2010.


Variation on a theorem by
Carathéodory. Mathematika
56(1):169172, 2010.


Universal immersion spaces for edgecolored graphs
and nearestneighbor metrics, with Y. Bartal. SIAM
J. Discrete Math. 23(2):11101115, 2009.


Solvency games, with N. Berger, N. Kapur and V.
Vazirani. Proc. FSTTCS 6172, 2008. Updated version,
2010: [pdf]


MuirheadRado inequality for compact groups.
Positivity
13:559574, 2009.


Learning Mixtures of Arbitrary Distributions over
Large Discrete Domains, with Y. Rabani and C. Swamy.
Preprint,
2012. Earlier
preprint (for k=2), 2008.
Proc. 5th ITCS 207223, 2014.


On a capacitated multivehicle routing problem,
with X. Gao. Proc. 27th PODC 175184, 2008.


On partitioning graphs via single commodity flows,
with L. Orecchia, U. V. Vazirani and N. K. Vishnoi. Proc. 40th STOC
461470, 2008.


Approximation algorithms for labeling hierarchical
taxonomies, with Y. Rabani and C. Swamy. Proc.
19th SODA 671680, 2008 .


Contraction and expansion of convex sets, with
M. Langberg. Short version: Proc. 19th Canadian
Conf. Computational Geometry 2528, 2007. Long
version: Discrete
and Computational Geometry 42(4):594614, 2009.


Quantum algorithms for hidden nonlinear structures,
with A. M. Childs and U. V. Vazirani. Proc. 48th FOCS 395404, 2007. [pdf]
Preprint: [quantph]


Imaging geometry through dynamics: the observable
representation, with B. Gaveau and L. S. Schulman. J. Physics A
39(33):1030710321, 2006.


The effectiveness of Lloydtype methods for the
kmeans problem, with R. Ostrovsky, Y. Rabani and C. Swamy. Proc.
47th FOCS 165174, 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):17171728, 2006.


Analysis of incomplete data and an
intrinsicdimension Helly theorem, with J. Gao and M. Langberg. Discrete and
Computational Geometry 40(4): 537560, 2008 . Proc.
17th SODA 464473, 2006.


Errorcorrecting codes for automatic control,
with R. Ostrovsky and Y. Rabani.
IEEE
Trans. Information Theory 55(7):29312941, 2009.
Proc.46th FOCS 309316, 2005.


Realtime coding for multiple access channels,
with X. Gao. Proc. ISIT 6771, 2005.


Feedback control for router congestion resolution,
with X. Gao. Proc.
24th PODC 218226, 2005.


Physical limits of heatbath 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) 17291747, 2007.


The symmetric group defies strong Fourier sampling,
with C. Moore and A. Russell. SIAM J. Computing 37(6)
18421864, 2008. Proc. 46th
FOCS 479488, 2005. Preprint: [quantph]


Improved expansion of random Cayley graphs,
with P.S. Loh. Discrete
Mathematics and Theoretical Computer Science 6(2):523528, 2004.


Deterministic clustering with data nets, with
M. Effros. Research announcement in Proc. ISIT, 2004: Rapid
nearoptimal VQ design with a deterministic data net. ECCC
TR04050, 2004.


Wave packet scattering without kinematic
entanglement: convergence of expectation values, with
L. S. Schulman.
IEEE
Trans. Nanotechnology 4(1):813, 2005.


Fair and efficient router congestion control,
with X. Gao and K. Jain. Proc. 15th SODA
10431052, 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):938958, 2007. Preliminary
version: The Power of Basis Selection in
Fourier Sampling: Hidden Subgroup Problems in
Affine Groups, Proc. 15th SODA 11061115,
2004. Preprint: [quantph]


On the maximum tolerable noise of kinput gates for
reliable computation by formulas, with
W. Evans. IEEE Transactions on Information Theory
49(11):30943098, 2003. [abstract/ps/pdf]


Reconstruction from subsequences, with M. Dudik.
J. Combinatorial Theory Series A
103:337348, 2003. Or here.


A random walk model of wave propagation,
with M. Franceschetti and J. Bruck. IEEE Transactions on Antennas and
Propagation 52(5):13041317, 2004; received the 2004 S. A. Schelkunoff
Transactions Prize Paper Award. Preliminary version: IEEE APS
Antennas and Propagation Society Symposium 2002.


A random stacking process,
Special issue of Discrete Mathematics dedicated to
Daniel J. Kleitman 257(2):541547, 2002.


Lower Bounds for Linear Locally Decodable Codes and
Private Information Retrieval, with O. Goldreich,
H. Karloff and L. Trevisan. Computational
Complexity 15(3):263296, 2006. Preliminary
version: Proc. 17th Conference on Computational
Complexity 175183, 2002. ECCC
TR01080, 2001.


Quantum Mechanical Algorithms for the
Nonabelian Hidden Subgroup Problem, with
M. Grigni, M. Vazirani and
U. Vazirani. Combinatorica 24(1):137154,
2004. Preliminary version: Proc. 33rd STOC 6874,
2001.


The Vector Partition Problem for Convex
Objective Functions, with S. Onn. Mathematics
of Operations Research 26(3):583590, 2001. [abstract/ps/pdf]/journal


A Probabilistic Analysis of EM for
Mixtures of Separated, Spherical Gaussians,
with S. Dasgupta. J.
Machine Learning Research 8:203226,
2007. Preliminary version: A tworound
variant of EM for Gaussian mixtures,
Proc. 16th UAI (Conference on Uncertainty in
Artificial Intelligence) 152159, 2000. [abstract/ps/pdf]


Computing with highly mixed states,
with A. Ambainis and U. Vazirani. J. ACM
53(3):507531, 2006. Preliminary version: Proc. 32nd
STOC 697704, 2000. [ps]


Broadcasting on Trees and the Ising
Model, with W. Evans, C. Kenyon and
Y. Peres. Annals of Applied Probability
10(2):410433, 2000. [ps/pdf]


Clustering for EdgeCost Minimization.
ECCC TR99035, 1999. Proc. 32nd STOC 547555, 2000.
[Updated: abstract/ps/pdf]


Molecular Scale Heat Engines and Scalable
Quantum Computation, with U. Vazirani. Proc. 31st
STOC 322329, 1999. [abstract/ps/pdf
Preliminary version:
quantph, Scalable NMR Quantum
Computation.]


A computationally motivated definition of
parametric estimation and its applications to the
Gaussian distribution, with
V. Vazirani. Combinatorica 25(4):465486,
2005. Preliminary version: Proc. 31st STOC
288294, 1999. [ps/pdf].


The quantum communication complexity of
sampling, with A. Ambainis, A. TaShma,
U. Vazirani and A. Wigderson. SIAM J. Computing
32:15701585, 2003. Preliminary version:
Proc. 39th FOCS 342351, 1998. [ps/pdf]


Pattern Matching for Spatial Point
Sets, with D. Cardoze. Proc. 39th FOCS
156165, 1998. [Updated: abstract/ps/pdf]


A threeparty communication problem.
J. Computer and System Sciences 57:399401,
1998.


Asymptotically good codes correcting
insertions, deletions and transpositions, with
D. Zuckerman. IEEE Transactions on Information
Theory 45(7):25522557, 1999. [abstract/ps/pdf]
Preliminary version: Proc. 8th SODA 669674,
1997.


Verification of Identities, with
S. Rajagopalan. SIAM J. Computing 29(4):11551163,
2000. Preliminary version: Proc. 37th FOCS 612616,
1996.


Bounds on the Chromatic Polynomial and on
the Number of Acyclic Orientations of a Graph,
with N. Kahale. Combinatorica 16(3):383397,
1996. [ps/pdf]


Splitters and nearoptimal
derandomization, with M. Naor and
A. Srinivasan. Proc. 36th FOCS 182191, 1995. [abstract/ps/pdf]


Fairness in Scheduling, with
M. Ajtai, J. Aspnes, M. Naor, Y. Rabani and
O. Waarts. J. of Algorithms 29(2):306357, 1998. [ps/pdf]
Preliminary version: Proc. 6th SODA 477485,
1995.


A Coding Theorem for Distributed
Computation, with S. Rajagopalan. Proc. 26th
STOC 790799, 1994. [ps/pdf]


A product theorem for intersection
families. European J. of Combinatorics
15:579586, 1994.


Signal propagation and noisy
circuits, with W. Evans. IEEE Transactions on
Information Theory 45(7) 23672373,
1999. Preliminary version: Proc. 34th FOCS
594603, 1993.


Coding for Interactive Communication.
Special issue on Codes and Complexity of the IEEE
Transactions on Information Theory 42(6) Part
I:17451756, 1996. [ps/pdf]
Preliminary versions: Proc. 33rd FOCS 724733,
1992 and Proc. 25th STOC 747756, 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:231240, 1993.


An equipartition of planar sets.
Discrete and Computational Geometry 9:257266,
1993.


Sample spaces uniform on
neighborhoods. Proc. 24th STOC 1725,
1992.


The Maintenance of Common Data in a
Distributed System, with B. Awerbuch.
J. ACM 44(1):86103, 1997. [ps/pdf]
Preliminary version: Proc. 32nd FOCS 505514,
1991.


Crossing families, with B. Aronov,
P. Erdös, W. Goddard, D. J. Kleitman,
M. Klugerman and J. Pach. Combinatorica
14(2):127134, 1994. Preliminary version:
Proc. 7th ACM Symp. Comp. Geom. 351356,
1991.


Optimal randomized algorithms for local
sorting and setmaxima, with W. Goddard,
C. Kenyon and V. King.
SIAM J. Computing
22(2):272283, 1993. Preliminary version:
Proc. 22nd STOC 4553, 1990.


Sorting on a ring of processors, with
Y. Mansour. J. of Algorithms 11:622630,
1990.
