Articles under category:
Algorithms
Algorithms
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 19, Article 8 (pp 171)
[APRXRND20 Spec Issue]
Pinning Down the Strong Wilber1 Bound for Binary Search Trees by Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak 
Vol 19, Article 2 (pp 123)
On Solving Reachability in Grid Digraphs using a Pseudoseparator by Rahul Jain and Raghunath Tewari 
Vol 19, Article 1 (pp 148)
SublinearTime Computation in the Presence of Online Erasures by Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma 
Vol 18, Article 23 (pp 124)
Pure Entropic Regularization for Metrical Task Systems by Christian Coester and James R. Lee 
Vol 18, Article 20 (pp 132)
Universal Streaming of Subset Norms by Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang 
Vol 18, Article 18 (pp 119)
Algorithms for Intersection Graphs for $t$Intervals and $t$Pseudodisks by Chandra Chekuri and Tanmay Inamdar 
Vol 18, Article 9 (pp 118)
[APRXRND19 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 124)
[APRXRND19 Spec Issue]
Fast and Deterministic Approximations for $k$Cut by Kent Quanrud 
Vol 18, Article 6 (pp 133)
[APRXRND19 Spec Issue]
MaxMin Greedy Matching by Alon Eden, Uriel Feige, and Michal Feldman 
Vol 17, Article 5 (pp 127)
New Algorithms and Lower Bounds for AllPairs MaxFlow in Undirected Graphs by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi 
Vol 16, Article 15 (pp 125)
[APRXRND16 Spec Issue]
Online Row Sampling by Michael B. Cohen, Cameron Musco, and Jakub Pachocki 
Vol 16, Article 12 (pp 118)
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 136)
Optimal Unateness Testers for RealValued Functions: Adaptivity Helps by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri 
Vol 15, Article 21 (pp 127)
The GramSchmidt Walk: A Cure for the Banaszczyk Blues by Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett 
Vol 15, Article 15 (pp 158)
[APRXRND16 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 136)
Randomized PolynomialTime Identity Testing for Noncommutative Circuits by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja 
Vol 15, Article 4 (pp 132)
[RESEARCH SURVEY]
PotentialFunction Proofs for Gradient Methods by Nikhil Bansal and Anupam Gupta 
Vol 14, Article 15 (pp 124)
QuantumWalk Speedup of Backtracking Algorithms by Ashley Montanaro 
Vol 14, Article 14 (pp 129)
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 133)
[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 121)
[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 127)
LinearTime Algorithm for Quantum 2SAT by Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang 
Vol 13, Article 21 (pp 138)
[CCC16 Spec Issue]
Decoding Reed–Muller Codes over Product Sets by John Y. Kim and Swastik Kopparty 
Vol 13, Article 20 (pp 125)
The Inapproximability of Maximum SingleSink Unsplittable, Priority and Confluent Flow Problems by F. Bruce Shepherd and Adrian R. Vetta 
Vol 13, Article 19 (pp 151)
[APRXRND15 Spec Issue]
Improved NPInapproximability for $2$Variable Linear Equations by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright 
Vol 13, Article 17 (pp 141)
A Constructive Lovász Local Lemma for Permutations by David G. Harris and Aravind Srinivasan 
Vol 13, Article 14 (pp 117)
[APRXRND15 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 122)
[APRXRND15 Spec Issue]
The Minimum Bisection in the Planted Bisection Model by Amin CojaOghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch 
Vol 13, Article 5 (pp 147)
[APRXRND13 Spec Issue]
A PseudoApproximation for the Genus of Hamiltonian Graphs by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos 
Vol 13, Article 2 (pp 121)
[CCC16 Spec Issue]
Identity Testing for ConstantWidth, and AnyOrder, ReadOnce Oblivious Arithmetic Branching Programs by Rohit Gurjar, Arpita Korwar, and Nitin Saxena 
Vol 12, Article 18 (pp 135)
Upper Bounds on Quantum Query Complexity Inspired by the ElitzurVaidman Bomb Tester by Cedric YenYu Lin and HanHsuan Lin 
Vol 12, Article 17 (pp 125)
[APRXRND14 Spec Issue]
Approximation Algorithms for Hypergraph SmallSet Expansion and SmallSet Vertex Expansion by Anand Louis and Yury Makarychev 
Vol 12, Article 15 (pp 129)
[APRXRND14 Spec Issue]
LowestDegree $k$Spanner: Approximation and Hardness by Eden Chlamtáč and Michael Dinitz 
Vol 12, Article 14 (pp 114)
[APRXRND15 Spec Issue]
Minimizing Maximum FlowTime on Related Machines by Nikhil Bansal and Bouke Cloostermans 
Vol 12, Article 7 (pp 127)
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields by Swastik Kopparty, Mrinal Kumar, and Michael Saks 
Vol 12, Article 6 (pp 111)
[NOTE]
Simple Proof of Hardness of Feedback Vertex Set by Venkatesan Guruswami and Euiwoong Lee 
Vol 12, Article 2 (pp 134)
Lattice Sparsification and the Approximate Closest Vector Problem by Daniel Dadush and Gábor Kun 
Vol 11, Article 16 (pp 403412)
[NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube by Aleksandrs Belovs and Eric Blais 
Vol 11, Article 15 (pp 395401)
[NOTE]
Groups with Identical $k$Profiles by George Glauberman and Łukasz Grabowski 
Vol 11, Article 13 (pp 339355)
Computing the Partition Function for Cliques in a Graph by Alexander Barvinok 
Vol 11, Article 7 (pp 221235)
[APRXRND12 Spec Issue]
The Projection Games Conjecture and the NPHardness of ln $n$Approximating SetCover by Dana Moshkovitz 
Vol 11, Article 4 (pp 105147)
Maximizing the Spread of Influence through a Social Network by David Kempe, Jon Kleinberg, and Éva Tardos 
Vol 11, Article 1 (pp 134)
The Complexity of Deciding Statistical Properties of Samplable Distributions by Thomas Watson 
Vol 10, Article 18 (pp 465514)
On Reconstruction and Testing of ReadOnce Formulas by Amir Shpilka and Ilya Volkovich 
Vol 10, Article 16 (pp 421451)
How Many Bits Can a Flock of Birds Compute? by Bernard Chazelle 
Vol 10, Article 13 (pp 341358)
[APRXRND12 Spec Issue]
Approximation Algorithm for NonBoolean Max$k$CSP by Konstantin Makarychev and Yury Makarychev 
Vol 10, Article 12 (pp 297339)
WidthParametrized SAT: TimeSpace Tradeoffs by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang 
Vol 10, Article 11 (pp 257295)
Efficient Rounding for the Noncommutative Grothendieck Inequality by Assaf Naor, Oded Regev, and Thomas Vidick 
Vol 10, Article 10 (pp 237256)
Lower Bounds for the Average and Smoothed Number of ParetoOptima by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin 
Vol 9, Article 30 (pp 897945)
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream by KaiMin Chung, Michael Mitzenmacher, and Salil Vadhan 
Vol 9, Article 19 (pp 617651)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems by Uriel Feige, Elchanan Mossel, and Dan Vilenchik 
Vol 8, Article 26 (pp 597622)
A ConstantFactor Approximation Algorithm for Coclustering by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar 
Vol 8, Article 25 (pp 567595)
[Motwani Special Issue]
Online Graph EdgeColoring in the RandomOrder Arrival Model by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani 
Vol 8, Article 24 (pp 533565)
Solving Packing Integer Programs via Randomized Rounding with Alterations by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan 
Vol 8, Article 20 (pp 429460)
[Motwani Special Issue]
BudgetConstrained Auctions with Heterogeneous Items by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala 
Vol 8, Article 19 (pp 415428)
Distance Transforms of Sampled Functions by Pedro F. Felzenszwalb and Daniel P. Huttenlocher 
Vol 8, Article 18 (pp 401413)
[Motwani Special Issue]
An $O(k^3\log n)$Approximation Algorithm for VertexConnectivity Survivable Network Design by Julia Chuzhoy and Sanjeev Khanna 
Vol 8, Article 15 (pp 351368)
[Motwani Special Issue]
One Tree Suffices: A Simultaneous $O(1)$Approximation for SingleSink BuyatBulk by Ashish Goel and Ian Post 
Vol 8, Article 14 (pp 321350)
[Motwani Special Issue]
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality by Sariel HarPeled, Piotr Indyk, and Rajeev Motwani 
Vol 8, Article 9 (pp 209229)
[Motwani Special Issue]
Improved Bounds for Speed Scaling in Devices Obeying the CubeRoot Rule by Nikhil Bansal, HoLeung Chan, Dmitriy Katz, and Kirk Pruhs 
Vol 8, Article 7 (pp 165195)
[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 121164)
[RESEARCH SURVEY]
The Multiplicative Weights Update Method: a MetaAlgorithm and Applications by Sanjeev Arora, Elad Hazan, and Satyen Kale 
Vol 8, Article 4 (pp 6994)
[Motwani Special Issue]
Regularity Lemmas and Combinatorial Algorithms by Nikhil Bansal and R. Ryan Williams 
Vol 7, Article 5 (pp 4974)
Metric Clustering via Consistent Labeling by Robert Krauthgamer and Tim Roughgarden 
Vol 7, Article 2 (pp 1925)
[NOTE]
Inverting a Permutation is as Hard as Unordered Search by Ashwin Nayak 
Vol 6, Article 11 (pp 247290)
The Submodular Welfare Problem with Demand Queries by Uriel Feige and Jan Vondrák 
Vol 6, Article 8 (pp 179199)
Routing Without Regret: On Convergence to Nash Equilibria of RegretMinimizing Algorithms in Routing Games by Avrim Blum, Eyal EvenDar, and Katrina Ligett 
Vol 6, Article 2 (pp 2746)
Reordering Buffers for General Metric Spaces by Matthias Englert, Harald Räcke, and Matthias Westermann 
Vol 5, Article 9 (pp 173189)
All Pairs Bottleneck Paths and MaxMin Matrix Products in Truly Subcubic Time by Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster 
Vol 5, Article 4 (pp 83117)
SDP Gaps and UGChardness for MaxCutGain by Subhash Khot and Ryan O'Donnell 
Vol 4, Article 9 (pp 191193)
[COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem by Viswanath Nagarajan 
Vol 4, Article 5 (pp 111128)
Approximation Algorithms for Unique Games by Luca Trevisan 
Vol 4, Article 2 (pp 2151)
Optimal lower bounds for the KorkineZolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem by Miklós Ajtai 
Vol 4, Article 1 (pp 120)
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 211219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson 
Vol 3, Article 10 (pp 197209)
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 179195)
Approximation Algorithms and Online Mechanisms for Item Pricing by MariaFlorina Balcan and Avrim Blum 
Vol 3, Article 8 (pp 159177)
Removing Degeneracy May Require a Large Dimension Increase by Jiří Matoušek and Petr Škovroň 
Vol 3, Article 1 (pp 123)
Censorship Resistant PeertoPeer Networks by Amos Fiat and Jared Saia 
Vol 2, Article 13 (pp 249266)
Correlation Clustering with a Fixed Number of Clusters by Ioannis Giotis and Venkatesan Guruswami 
Vol 2, Article 12 (pp 225247)
Matrix Approximation and Projective Clustering via Volume Sampling by Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang 
Vol 2, Article 11 (pp 207224)
Embedding the Ulam metric into ℓ_{1} by Moses Charikar and Robert Krauthgamer 
Vol 2, Article 10 (pp 185206)
Learning Restricted Models of Arithmetic Circuits by Adam Klivans and Amir Shpilka 
Vol 2, Article 8 (pp 147172)
On Learning Random DNF Formulas Under the Uniform Distribution by Jeffrey C. Jackson and Rocco A. Servedio 
Vol 2, Article 7 (pp 137146)
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 6590)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua BureshOppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi 
Vol 2, Article 3 (pp 5364)
An Improved Approximation Ratio for the Covering Steiner Problem by Anupam Gupta and Aravind Srinivasan 
Vol 2, Article 2 (pp 1951)
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 105117)
Combining Online Algorithms for Acceptance and Rejection by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour 