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


Quasirandom multilinear polynomials, with G. Kalai.
Israel J. Math., 2018.
Preprint.


Explicit Binary Tree Codes with Polylogarithmic Size Alphabet,
with G. Cohen and B. Haeupler.
Proc. 50th STOC 535544, 2018.


Learning Dynamics and the CoEvolution of Competing Sexual Species, with G. Piliouras.
Proc. 9th ITCS 59:159:3, 2018. Preprint,
2017.


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


Quasiregular sequences and optimal schedules for
security games, with D. Kempe and O. Tamuz.
Proc. 29th SODA 16251644, 2018. Preprint,
2016.


The duality gap for twoteam zerosum games, with U. Vazirani.
Games and Economic Behavior, 2019.
Proc. 8th ITCS 56:156:8, 2017.


Convergence of IncentiveDriven Dynamics in Fisher
Markets, with K. Dvijotham and Y. Rabani.
Proc. 28th SODA 554567, 2017. Preprint,
2016.


Extractors for Near Logarithmic MinEntropy, with
G. Cohen.
Proc. 57th FOCS 178187, 2016. Preprint,
2016.


Stability of Causal Inference, with P. Srivastava.
Proc. 32nd UAI 666675, 2016.
(Or here.)
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 12311245, 2015.


Preprint,
2015. Proc. 47th STOC 831840, 2015.


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


Preprint, 2015.


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


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.
Proc. 55th FOCS 3140, 2014. Preprint, 2014.


Preprint, 2013.


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


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


Allocation of Divisible Goods under Lexicographic
Preferences, with V. Vazirani.
Proc. FSTTCS 543559, 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): 133145, 2015.
Proc. 33rd Crypto 258276, 2013.
Preprint, 2012.


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 (or here). (Correction)


Volume in general metric spaces, with
I. Abraham, Y. Bartal and O. Neiman.
Discrete and Computational Geometry 52(2):366389, 2014.
Proc. 18th ESA,
II:8799 (Springer LNCS 6347), 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
(or here).


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


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


Preprint,
2012. Earlier
preprint (for k=2), 2008.


On a capacitated multivehicle routing problem,
with X. Gao.
Proc. 27th PODC 175184, 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. Long
version: Discrete
and Computational Geometry 42(4):594614, 2009. Short version: Proc. 19th Canadian
Conf. Computational Geometry 2528, 2007.


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


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


Proc.
47th FOCS 165174, 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):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. Long
version: SIAM
J. Computing 36(6) 17291747, 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)
18421864, 2008. Proc. 46th
FOCS 479488, 2005. Preprint


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


Rapid nearoptimal VQ design with a deterministic data net,
with M. Effros.
Proc. ISIT, 2004.
Deterministic clustering with data nets, 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. The Power of Basis Selection in
Fourier Sampling: Hidden Subgroup Problems in
Affine Groups, Proc. 15th SODA 11061115,
2004. Preprint


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


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. IEEE APS
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):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. Proc. 17th Conference on Computational
Complexity 175183, 2002. Preprint, 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:


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


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


Proc. 32nd STOC 697704, 2000.


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


Updated


Preprint, 1998


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


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


Pattern Matching for Spatial Point
Sets, with D. Cardoze. Proc. 39th FOCS
156165, 1998. Updated


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. Proc. 8th SODA 669674, 1997.


Verification of Identities, with
S. Rajagopalan.
SIAM J. Computing 29(4):11551163,
2000. 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. Or here.


Splitters and nearoptimal
derandomization, with M. Naor and
A. Srinivasan. Proc. 36th FOCS 182191, 1995.


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




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. Or here with proper figures. 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.
Combines 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.


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.
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. Proc. 22nd STOC 4553, 1990.


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


Link to all preprints on the ArXiv

Link to Computer Science publication listings at DBLP

Essays


Editorial Work

Past service on editorial boards:
EditorinChief, 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, YiKai 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,
PoShen Loh, ChihKai Kevin Ko, Jeremy Hurwitz, Euiwoong Lee, Zhaorong Jin,
William Hoza, and current students.

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

