Caltech logo

Leonard J. Schulman
Professor of Computer Science


Center for the
Mathematics of

CS Theory Group

CS Theory Seminar

Graduate Study


Bio - Contact Info - Research - Essays - Editorial Work - Students - Glossary


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 the Israel Institute for Advanced Studies, UC Berkeley, the Weizmann Institute of Science, and the Georgia Institute of Technology. From 2003 to 2017 he directed the Caltech Center for the Mathematics of Information, and from 2013 through 2018 he served two terms as Editor-in-Chief of the SIAM Journal on Computing. His research is in several overlapping areas: algorithms; coding and communication; combinatorics and probability; quantum computation. Honors include: MIT Bucsela Prize ('88), NSF Mathematical Sciences Postdoctoral Fellowship ('92), NSF CAREER ('99), IEEE Schelkunoff Prize ('04), ACM Notable Paper ('12). (Photo)

Contact Information

1200 E. California Blvd., MC 305-16, Pasadena CA 91125, USA
Office: Annenberg 317, (626) 395 6839. Studio: Annenberg 322.
ORCID: 0000-0001-9901-2797
Secretary: Linda Taddeo. Annenberg 343, (626) 395 6704,
Instructions for people who need reference letters: please follow Ravi Vakil's helpful guidelines


* Hadamard Extensions and the Identification of Mixtures of Product Distributions, with S. L. Gordon. (Preprint, 2021.)
* The invisible hand of Laplace: the role of market structure in price convergence and oscillation, with Y. Rabani. J. Mathematical Economics 102475, 2021. (Preprint, 2020.)
* Source Identification for Mixtures of Product Distributions, with S. L. Gordon, B. Mazaheri and Y. Rabani. (Preprint, 2020.)
* The Sparse Hausdorff Moment Problem, with S. L. Gordon, B. Mazaheri and Y. Rabani. (Preprint, 2020.)
* Edge Expansion and Spectral Gap of Nonnegative Matrices, with J. C. Mehta. Proc. 31st SODA 1200-1213, 2020.
* Online codes for analog signals, with P. Srivastava. IEEE Transactions on Information Theory 65(10):6633-6649, 2019.
* Quasi-random multilinear polynomials, with G. Kalai. Israel J. Math. 230(1):195-211, 2019.
* Explicit Binary Tree Codes with Polylogarithmic Size Alphabet, with G. Cohen and B. Haeupler. Proc. 50th STOC 535-544, 2018.
* Learning Dynamics and the Co-Evolution of Competing Sexual Species, with G. Piliouras. Proc. 9th ITCS 59:1-59:3, 2018. (Full version.)
* Quasi-regular sequences and optimal schedules for security games, with D. Kempe and O. Tamuz. Proc. 29th SODA 1625-1644, 2018.
* The duality gap for two-team zero-sum games, with U. Vazirani. Games and Economic Behavior 115:336-345, 2019. (Proc. 8th ITCS 56:1-56:8, 2017.)
* Convergence of Incentive-Driven Dynamics in Fisher Markets, with K. Dvijotham and Y. Rabani. Special Issue of Games and Economic Behavior, 2020. (Proc. 28th SODA 554-567, 2017.)
* Extractors for Near Logarithmic Min-Entropy, with G. Cohen. Proc. 57th FOCS 178-187, 2016.
* Stability of Causal Inference, with P. Srivastava. Proc. 32nd UAI 666-675, 2016. (Or here.)
* Symbolic integration and the complexity of computing averages, with A. Sinclair and P. Srivastava. Proc. 56th FOCS 1231-1245, 2015.
* (Proc. 47th STOC 831-840, 2015.)
* One-Shot Bargaining Mechanisms, with Y. Babichenko. (Preprint, 2015.)
ACM DL Author-ize service Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
STOC '15 Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015
* The Adversarial Noise Threshold for Distributed Protocols, with W. M. Hoza. Proc. 27th SODA 240-258, 2016.
* Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions, with U. Bhaskar, K. Ligett and C. Swamy. Special Issue of Games and Economic Behavior, 2018.
ACM DL Author-ize service Tree codes and a conjecture on exponential sums
Cristopher Moore, Leonard J. Schulman
ITCS '14 Proceedings of the 5th conference on Innovations in theoretical computer science, 2014
* The Network Improvement Problem for Equilibrium Routing, with U. Bhaskar and K. Ligett. 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. Theory of Computing, Special Issue on Boolean Functions, 10(3):55-75, 2014.
* Allocation of Divisible Goods under Lexicographic Preferences, with V. Vazirani. Proc. FSTTCS 543-559, 2015.
* Optimal Coding for Streaming Authentication and Interactive Communication, with M. Franklin, R. Gelles and R. Ostrovsky. IEEE Trans. Information Theory 61(1): 133-145, 2015. (Proc. 33rd Crypto 258-276, 2013.)
* 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. Discrete and Computational Geometry 52(2):366-389, 2014. (Proc. 18th ESA II:87-99, 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
* Muirhead-Rado inequality for compact groups. Positivity 13:559-574, 2009.
ACM DL Author-ize service Learning mixtures of arbitrary distributions over large discrete domains
Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
ITCS '14 Proceedings of the 5th conference on Innovations in theoretical computer science, 2014
Preprint (for k=2), 2008.
* On a capacitated multivehicle routing problem, with X. Gao. Proc. 27th PODC 175-184, 2008.
ACM DL Author-ize serviceOn partitioning graphs via single commodity flows
Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi
STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing 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. Long version: Discrete and Computational Geometry 42(4):594-614, 2009. (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.
* Imaging geometry through dynamics: the observable representation, with B. Gaveau and L. S. Schulman. J. Physics A 39(33):10307-10321, 2006.
* (Proc. 47th FOCS 165-174, 2006.) ACM 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. Long version: SIAM J. Computing 36(6) 1729-1747, 2007. 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.
* 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.)
* Improved expansion of random Cayley graphs, with P.-S. Loh. Discrete Mathematics and Theoretical Computer Science 6(2):523-528, 2004.
* Rapid near-optimal VQ design with a deterministic data net, with M. Effros. Proc. ISIT, 2004. Deterministic clustering with data nets, (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. (Proc. 15th SODA 1106-1115, 2004.)
* 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.
* 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. IEEE AP-S Antennas and Propagation Society Symposium 2002. S. A. Schelkunoff Transactions Prize Paper Award 2004.
* 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. (Proc. 17th CCC 175-183, 2002.)
* Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem, with M. Grigni, M. Vazirani and U. Vazirani. Combinatorica 24(1):137-154, 2004. (Proc. 33'rd STOC 68-74, 2001.)
* The Vector Partition Problem for Convex Objective Functions, with S. Onn. Mathematics of Operations Research 26(3):583-590, 2001.
* A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians, with S. Dasgupta. J. Machine Learning Research 8:203-226, 2007. (Proc. 16th UAI 152-159, 2000.)
* (Proc. 32nd STOC 697-704, 2000.)
* Broadcasting on Trees and the Ising Model, with W. Evans, C. Kenyon and Y. Peres. Annals of Applied Probability 10(2):410-433, 2000.
ACM DL Author-ize serviceClustering for edge-cost minimization (extended abstract)
Leonard J. Schulman
STOC '00 Proceedings of the thirty-second annual ACM symposium on theory of computing 547-555, 2000
ACM DL Author-ize service Molecular scale heat engines and scalable quantum computation
Leonard J. Schulman, Umesh V. Vazirani
STOC '99 Proceedings of the thirty-first annual ACM symposium on theory of computing 322-329, 1999
* A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution, with V. Vazirani. Combinatorica 25(4):465-486, 2005. (Proc. 31st STOC 288-294, 1999.)
* The quantum communication complexity of sampling, with A. Ambainis, A. Ta-Shma, U. Vazirani and A. Wigderson. SIAM J. Computing 32:1570-1585, 2003. (Proc. 39th FOCS 342-351, 1998.)
* Pattern Matching for Spatial Point Sets, with D. Cardoze. Proc. 39th FOCS 156-165, 1998. Updated
* 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. (Proc. 8th SODA 669-674, 1997.)
* Verification of Identities, with S. Rajagopalan. SIAM J. Computing 29(4):1155-1163, 2000. (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.
* Splitters and near-optimal derandomization, with M. Naor and A. Srinivasan. Proc. 36th FOCS 182-191, 1995.
* Fairness in Scheduling, with M. Ajtai, J. Aspnes, M. Naor, Y. Rabani and O. Waarts. J. of Algorithms 29(2):306-357, 1998. (Proc. 6th SODA 477-485, 1995.)
ACM DL Author-ize service A coding theorem for distributed computation
Sridhar Rajagopalan, Leonard Schulman
STOC '94 Proceedings of the twenty-sixth annual ACM symposium on theory of computing 790-799, 1994
* 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. Or here with proper figures. (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. (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.
* (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. (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. (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 preprints on the ArXiv
Link to Computer Science publication listings at DBLP


* 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

Past service on editorial boards:
Editor-in-Chief, SIAM Journal on Computing
Journal of the ACM
ACM Transactions on Algorithms
SIAM Journal on Discrete Mathematics
ACM Transactions on Computation Theory

Postdocs and students I've worked with

Postdocs: Ashwin Nayak, Yaoyun Shi, Sean Hallgren, Jie Gao, Michael Langberg, Nevin Kapur, Noam Berger, Eyal Rozenman, Chaitanya Swamy, Ben Recht, Yi-Kai Liu, Dan Feldman, Gorjan Alagic, Yakov Babichenko, Umang Bhaskar, Siddharth Barman, Stacey Jeffery, Georgios Piliouras, Krishnamurthy Dvijotham, Gil Cohen, Piyush Srivastava. Students: David Cardoze, Miroslav Dudik, Xiaojie Gao, Massimo Franceschetti, Po-Shen Loh, Chih-Kai Kevin Ko, Jeremy Hurwitz, Euiwoong Lee, Zhaorong Jin, William Hoza, and current students.


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: Conference on Innovations in Theoretical Computer Science
PODC: ACM Symposium on Principles of Distributed Computing
SODA: SIAM-ACM Symposium on Discrete Algorithms
STOC: ACM Symposium on Theory of Computing
UAI: Conference on Uncertainty in Artificial Intelligence

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

Tennis balls have spin 1/2
Maria Sharapova upon winning the 2006 US Open women's singles title: "Well, I figured I lost the last four times I played against Justine, so everything that I did in the last four times, I had to flip it 360 and to do the total opposite. And that's just what I tried to do today."

A letter from Gauss to Dirichlet, September 9, 1826 (excerpt):
"I wish you from my heart a situation in which you can, as much as possible, remain the master of your time and choice of your tasks."