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

CS Theory Seminar

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. During AY 2017-18 he is in residence at the Israel Institute for Advanced Studies, generously supported by a EURIAS Senior Fellowship. He has also held appointments at 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 the present he has served 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. Honors include: MIT Bucsela Prize ('88), NSF Mathematical Sciences Postdoctoral Fellowship ('92), NSF CAREER ('99), IEEE Schelkunoff Prize ('04), ACM Notable Paper ('12), UAI Best Paper Award ('16).

Research

*

Online codes for analog signals, with P. Srivastava. Preprint, 2017.

*

Quasi-regular sequences and optimal schedules for security games, with D. Kempe and O. Tamuz. Proc. 29th SODA, 2018, to appear. Preprint, 2016.

*

The duality gap for two-team zero-sum games, with U. Vazirani. Proc. 8th ITCS, 2017.

*

Convergence of Incentive-Driven Dynamics in Fisher Markets, with K. Dvijotham and Y. Rabani. Proc. 28th SODA 554-567, 2017. Preprint, 2016.

*

Extractors for Near Logarithmic Min-Entropy, with G. Cohen. Proc. 57th FOCS 178-187, 2016. Preprint, 2016.

*

Stability of Causal Inference, with P. Srivastava. Proc. 32nd UAI 666-675, 2016. Best Paper Award

*

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

*

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

*

One-Shot Bargaining Mechanisms, with Y. Babichenko. Preprint, 2015.

*

Preprint, 2015. Proc. 47th STOC 831-840, 2015.

*

ACM DL Author-ize serviceLearning 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
Preprint, 2015.

*

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

*

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

*

ACM DL Author-ize serviceTree 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
Preprint, 2013.

*

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

*

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. Preprint, 2012.

*

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

*

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. Preprint, 2012.

*

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 (Springer LNCS 6347), 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 (or here).

*

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 serviceLearning 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, 2012. Earlier 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. Short version: 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. Preprint

*

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. Preprint

*

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. The Power of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups, Proc. 15th SODA 1106-1115, 2004. Preprint

*

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. Or here.

*

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

*

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 Conference on Computational Complexity 175-183, 2002. Preprint, 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:
ACM DL Author-ize serviceQuantum mechanical algorithms for the nonabelian hidden subgroup problem
Michelangelo Grigni, Leonard Schulman, Monica Vazirani, Umesh Vazirani
STOC '01 Proceedings of the thirty-third annual ACM symposium on theory of computing 68-74, 2001

*

The Vector Partition Problem for Convex Objective Functions, with S. Onn. Mathematics of Operations Research 26(3):583-590, 2001. Or here.

*

A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians, with S. Dasgupta. J. Machine Learning Research 8:203-226, 2007. A two-round variant of EM for Gaussian mixtures, Proc. 16th UAI (Conference on Uncertainty in Artificial Intelligence) 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
Updated

*

ACM DL Author-ize serviceMolecular 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
Preprint, 1998

*

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. Or here.

*

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. Or here.

*

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 serviceA 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. 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. Combines 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

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: 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