KS

• The Kadison–Singer Problem in mathematics and engineering — Casazza, Tremain, PNAS'05

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 NP-complete 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
• Hit-and-run 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 Non-Metric 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 3-query locally decodable codes of subexponential length — Yekhanin, STOC'07
• A combinatorial, primal-dual 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

  Polya-Urn processes

  Pointers to Janson on Theory of Branching Processes

• Solving linear systems ..., Spielman, Teng

  Sparsification and graph approximation

Algorithms with distributed stability

• Asynchronous distributed averaging on communication networks — Mehyar, Spanos, Pongsajapan, Low, Murray, TN'07

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
• Database-friendly 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

  Relative-error 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 Johnson-Lindenstrauss 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 non-hermitian matrices — Williamson, AMS'39
• A principal axis transformation for non-hermitian matrices — Eckart, Young, AMS'39

Primal-dual 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 polynomial-time algorithm for linear programming — Karmarkar, COMBINATORICA'84

Multiplicative weight updates

• The multiplicative weights update method: A meta algorithm and applications — Arora, Hazan, Kale
• Game theory, on-line prediction and boosting — Freund, Schapire, COLT '96
• The boosting approach to machine learning: An overview — Schapire, MSRI '03
• A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points — Glicksberg, '52

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 quasi-randomness (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
• Twice-Ramanujan 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 '??

  Bookmark-coloring 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 3-colorable 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 multi-commodity flows

• Oblivious routing in the Lp-norm — 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 max-flow min-cut theorems and their use in designing approximation algorithms — Leighton, Rao, JACM'99
• On Partitioning Graphs via Single-Commodity Flows, Orecchia, Schulman, Vazirani, Vishnoi, STOC'08
• A combinatorial, primal-dual 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, SIAM-JoC'02
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms — Leighton, Rao, JACM'99

Partitioning heuristics

• The graph paritioning archive — Repository of graphs and cutting results by various algorithms
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs — Karypis, Kumar, SIAM'99
• A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts — Lang, Rao, IPCO'04

Convex geometry

• Random Walks on Polytopes and an Affine Interior Point Method for Linear Programming — Kannan, Narayanan, STOC'09
• An Elementary Introduction to Modern Convex Geometry — Ball, MSRI'97
• Ellipsoids of maximal volume in convex bodies — Ball, Geometriae Dedicata'04

Functional and Harmonic Analysis

• Approximating a norm by a polynomial — Barvinok, GAFA'01
• Structure and Randomness in Combinatorics — Tao, FOCS'07 Tutorial
• Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies — Khot, Naor, FOCS'07
• Approximating the Cut-Norm via Grothendieck's Inequality — Alon, Naor, STOC'04
• Computing the matrix p-norm — Bhaskara, Vijayaraghavan, '10
• The power method for p norms — Boyd, '74

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 Scale-Free 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

• Notes on Word Hyperbolic Groups — Alonso, et al., Journal'91

Game theory

• On the Equivalence of Linear Programming Problems and Zero-Sum Games — Adler, 2010
• A symmetrization for finite two-person games — Jurg, Jansen, Potters, Tijs, 1992
• Eisenberg-Gale Markets: Algorithms and Game-Theoretic Properties — V. Vazirani, Jain, STOC'07

Stochastic Optimization

• A Generalization of Janson Inequalities and its Application to Finding Shortest Paths — Subramanian, SODA'99 (5/31/2007)
• An FPTAS for the Most-likely-on-time 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

• The PCP Theorem by Gap Amplification — Dinur, STOC'06 Notes (5/12/2007)
• On Dinur's Proof of the PCP Theorem — Sudan, Radhakrishnan, Bulletin of AMS'06 Notes (5/12/2007)
• A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments — Hirsch, LJ/IGPL'98 Notes (3/11/07)

Dynamic optimality

• A lower bound framework for binary search trees with rotations — Derryberry, Sleator, Wang, CMU-TR'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, CBMS-NSF'83, Link-cut 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 upper-bounds in the routing literature.

• On-line routing in all-optical networks — Bartal, Leonardi, TCS'99
• Universal augmentation schemes for network navigability: Overcoming the \sqrt{n}-barrier — Fraigniaud, Gavoille, Kosowski, Lebhar, Lotker, SPAA'07
• An Energy-Driven Approach to Linkage Unfolding — Cantarella, Iben, Demaine, O'Brien, SCG'04 (6/10/07)
• Brief announcement: Name-independent compact routing in trees — Laing, PODC'04
• Brief announcement: A space lower bound for name-independent compact routing in trees — Laing, Rajaraman, SPAA'05
• On space-stretch trade-offs: lower bounds — Abraham, Gavoille, Malkhi, SPAA'06 Notes (3/28/07)
• Compact name-independent 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 series-parallel 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

• Label Placement by Maximum Independent Set in Rectangles — Agarwal, van Kreveld, Suri, WADS'98 (4/10/07)
• Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming — Goemans, Williamson, STOC'94

Algorithms

• All-pairs shortest paths with real weights in O(n^3 / log n) time — Chan, WADS'05
• Generating Random Factored Numbers, Easily — Kalai, SODA'02

Coding

• LT Codes — Luby, FOCS'02
• Raptor Codes — Shokrollahi, TR'03

Arithmetic and analytic combinatorics

• Some Techniques for Solving Recurrences — Lueker '80

Systems

• MapReduce: Simplified Data Processing on Large Clusters — Dean, Ghemawat, OSDI'04
• Bigtable: A Distributed Storage System for Structured Data — Google, OSDI'06
• Practical Packrat Parsing — Robert Grimm, TR'04
• Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism — Anderson, Bershad, Lazowska, Levy, SOSP'91

Return to Petar Maymounkov's homepage.