Articles under category:
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 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