|
Center for the
Mathematics of
Information
CS Theory
Group
Graduate Study
Links
|
|
Bio - Contact Info -
Research - Essays - Editorial Work - Students - Glossary
|
|
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 Israel Institute for
Advanced Studies. He is a Fellow of SIAM, the Society for Industrial
and Applied Mathematics. Awards include the IEEE
Schelkunoff Prize (2004), ACM Notable Paper (2012), UAI Best Paper
Award (2016), and FOCS Test of Time Award (2022).
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.
|  |
|
| Contact Information
|
1200 E. California Blvd., MC 305-16, Pasadena CA 91125, USA
Office: Annenberg 317, (626) 395 6839.
Studio: Annenberg 322. schulman@caltech.edu
ORCID: 0000-0001-9901-2797
Secretary: Sumaia Abedin, (626) 395 6704, sabedin@caltech.edu
|
| Research
|
|
Diversity in Evolutionary Dynamics,
with Y. Rabani and A. Sinclair. Proc. ITCS 2025, to appear. (Preliminary version)
|
|
|
Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity,
with S. L. Gordon, E. Jahn, B. Mazaheri and Y. Rabani. Proc. 37th COLT.
Proc. Machine Learning
Research Vol. 247:2071-2091, 2024.
|
|
|
Identifiability of Product of Experts Models,
with S. L. Gordon, M. Kant, E. Ma and A. Staicu. Proc. 27th AISTATS.
Proc. Machine Learning
Research Vol. 238:4492-4500, 2024.
|
|
|
Causal Discovery under Latent Class Confounding,
with B. Mazaheri, S. L. Gordon and Y. Rabani. (Preliminary version)
|
|
|
Causal Inference Despite Limited Global Confounding via Mixture Models,
with S. L. Gordon, B. Mazaheri and Y. Rabani. Proc. CLeaR 2023
|
|
|
Hadamard Extensions and the Identification of Mixtures of Product Distributions,
with S. L. Gordon. IEEE Transactions on Information Theory 68(6):4085-4089, 2022.
(Or here.)
|
|
|
A Refined Approximation for Euclidean k-Means,
with F. Grandoni, R. Ostrovsky, Y. Rabani and R. Venkat.
Information Processing Letters Vol. 176, 106251, 2022.
(Or here.)
|
|
|
Source Identification for Mixtures of Product Distributions,
with S. L. Gordon, B. Mazaheri and Y. Rabani.
Proc. 34th COLT. Proc. Machine Learning Research Vol. 134:2193-2216, 2021.
|
|
|
Condition Number Bounds for Causal Inference,
with S. L. Gordon, V. Kumar and P. Srivastava. Proc. 37th UAI.
Proc. Machine Learning Research Vol. 161:1948-1957, 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.)
|
|
|
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 134:361-375, 2022. (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.)
Erratum. Best Paper Award.
|
|
|
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.)
|
|
|
|
|
|
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.
|
|
|
|
|
|
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.
|
|
|
Preprint (for k=2), 2008.
|
|
|
On a capacitated multivehicle routing problem,
with X. Gao.
Proc. 27th PODC 175-184, 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.
|
|
|
Updated
|
|
|
|
|
|
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.)
|
|
|
|
|
|
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. FOCS Test of Time Award.
|
|
|
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
|
|
|
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, Jingcheng Liu.
Students: David Cardoze, Elitza Maneva, Miroslav Dudik, Xiaojie Gao, Massimo Franceschetti,
Po-Shen Loh, Chih-Kai Kevin Ko, Jeremy Hurwitz, Euiwoong Lee, Zhaorong Jin,
Will Hoza, Karthik Karnik, Will Overman, Vinayak Kumar, Jenish Mehta, Andrew Lin, Lin Lin Lee, Ann Caplin,
Charlotte Park, Manav Kant, Eric Ma, Andrei Staicu, and current students.
|
Glossary
|
|
AISTATS: Conference on Artificial Intelligence and Statistics
COLT: Conference on Learning Theory
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."
|
|
