KS
Markov type
 $L_p$ compression, traveling
salesmen, and stable walks — Naor, Peres '09
 Embeddings of discrete groups
and the speed of random walks — Naor, Peres '07
 The wreath product of Z with Z
has Hilbert compression exponent 2/3 — Austin, Naor, Peres
'07
 Markov chains in smooth
Banach spaces and Gromov hyperbolic metric spaces — Naor, Peres,
Schramm, Sheffield '04
 Markov
chains, Riesz transforms and Lipschitz maps — Ball, GAFA'91
***
 Inapproximability of NPcomplete problems,
discrete Fourier analysis, and geometry — Khot, '10
 Constructive algorithms for discrepancy minimization
— Bansal, '10
 How long does it take to catch a
wild kangaroo? — Montenegro, Tetali, STOC'09
 Random
walks and an O*(n^5) volume algorithm for convex bodies — Kannan,
Lovasz, Simonovits, Rand. Struct. Alg.'98
 Hitandrun
mixes fast — Lovasz, J. Math. Prog.'99
 Maximizing
quadratic progams: extending Grothendieck's inequality —
Charikar, Wirth, FOCS'04
 $O(\sqrt{\log n})$
approximation to sparsest cut in $\tilde{O}(n^2)$ time —
Arora, Hazan, Kale, FOCS'04
Mixture
 Kakeya sets, new mergers and old extractors, Dvir, Wigderson, FOCS'08
 On the size of Kakeya sets in finite fields, Dvir, J.Amer.Math.Soc.'08
 Ramanujan
graphs — Lubotzky, Phillips, Sarnak, Combinatorica'87
 Expanders via random
spanning trees — Goyal, Rademacher, Vempala, '08
 Links to how to generate random spanning trees simply
 Sampling to estimate
arbitrary subset sums — Duffield, Lund, Thorup, '05
 Fast
Dimension Reduction Using Rademacher Series on Dual BCH Codes
— Ailon, Liberty, SODA'08
 Clustering for Metric and NonMetric distance
measures — Ackermann, Blomer, Sohler, SODA'08
 Shuffling, carry distribution and Young tableux — See
Diaconis (and Mitzenmacher blog)
 Graph limits and parameter testing — Lovasz, Szegedy, Sos, Vesztergombi, Borgs, Chayes, STOC'06

Estimating the Largest Eigenvalue by the Power and Lanczos
Algorithms with a Random Start — Kuczynski, Wozniakowski,
SIAM'92
 Randomized
approximation schemes for cuts and flows in capacitated graphs
— Benczur, Karger
 The mixing rate of Markov chains, an isoperimetric
inequality, and computing the volume — Lovasz,
Simonovits, FOCS'90
 Random walks in convex body and an improved volume
algorithm — Lovasz, Simonovits, Random Struct. Algorithms
'93

Towards 3query locally decodable codes of subexponential
length — Yekhanin, STOC'07

A combinatorial, primaldual approach to semidefinite programs
— Arora, Kale, STOC'07

On the submodularity of influence in social networks —
Mossel, Roch, STOC'07
 Pointers to approximations of submodular funcs by greedy
algs

Simple deterministic approximation algorithms for counting
matchings — Bayati, et al, STOC'07

Fourier meets Mobius: fast subset convolution —
Bjorklund, et al, STOC'07

Faster integer multiplication — Furer, STOC'07

First to market is not everything: an analysis of preferential
attachment with fitness — Borgs, et al, STOC'07
 PolyaUrn processes
 Pointers to Janson on Theory of Branching Processes
 Solving linear systems ..., Spielman, Teng
 Sparsification and graph approximation
Algorithms with distributed stability
Sketching, streaming, sensing, sparse approximations
 Declaring
Independence via the Sketching of Sketches — Indyk,
McGregor, SODA'08
 Improved
Approximation Algorithms for Large Matrices via Random
Projections — Sarlos, FOCS'06
 Databasefriendly
random projections — Achlioptas, J. CSS'03
 A remark on
compressed sensing — Kashin, Temlyakov, Note'07
 The
space complexity of approximating the frequency moments —
Alon, Matias, Szegedy, STOC'96
 Historic compressed sensing pointers
 Rubobust Uncertainty Principles ..., Candes, Romberg, Tao
 Compressed Sensing, Donoho
 Algorithmic Linear Dimension Reduction in the L1 Norm for
Sparse Vectors, Gilbert
 One sketch for all: fast algorithms for compressed sensing,
Gilbert, Vershynin
 The Dantzig selector: statistical estimation when ..., Candes,
Tao
 Error Correcting via Linear Programming, Candes, Rudelson, Tao,
Vershynin
 Decoding by Linear Programming, Candes, Tao
 Near Optimal Signal Recovery From Random Projections ...,
Candes, Tao
 Compressed Sensing, Candes
 Combinatorial Algorithms for Compressed Sensing, Cormode
Matrix/operator geometry, computation, and approximation
 Approximating orthogonal
matrices by permutation matrices — Barvinok, '05
 Faster Least Squares
Approximation — Drineas, Mahoney, Muthukrishnan, Sarlos '08
 Relativeerror
CUR matrix decompositions — Drineas, Mahoney, Muthukrishnan,
SIAM'08
 CUR matrix
decompositions for improved data analysis — Mahoney, Drineas,
PNAS'08
 Sampling
algorithms for L2 regression and applications — Drineas, Mahoney,
Muthukrishnan, SODA'06
 Approximate
nearest neighbors and the fast JohnsonLindenstrauss
transform — Ailon, Chazelle, STOC'06

The condition number of a randomly perturbed matrix —
Tao, Vu, STOC'07

An introduction to the conjugate gradient method without the
agonizing pain — Shewchuk '94

Note on a principal axis transformation for nonhermitian
matrices — Williamson, AMS'39

A principal axis transformation for nonhermitian matrices
— Eckart, Young, AMS'39
Primaldual methods in optimization
 Convexity and
Commuting Hamiltonians — Atiyah '82
 Convexity
properties of the moment mapping — Guillemin, Sternberg '82
 Convexity
properties of the moment mapping, II — Guillemin, Sternberg '84
 Convexity
properties of the moment mapping, III — Kirwan '84
 Stateless
Distributed Gradient Descent for Positive Linear Programs —
Awerbuch, Khandekar, STOC'08
 The
Nonlinear Geometry of Linear Programming. I Affine and Projective
Scaling Trajectories — Bayer, Lagarias, AMS'89
 The
Nonlinear Geometry of Linear Programming. II Legendre Transform
Coordinates and Central Trajectories — Bayer, Lagarias,
AMS'89
 The
Nonlinear Geometry of Linear Programming. III Projective Legendre
Transform Coordinates and Hilbert Geometry — Lagarias,
AMS'90
 Karmarkar's
linear programming algorithm and Newton's method — Bayer, Lagarias,
J. Mathematical Programming '05
 A
modification of Karmarkar's linear programming algorithm —
Vanderbei, Meketon, Freedman, ALGORITHMICA'86
 A new
polynomialtime algorithm for linear programming — Karmarkar,
COMBINATORICA'84
Multiplicative weight updates
Spectral Graph Theory
 Spectral Graph Theory, Chung
 Chapter 1:
Eigenvalues and the Laplacian of a graph
 Chapter 2:
Isoperimetric problems
 Chapter 3:
Diameters and eigenvalues
 Chapter 4:
Paths, flows and routing
 Chapter 5: Eigenvalues and quasirandomness (major
rewrite)
 Chapter 6: Expanders and explicit constructions
 Chapter 7: Eigenvalues of symmetrical graphs
 Chapter 8: Eigenvalues of subgraphs with boundary
conditions
 Chapter 9: Harnack inequalities
 Chapter 10: Heat kernels
 Chapter 11: Sobolev inequalities
 Chapter 12: Advanced techniques on random walks
 Bibliography
 Finding sparse cuts locally
using evolving sets — Andersen, Peres, STOC'09
 TwiceRamanujan sparsifiers,
Batson, Spielman, Srivastava, 2008
 Max Cut and the Smallest Eigenvalue,
Trevisan, '08
 Random
walks and the effective resistance of networks — Tetali,
CONF'91
 Graph Sparsification
by Effective Resistances — Spielman, Srivastava,
STOC'08
 Local graph partitioning using PageRank vectors
— Andersen, Chung, Lang, FOCS'06
 Scaling personalized web search — Jeh, Widom '??
 Bookmarkcoloring algorithm for Personalized PageRank
Computing — Berhin '??
 Spectral Partitioning, Eigenvalue Bounds, and Circle
Packings for Graphs of Bounded Genus — Kelner,
STOC'04
 A
spectral technique for coloring random 3colorable graphs
— Alon, Kahale, STOC'94
 Geometric
representations of graphs — Lovasz, Vesztergombi,
Survey'02

The Path Resistance Method for Bounding the Smallest Nontrivial
Eigenvalue of a Laplacian — Guattery, Leighton, Miller,
SODA'96

A short proof of the planarity characterization of Colin de
Verdiere — van der Holst, J. of Comb. Theory'95

On the null space of a Colin de Verdiere matrix — Lovasz,
Schrijver, Annales de l'Institute Fourier'99
 The
PageRank Citation Ranking: Bringing Order to the Web —
Page, Brin, Motwani, Winograd, Stanford'99
 Authoritative
sources in a hyperlinked environment — J. Kleinberg,
SODA'98
 Rubber
bands, convex embeddings and graph connectivity — Linial,
Lovasz, Wigderson, Combinatorica'88
 Short Paths
in Expander Graphs — Kleinberg, Rubinfeld, FOCS'96
Sparsest cut and multicommodity flows
 Oblivious routing in the Lpnorm
— Englert, Racke, FOCS'09
 Minimizing
average latency in oblivious routing — Harsha, Hayes, Narayanan,
Racke, Radhakrishnan, SODA'08
 Optimal
Hierarchical Decompositions for Congestion Minimization in
Networks — Raecke, STOC'08
 New lower bounds
for oblivious routing in undirected graphs — Hajiaghayi,
Kleinberg, Leighton, Raecke, SODA'06
 Multicommodity
maxflow mincut theorems and their use in designing approximation
algorithms
— Leighton, Rao, JACM'99
 On
Partitioning Graphs via SingleCommodity Flows,
Orecchia, Schulman, Vazirani, Vishnoi, STOC'08
 A
combinatorial, primaldual approach to semidefinite programs
— Arora, Kale, STOC'07
 Graph
partitioning using single commodity flows — Vazirani,
Khandekar, Rao, STOC'06
 O(\sqrt{\log n)}
approximation to SPARSEST CUT in O(n^2) time — Arora,
Hazan, Kale, FOCS'04
 Expander
Flows, Geometric Embeddings and Graph Partitioning —
Arora, Rao, Vazirani, STOC'04

A Polylogarithmic Approximation of the Minimum Bisection
— Feige, Krauthgamer, SIAMJoC'02
 Multicommodity
maxflow mincut theorems and their use in designing approximation
algorithms — Leighton, Rao, JACM'99
Partitioning heuristics
Convex geometry
Functional and Harmonic Analysis
Probability
 A constructive proof of the
general Lovasz Local Lemma — Moser, Tardos, '09
 Reversible
Markov Chains and Random Walks on Graphs — Aldous, Fill, Book'??
 On the notion of recurrence in discrete stochastic processes — Kac, Bull. AMS'47

Balanced allocations: the weighted case — Talwar, Wieder,
STOC'07
 Chance and
stability – Stable distributions and their applications
— Uchaikin, Zolotarev, Book'99
 On
the sum of nonnegative independent random variables with unbounded
variance — Feige'03
 The
Markov chain Monte Carlo method — Jerrum, Sinclair,
'96
 The Diameter of a ScaleFree Random Graph
— Bollobas, Riordan, Combinatorica'04
 Correlation Inequalities on Some
Partially Ordered Sets — Fortuin, Kasteleyn, Ginibre,
'71
 On Concentration of
Probability — Svante Janson, SURVEY'00
Groups, algebra and geometry
Game theory
Stochastic Optimization
 A Generalization of Janson Inequalities and its
Application to Finding Shortest Paths — Subramanian,
SODA'99 (5/31/2007)
 An FPTAS for the Mostlikelyontime Path
— Brand, Kara, MERL/TR (5/22/2007)
 A New Approach to Stochastic Shortest Paths
— Brand, Kelner, Mitzenmacher, Nikolova, ESA'06
(5/17/2007)
 Optimal Route Planning under Uncertainty —
Nikolova, Brand, Karger, ICAPS'06 (5/15/2007)
Complexity
Dynamic optimality
 A lower bound framework for binary search trees with
rotations — Derryberry, Sleator, Wang, CMUTR'05
(4/28/07)
 Lower bounds for accessing binary search trees with
rotations — Wilber, SIAM JCOMP'89, Notes (2/27/07)
 Dynamic Optimality – Almost —
Demaine, Harmon, Iacono, Patrascu, FOCS'04, Notes (2/25/07)
 Data Structures and Network Algorithms —
Tarjan, CBMSNSF'83, Linkcut Trees: Sections 5.1,5.2,5.4
(2/25/07)
 Rotation Distance,
Triangulations, and Hyperbolic Geometry — Sleator,
Tarjan, Thurston, TR'86
Distance Oracles, Labels, Compact Routing and Oblivious
Routing
Here is my
summary of lower and
upperbounds in the routing literature.
 Online routing in alloptical networks
— Bartal, Leonardi, TCS'99
 Universal
augmentation schemes for network navigability: Overcoming the
\sqrt{n}barrier — Fraigniaud, Gavoille, Kosowski,
Lebhar, Lotker, SPAA'07
 An EnergyDriven Approach to Linkage Unfolding
— Cantarella, Iben, Demaine, O'Brien, SCG'04 (6/10/07)
 Brief announcement: Nameindependent compact routing
in trees — Laing, PODC'04
 Brief announcement: A space lower bound for
nameindependent compact routing in trees — Laing,
Rajaraman, SPAA'05
 On spacestretch
tradeoffs: lower bounds — Abraham, Gavoille, Malkhi,
SPAA'06 Notes (3/28/07)
 Compact nameindependent routing with minimum
stretch — Abraham, Gavoille, Malkhi, Nisan, Thorup,
SPAA'04, Notes
(3/25/07)
 Compact Routing Schemes — Thorup, Zwick,
SPAA'01, Notes
(2/23/07)
 Brief Announcement: Compact Routing with Additive
Stretch Using Distance Labelings — Brady, Cowen, SPAA'06
Notes (3/28/07)
 Approximate Distance
Oracles — Thorup, Zwick, STOC'01 Talk Notes (3/17/07)
 The Moore bound for irregular
graphs — Alon, Hoory, Linial, G&CJ'02 Notes (3/17/07)
 Monotone Maps, Sphericity and Bounded Second
Eigenvalue — Linial, Bilu, JCT'05
 Geographic Routing Using Hyperbolic Space
— Kleinberg, INFOCOM'07
 On a Conjecture Related to Geometric Routing
— (Journal version), Papadimitriou, Ratajczak,
TCC'05
Metric Embeddings
 Approximating a Finite Metric
by a Small Number of Tree Metrics — Charikar, Chekuri, Goel, Guha, Plotkin,
FOCS'98
 Dimension reduction
in the L1 norm — Charikar, Sahai, FOCS'02
 A tight bound on
approximating arbitrary metrics by tree metrics
— Fakcharoenphol, Rao, Talwar, STOC

A tight upper bound on the probabilistic embedding of
seriesparallel graphs — Emek, Peleg
 Improved Embeddings of Graph Metrics into Random
Trees — Dhamdere, Gupta, Raecke, SODA'06 Notes (12/6/06)
 Embedding Tree Metrics into Low Dimensional
Euclidean Spaces — Gupta, STOC'99
 Probabilistic Approximations of Metric Spaces and
its Algorithmic Applications — Bartal, FOCS'96
 On the Euclidean Distortion of Complete Binary
Trees — Linial, Saks, NOTE'01
Optimization
Algorithms
Coding
Arithmetic and analytic combinatorics
Systems
Return to Petar Maymounkov's
homepage.