Leonard J. Schulman
Professor of Computer Science
California Institute of Technology

Caltech Crest

Research

Courses

Contact Information

Center for the
Mathematics of
Information

Institute for
Quantum
Information

CS Theory Group

Graduate Study

Links

Bio - Research - Essays - Editorial Work

Bio

Leonard J. Schulman received the B.Sc. in Mathematics in 1988 and the Ph.D. in Applied Mathematics in 1992, both from the Massachusetts Institute of Technology. Since 2000 he has been on the faculty of the California Institute of Technology. He has also held appointments at UC Berkeley, the Weizmann Institute of Science, the Georgia Institute of Technology, and the Mathematical Sciences Research Institute. He has received the MIT Bucsela prize in mathematics, an NSF mathematical sciences postdoctoral fellowship, an NSF CAREER award, and the IEEE Schelkunoff prize. He is the director of the Caltech Center for the Mathematics of Information, is on the faculty of the Institute for Quantum Information and Matter, and serves as Editor-in-Chief of the SIAM Journal on Computing. His research is in several overlapping areas: algorithms and communication protocols; combinatorics and probability; coding and information theory; quantum computation.

Research

*

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, 2014, to appear.

*

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

*

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

*

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, 2012. Theory of Computing, Special Issue on Boolean Functions, 10(3):55-75, 2014.

*

Allocation of Divisible Goods under Lexicographic Preferences, with V. Vazirani. Preprint, 2012.

*

Optimal Coding for Streaming Authentication and Interactive Communication, with M. Franklin, R. Gelles and R. Ostrovsky. Preprint, 2012. Proc. 33rd Crypto 258-276, 2013. IEEE Trans. Information Theory, 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. Discrete and Computational Geometry, to appear.

*

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, 2012. Earlier preprint (for k=2), 2008. Proc. 5th ITCS 207-223, 2014.

*

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] Preprint: [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. Preprint: [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. Preprint: [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.


Link to all tech reports on the ArXiv

Essays

*

Quantum algorithms: a test for the laws of physics, ENGenious Issue 7 Winter 2010.

*

A bit chilly, Nature 438:431-432, 24 November 2005.

Editorial Work

Editor-in-Chief, SIAM Journal on Computing

Past service on editorial boards:
Journal of the ACM
ACM Transactions on Algorithms
SIAM Journal on Discrete Mathematics
ACM Transactions on Computation Theory

Glossary

Crypto: IACR International Cryptology Conference.
ESA: European Symposium on Algorithms.
FOCS: IEEE Symposium on Foundations of Computer Science.
FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science
IPCO: Conference on Integer Programming and Combinatorial Optimization.
ISIT: IEEE International Symposium on Information Theory.
ITCS: Innovations in Theoretical Computer Science Conference.
PODC: ACM Symposium on Principles of Distributed Computing.
SODA: SIAM-ACM Symposium on Discrete Algorithms.
STOC: ACM Symposium on Theory of Computing.

Fantasy, abandoned by reason, produces impossible monsters; united with it, she is the mother of the arts and the origin of marvels. - Goya