ToC Library Graduate Surveys 9 (2020) 100 pages A Survey on Distribution Testing: Your Data is Big. But is it Blue? by Clément L. Canonne

ToC Library Graduate Surveys 5 (2013) 60 pages Fast Matrix Multiplication by Markus Bläser

Vol 20, Article 6 (pp 1-23) On a Generalization of Iterated and Randomized Rounding by Nikhil Bansal

Vol 19, Article 8 (pp 1-71) [APRX-RND20 Spec Issue] Pinning Down the Strong Wilber-1 Bound for Binary Search Trees by Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak

Vol 19, Article 2 (pp 1-23) On Solving Reachability in Grid Digraphs using a Pseudoseparator by Rahul Jain and Raghunath Tewari

Vol 19, Article 1 (pp 1-48) Sublinear-Time Computation in the Presence of Online Erasures by Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma

Vol 18, Article 23 (pp 1-24) Pure Entropic Regularization for Metrical Task Systems by Christian Coester and James R. Lee

Vol 18, Article 20 (pp 1-32) Universal Streaming of Subset Norms by Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang

Vol 18, Article 18 (pp 1-19) Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks by Chandra Chekuri and Tanmay Inamdar

Vol 18, Article 9 (pp 1-18) [APRX-RND19 Spec Issue] Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions by Zongchen Chen and Santosh S. Vempala

Vol 18, Article 7 (pp 1-24) [APRX-RND19 Spec Issue] Fast and Deterministic Approximations for $k$-Cut by Kent Quanrud

Vol 18, Article 6 (pp 1-33) [APRX-RND19 Spec Issue] Max-Min Greedy Matching by Alon Eden, Uriel Feige, and Michal Feldman

Vol 17, Article 5 (pp 1-27) New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi

Vol 16, Article 15 (pp 1-25) [APRX-RND16 Spec Issue] Online Row Sampling by Michael B. Cohen, Cameron Musco, and Jakub Pachocki

Vol 16, Article 12 (pp 1-18) Optimality of Correlated Sampling Strategies by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan

Vol 16, Article 3 (pp 1-36) Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri

Vol 15, Article 21 (pp 1-27) The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues by Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett

Vol 15, Article 15 (pp 1-58) [APRX-RND16 Spec Issue] Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem by Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov

Vol 15, Article 7 (pp 1-36) Randomized Polynomial-Time Identity Testing for Noncommutative Circuits by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja

Vol 15, Article 4 (pp 1-32) [RESEARCH SURVEY] Potential-Function Proofs for Gradient Methods by Nikhil Bansal and Anupam Gupta

Vol 14, Article 15 (pp 1-24) Quantum-Walk Speedup of Backtracking Algorithms by Ashley Montanaro

Vol 14, Article 14 (pp 1-29) Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits by Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson

Vol 14, Article 10 (pp 1-33) [CCC17 Spec Issue] From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems by Mrinalkanti Ghosh and Madhur Tulsiani

Vol 14, Article 3 (pp 1-21) [CCC17 Spec Issue] A Deterministic PTAS for the Commutative Rank of Matrix Spaces by Markus Bläser, Gorav Jindal, and Anurag Pandey

Vol 14, Article 1 (pp 1-27) Linear-Time Algorithm for Quantum 2SAT by Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang

Vol 13, Article 21 (pp 1-38) [CCC16 Spec Issue] Decoding Reed–Muller Codes over Product Sets by John Y. Kim and Swastik Kopparty

Vol 13, Article 20 (pp 1-25) The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems by F. Bruce Shepherd and Adrian R. Vetta

Vol 13, Article 19 (pp 1-51) [APRX-RND15 Spec Issue] Improved NP-Inapproximability for $2$-Variable Linear Equations by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright

Vol 13, Article 17 (pp 1-41) A Constructive Lovász Local Lemma for Permutations by David G. Harris and Aravind Srinivasan

Vol 13, Article 14 (pp 1-17) [APRX-RND15 Spec Issue] A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words by David Felber and Rafail Ostrovsky

Vol 13, Article 8 (pp 1-22) [APRX-RND15 Spec Issue] The Minimum Bisection in the Planted Bisection Model by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch

Vol 13, Article 5 (pp 1-47) [APRX-RND13 Spec Issue] A Pseudo-Approximation for the Genus of Hamiltonian Graphs by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos

Vol 13, Article 2 (pp 1-21) [CCC16 Spec Issue] Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs by Rohit Gurjar, Arpita Korwar, and Nitin Saxena

Vol 12, Article 18 (pp 1-35) Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester by Cedric Yen-Yu Lin and Han-Hsuan Lin

Vol 12, Article 17 (pp 1-25) [APRX-RND14 Spec Issue] Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion by Anand Louis and Yury Makarychev

Vol 12, Article 15 (pp 1-29) [APRX-RND14 Spec Issue] Lowest-Degree $k$-Spanner: Approximation and Hardness by Eden Chlamtáč and Michael Dinitz

Vol 12, Article 14 (pp 1-14) [APRX-RND15 Spec Issue] Minimizing Maximum Flow-Time on Related Machines by Nikhil Bansal and Bouke Cloostermans

Vol 12, Article 7 (pp 1-27) Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields by Swastik Kopparty, Mrinal Kumar, and Michael Saks

Vol 12, Article 6 (pp 1-11) [NOTE] Simple Proof of Hardness of Feedback Vertex Set by Venkatesan Guruswami and Euiwoong Lee

Vol 12, Article 2 (pp 1-34) Lattice Sparsification and the Approximate Closest Vector Problem by Daniel Dadush and Gábor Kun

Vol 11, Article 16 (pp 403-412) [NOTE] Quantum Algorithm for Monotonicity Testing on the Hypercube by Aleksandrs Belovs and Eric Blais

Vol 11, Article 15 (pp 395-401) [NOTE] Groups with Identical $k$-Profiles by George Glauberman and Łukasz Grabowski

Vol 11, Article 13 (pp 339-355) Computing the Partition Function for Cliques in a Graph by Alexander Barvinok

Vol 11, Article 7 (pp 221-235) [APRX-RND12 Spec Issue] The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover by Dana Moshkovitz

Vol 11, Article 4 (pp 105-147) Maximizing the Spread of Influence through a Social Network by David Kempe, Jon Kleinberg, and Éva Tardos

Vol 11, Article 1 (pp 1-34) The Complexity of Deciding Statistical Properties of Samplable Distributions by Thomas Watson

Vol 10, Article 18 (pp 465-514) On Reconstruction and Testing of Read-Once Formulas by Amir Shpilka and Ilya Volkovich

Vol 10, Article 16 (pp 421-451) How Many Bits Can a Flock of Birds Compute? by Bernard Chazelle

Vol 10, Article 13 (pp 341-358) [APRX-RND12 Spec Issue] Approximation Algorithm for Non-Boolean Max-$k$-CSP by Konstantin Makarychev and Yury Makarychev

Vol 10, Article 12 (pp 297-339) Width-Parametrized SAT: Time--Space Tradeoffs by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang

Vol 10, Article 11 (pp 257-295) Efficient Rounding for the Noncommutative Grothendieck Inequality by Assaf Naor, Oded Regev, and Thomas Vidick

Vol 10, Article 10 (pp 237-256) Lower Bounds for the Average and Smoothed Number of Pareto-Optima by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin

Vol 9, Article 30 (pp 897-945) Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream by Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan

Vol 9, Article 19 (pp 617-651) Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems by Uriel Feige, Elchanan Mossel, and Dan Vilenchik

Vol 8, Article 26 (pp 597-622) A Constant-Factor Approximation Algorithm for Co-clustering by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar

Vol 8, Article 25 (pp 567-595) [Motwani Special Issue] Online Graph Edge-Coloring in the Random-Order Arrival Model by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani

Vol 8, Article 24 (pp 533-565) Solving Packing Integer Programs via Randomized Rounding with Alterations by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan

Vol 8, Article 20 (pp 429-460) [Motwani Special Issue] Budget-Constrained Auctions with Heterogeneous Items by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala

Vol 8, Article 19 (pp 415-428) Distance Transforms of Sampled Functions by Pedro F. Felzenszwalb and Daniel P. Huttenlocher

