| 2013 | (1+ Є)-approximation for facility location in data streams. Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, Christian Sohler |
| 2013 | 4-connected projective-planar graphs are hamiltonian-connected. Ken-ichi Kawarabayashi, Kenta Ozeki |
| 2013 | 5-coloring K Ken-ichi Kawarabayashi |
| 2013 | A Adrian Kosowski |
| 2013 | A Constant Factor Approximation Algorithm for Reordering Buffer Management. Noa Avigdor-Elgrabli, Yuval Rabani |
| 2013 | A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio. Elisabeth Günther, Olaf Maurer, Nicole Megow, Andreas Wiese |
| 2013 | A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory. Martin Grohe, Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2013 | A unified approach to truthful scheduling on related machines. Leah Epstein, Asaf Levin, Rob van Stee |
| 2013 | Active Self-Assembly of Simple Units Using an Insertion Primitive. Nadine Dabby, Ho-Lin Chen |
| 2013 | Adaptive and Approximate Orthogonal Range Counting. Timothy M. Chan, Bryan T. Wilkinson |
| 2013 | Algorithms for the Densest Sub-Lattice Problem. Daniel Dadush, Daniele Micciancio |
| 2013 | An Almost Optimal Algorithm for Computing Nonnegative Rank. Ankur Moitra |
| 2013 | An Infinite Class of Sparse-Yao Spanners. Matthew Bauer, Mirela Damian |
| 2013 | Anonymous Meeting in Networks. Yoann Dieudonné, Andrzej Pelc |
| 2013 | Approximability and proof complexity. Ryan O'Donnell, Yuan Zhou |
| 2013 | Approximate Counting via Correlation Decay on Planar Graphs. Yitong Yin, Chihao Zhang |
| 2013 | Approximate Distance Oracles with Improved Query Time. Christian Wulff-Nilsen |
| 2013 | Approximate Maximum Flow on Separable Undirected Graphs. Gary L. Miller, Richard Peng |
| 2013 | Approximate Shortest Descending Paths. Siu-Wing Cheng, Jiongxin Jin |
| 2013 | Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. Venkatesan Guruswami, Ali Kemal Sinop |
| 2013 | Approximating Watchman Routes. Joseph S. B. Mitchell |
| 2013 | Balls into Bins via Local Search. Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, He Sun |
| 2013 | Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev |
| 2013 | Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection. Per Austrin, Siavosh Benabbas, Konstantinos Georgiou |
| 2013 | Better bounds for matchings in the streaming model. Michael Kapralov |
| 2013 | Breaking the O(n Ran Duan |
| 2013 | Breaking the n David J. Rosenbaum |
| 2013 | Clinching Auction with Online Supply. Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme |
| 2013 | Clustering Affine Subspaces: Hardness and Algorithms. Euiwoong Lee, Leonard J. Schulman |
| 2013 | Combinatorial and Geometric Properties of Planar Laman Graphs. Stephen G. Kobourov, Torsten Ueckerdt, Kevin Verbeek |
| 2013 | Communication Complexity of Combinatorial Auctions with Submodular Valuations. Shahar Dobzinski, Jan Vondrák |
| 2013 | Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis. Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini |
| 2013 | Compressed static functions with applications. Djamal Belazzougui, Rossano Venturini |
| 2013 | Computing the Discrete Fréchet Distance in Subquadratic Time. Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, Micha Sharir |
| 2013 | Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing. Mathieu Leconte, Marc Lelarge, Laurent Massoulié |
| 2013 | Correlation Decay up to Uniqueness in Spin Systems. Liang Li, Pinyan Lu, Yitong Yin |
| 2013 | Decremental maintenance of strongly connected components. Liam Roditty |
| 2013 | Dichotomy for Holant* Problems with Domain Size 3. Jin-Yi Cai, Pinyan Lu, Mingji Xia |
| 2013 | Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems. Hiroshi Hirai |
| 2013 | Distance Oracles for Stretch Less Than 2. Rachit Agarwal, Philip Brighten Godfrey |
| 2013 | Dynamic graph connectivity in polylogarithmic worst case time. Bruce M. Kapron, Valerie King, Ben Mountjoy |
| 2013 | Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree. Gerth Stølting Brodal, Rolf Fagerberg, Thomas Mailund, Christian N. S. Pedersen, Andreas Sand |
| 2013 | Efficient protocols of generating bipartite classical distributions and quantum states. Rahul Jain, Yaoyun Shi, Zhaohui Wei, Shengyu Zhang |
| 2013 | Eigenvalues of a matrix in the streaming model. Alexandr Andoni, Huy L. Nguyen |
| 2013 | Energy Efficient Scheduling of Parallelizable Jobs. Kyle Fox, Sungjin Im, Benjamin Moseley |
| 2013 | Euclidean spanners in high dimensions. Sariel Har-Peled, Piotr Indyk, Anastasios Sidiropoulos |
| 2013 | Exponential Lower Bounds for the PPSZ Dominik Scheder, Bangsheng Tang, Shiteng Chen, Navid Talebanfard |
| 2013 | Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. Dana Ron, Rocco A. Servedio |
| 2013 | Fast Algorithms for Interactive Coding. Zvika Brakerski, Moni Naor |
| 2013 | Fast Constructions of Light-Weight Spanners for General Graphs. Michael Elkin, Shay Solomon |
| 2013 | Fast matrix multiplication using coherent configurations. Henry Cohn, Christopher Umans |
| 2013 | Faster Deterministic Fully-Dynamic Graph Connectivity. Christian Wulff-Nilsen |
| 2013 | Finding Endogenously Formed Communities. Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, Shang-Hua Teng |
| 2013 | Frozen variables in random boolean constraint satisfaction problems. Michael Molloy, Ricardo Restrepo |
| 2013 | Fuel Efficient Computation in Passive Self-Assembly. Robert Schweller, Michael Sherman |
| 2013 | Generalized Perron-Frobenius Theorem for Multiple Choice Matrices, and Applications. Chen Avin, Michael Borokhovich, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
| 2013 | Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More. Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai |
| 2013 | Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes. Chih-Hung Liu, D. T. Lee |
| 2013 | How to Sell Hyperedges: The Hypermatching Assignment Problem. Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli |
| 2013 | Improved Algorithms for Constructing Consensus Trees. Jesper Jansson, Chuanqi Shen, Wing-Kin Sung |
| 2013 | Improved quantum query algorithms for triangle finding and associativity testing. Troy Lee, Frédéric Magniez, Miklos Santha |
| 2013 | Ironing in Dynamic Revenue Management: Posted Prices & Biased Auctions. Rahul Deb, Mallesh M. Pai |
| 2013 | Jungles, bundles, and fixed parameter tractability. Fedor V. Fomin, Michal Pilipczuk |
| 2013 | Known algorithms for EDGE CLIQUE COVER are probably optimal. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk |
| 2013 | Lattice Sparsification and the Approximate Closest Vector Problem. Daniel Dadush, Gábor Kun |
| 2013 | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's". Erik D. Demaine, Morteza Zadimoghaddam |
| 2013 | Learning mixtures of structured distributions over discrete domains. Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun |
| 2013 | Learning pseudo-Boolean Sofya Raskhodnikova, Grigory Yaroslavtsev |
| 2013 | List-coloring embedded graphs. Zdenek Dvorák, Ken-ichi Kawarabayashi |
| 2013 | Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. Alina Ene, Jan Vondrák, Yi Wu |
| 2013 | Local-Search based Approximation Algorithms for Mobile Facility Location Problems. Sara Ahmadian, Zachary Friggstad, Chaitanya Swamy |
| 2013 | Low-distortion Inference of Latent Similarities from a Multiplex Social Network. Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins |
| 2013 | Lower Bounds for Adaptive Sparse Recovery. Eric Price, David P. Woodruff |
| 2013 | Lyndon Words and Short Superstrings. Marcin Mucha |
| 2013 | Matroid Secretary for Regular and Decomposable Matroids. Michael Dinitz, Guy Kortsarz |
| 2013 | Mimicking Networks and Succinct Representations of Terminal Cuts. Robert Krauthgamer, Inbal Rika |
| 2013 | Minimizing the number of lattice points in a translated polygon. Friedrich Eisenbrand, Nicolai Hähnle |
| 2013 | Minimum Makespan Scheduling with Low Rank Processing Times. Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, Udi Wieder |
| 2013 | Mixing Times of Markov Chains for Self-Organizing Lists and Biased Permutations. Prateek Bhakta, Sarah Miracle, Dana Randall, Amanda Pascoe Streib |
| 2013 | More Compact Oracles for Approximate Distances in Undirected Planar Graphs. Ken-ichi Kawarabayashi, Christian Sommer, Mikkel Thorup |
| 2013 | Morphing Planar Graph Drawings with a Polynomial Number of Steps. Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson |
| 2013 | Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs. Freek van Walderveen, Norbert Zeh, Lars Arge |
| 2013 | Near Optimal Leader Election in Multi-Hop Radio Networks. Mohsen Ghaffari, Bernhard Haeupler |
| 2013 | Near-Optimal Range Reporting Structures for Categorical Data. Kasper Green Larsen, Freek van Walderveen |
| 2013 | Nested Quantum Walks with Quantum Data Structures. Stacey Jeffery, Robin Kothari, Frédéric Magniez |
| 2013 | New Additive Spanners. Shiri Chechik |
| 2013 | New Approximability Results for Two-Dimensional Bin Packing. Klaus Jansen, Lars Prädel |
| 2013 | On differentially private low rank approximation. Michael Kapralov, Kunal Talwar |
| 2013 | On the Complexity of Information Spreading in Dynamic Networks. Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola |
| 2013 | On the number of matroids. Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol |
| 2013 | Online Mixed Packing and Covering. Yossi Azar, Umang Bhaskar, Lisa Fleischer, Debmalya Panigrahi |
| 2013 | Online Submodular Welfare Maximization: Greedy is Optimal. Michael Kapralov, Ian Post, Jan Vondrák |
| 2013 | Optimal Dynamic Sequence Representations. Gonzalo Navarro, Yakov Nekrich |
| 2013 | Optimal Listing of Cycles and st-Paths in Undirected Graphs. Etienne Birmelé, Rui A. Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, Gustavo Sacomoto |
| 2013 | Optimal and Efficient Parametric Auctions. Pablo Daniel Azar, Constantinos Daskalakis, Silvio Micali, S. Matthew Weinberg |
| 2013 | Output-sensitive Skyline Algorithms in External Memory. Xiaocheng Hu, Cheng Sheng, Yufei Tao, Yi Yang, Shuigeng Zhou |
| 2013 | Packing directed cycles through a specified vertex set. Ken-ichi Kawarabayashi, Daniel Král', Marek Krcál, Stephan Kreutzer |
| 2013 | Playing Mastermind with Many Colors. Benjamin Doerr, Reto Spöhel, Henning Thomas, Carola Winzen |
| 2013 | Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion. Chandra Chekuri, Alina Ene |
| 2013 | Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 Sanjeev Khanna |
| 2013 | Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching. Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg |
| 2013 | Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations. Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |
| 2013 | Regret Minimization for Reserve Prices in Second-Price Auctions. Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour |
| 2013 | Reporting neighbors in high-dimensional Euclidean spaces. Dror Aiger, Haim Kaplan, Micha Sharir |
| 2013 | Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker |
| 2013 | Segmentation of Trajectories for Non-Monotone Criteria. Boris Aronov, Anne Driemel, Marc J. van Kreveld, Maarten Löffler, Frank Staals |
| 2013 | Shift Finding in Sub-Linear Time. Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh |
| 2013 | Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs. Kyle Fox |
| 2013 | Simple and Nearly Optimal Multi-Item Auctions. Yang Cai, Zhiyi Huang |
| 2013 | Simple, Fast and Deterministic Gossip and Rumor Spreading. Bernhard Haeupler |
| 2013 | Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. Thomas Bläsius, Ignaz Rutter |
| 2013 | Skew Bisubmodularity and Valued CSPs. Anna Huber, Andrei A. Krokhin, Robert Powell |
| 2013 | Smoothed Analysis of the Successive Shortest Path Algorithm. Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin |
| 2013 | Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. Michael E. Saks, C. Seshadhri |
| 2013 | Testing Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant |
| 2013 | Testing Low Complexity Affine-Invariant Properties. Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett |
| 2013 | The Diffusion of Networking Technologies. Sharon Goldberg, Zhenming Liu |
| 2013 | The Fast Cauchy Transform and Faster Robust Linear Regression. Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff |
| 2013 | The Power of Linear Reconstruction Attacks. Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith |
| 2013 | The Power of Non-Uniform Wireless Power. Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra, Roger Wattenhofer |
| 2013 | The Space Complexity of 2-Dimensional Approximate Range Counting. Zhewei Wei, Ke Yi |
| 2013 | The communication complexity of addition. Emanuele Viola |
| 2013 | The complexity of detecting taut angle structures on triangulations. Benjamin A. Burton, Jonathan Spreer |
| 2013 | The simplex method is strongly polynomial for deterministic Markov decision processes. Ian Post, Yinyu Ye |
| 2013 | The traveling salesman problem for lines, balls and planes. Adrian Dumitrescu, Csaba D. Tóth |
| 2013 | Tight Cell-Probe Bounds for Online Hamming Distance Computation. Raphaël Clifford, Markus Jalsenius, Benjamin Sach |
| 2013 | Totally odd subdivisions and parity subdivisions: Structures and Coloring. Ken-ichi Kawarabayashi |
| 2013 | Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model. Ralph Neininger, Kevin Leckey, Wojciech Szpankowski |
| 2013 | Towards Polynomial Simplex-Like Algorithms for Market Equlibria. Jugal Garg, Ruta Mehta, Milind A. Sohoni, Nisheeth K. Vishnoi |
| 2013 | Transforming Curves on Surfaces Redux. Jeff Erickson, Kim Whittlesey |
| 2013 | Turning big data into tiny data: Constant-size coresets for Dan Feldman, Melanie Schmidt, Christian Sohler |
| 2013 | Twisted Tabulation Hashing. Mihai Patrascu, Mikkel Thorup |
| 2013 | Weighted Flowtime on Capacitated Machines. Kyle Fox, Madhukar Korupolu |
| 2013 | Weighted Graph Laplace Operator under Topological Noise. Tamal K. Dey, Pawas Ranjan, Yusu Wang |
| 2013 | Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges. Michael J. Bannister, Christopher DuBois, David Eppstein, Padhraic Smyth |
| 2013 | Є-Samples for Kernels. Jeff M. Phillips |