Vol 8, Article 18 (pp 401-413) [Motwani Special Issue] An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design by Julia Chuzhoy and Sanjeev Khanna

Vol 8, Article 15 (pp 351-368) [Motwani Special Issue] One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk by Ashish Goel and Ian Post

Vol 8, Article 14 (pp 321-350) [Motwani Special Issue] Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality by Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani

Vol 8, Article 9 (pp 209-229) [Motwani Special Issue] Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule by Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs

Vol 8, Article 7 (pp 165-195) [Motwani Special Issue] Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor by Chandra Chekuri, Sungjin Im, and Benjamin Moseley

Vol 8, Article 6 (pp 121-164) [RESEARCH SURVEY] The Multiplicative Weights Update Method: a Meta-Algorithm and Applications by Sanjeev Arora, Elad Hazan, and Satyen Kale

Vol 8, Article 4 (pp 69-94) [Motwani Special Issue] Regularity Lemmas and Combinatorial Algorithms by Nikhil Bansal and R. Ryan Williams

Vol 7, Article 5 (pp 49-74) Metric Clustering via Consistent Labeling by Robert Krauthgamer and Tim Roughgarden

Vol 7, Article 2 (pp 19-25) [NOTE] Inverting a Permutation is as Hard as Unordered Search by Ashwin Nayak

Vol 6, Article 11 (pp 247-290) The Submodular Welfare Problem with Demand Queries by Uriel Feige and Jan Vondrák

Vol 6, Article 8 (pp 179-199) Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games by Avrim Blum, Eyal Even-Dar, and Katrina Ligett

Vol 6, Article 2 (pp 27-46) Reordering Buffers for General Metric Spaces by Matthias Englert, Harald Räcke, and Matthias Westermann

Vol 5, Article 9 (pp 173-189) All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time by Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster

Vol 5, Article 4 (pp 83-117) SDP Gaps and UGC-hardness for Max-Cut-Gain by Subhash Khot and Ryan O'Donnell

Vol 4, Article 9 (pp 191-193) [COMMENT] On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem by Viswanath Nagarajan

Vol 4, Article 5 (pp 111-128) Approximation Algorithms for Unique Games by Luca Trevisan

Vol 4, Article 2 (pp 21-51) Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem by Miklós Ajtai

Vol 4, Article 1 (pp 1-20) Single Source Multiroute Flows and Cuts on Uniform Capacity Networks by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall

Vol 3, Article 11 (pp 211-219) The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson

Vol 3, Article 10 (pp 197-209) An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem by Chandra Chekuri and Martin Pál

■

Vol 3, Article 9 (pp 179-195) Approximation Algorithms and Online Mechanisms for Item Pricing by Maria-Florina Balcan and Avrim Blum

Vol 3, Article 8 (pp 159-177) Removing Degeneracy May Require a Large Dimension Increase by Jiří Matoušek and Petr Škovroň

Vol 3, Article 1 (pp 1-23) Censorship Resistant Peer-to-Peer Networks by Amos Fiat and Jared Saia

Vol 2, Article 13 (pp 249-266) Correlation Clustering with a Fixed Number of Clusters by Ioannis Giotis and Venkatesan Guruswami

Vol 2, Article 12 (pp 225-247) Matrix Approximation and Projective Clustering via Volume Sampling by Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang

Vol 2, Article 11 (pp 207-224) Embedding the Ulam metric into ℓ1 by Moses Charikar and Robert Krauthgamer

Vol 2, Article 10 (pp 185-206) Learning Restricted Models of Arithmetic Circuits by Adam Klivans and Amir Shpilka

Vol 2, Article 8 (pp 147-172) On Learning Random DNF Formulas Under the Uniform Distribution by Jeffrey C. Jackson and Rocco A. Servedio

Vol 2, Article 7 (pp 137-146) An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd

Vol 2, Article 4 (pp 65-90) Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi

Vol 2, Article 3 (pp 53-64) An Improved Approximation Ratio for the Covering Steiner Problem by Anupam Gupta and Aravind Srinivasan

Vol 2, Article 2 (pp 19-51) Proving Integrality Gaps without Knowing the Linear Program by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis

Vol 1, Article 6 (pp 105-117) Combining Online Algorithms for Acceptance and Rejection by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour