| 2013 | Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. | Mark Bun, Justin Thaler |
| 2013 | On Randomized Online Labeling with Polynomially Many Labels. | Jan Bulnek, Michal Kouck, Michael E. Saks |
| 2013 | Finding Short Paths on Polytopes by the Shadow Vertex Algorithm. | Tobias Brunsch, Heiko Rglin |
| 2013 | Exact and Efficient Generation of Geometric Random Variates and Random Graphs. | Karl Bringmann, Tobias Friedrich |
| 2013 | Online Checkpointing with Improved Worst-Case Guarantees. | Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan |
| 2013 | Direct Product via Round-Preserving Compression. | Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff |
| 2013 | How Hard Is Counting Triangles in the Streaming Model? | Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik |
| 2013 | A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions. | Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino |
| 2013 | Nondeterminism in the Presence of a Diverse or Unknown Future. | Udi Boker, Denis Kuperberg, Orna Kupferman, Michal Skrzypczak |
| 2013 | On the Complexity of Higher Order Abstract Voronoi Diagrams. | Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi |
| 2013 | Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. | Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof |
| 2013 | Optimal Orthogonal Graph Drawing with Convex Bend Costs. | Thomas Blsius, Ignaz Rutter, Dorothea Wagner |
| 2013 | Noncommutativity Makes Determinants Hard. | Markus Blser |
| 2013 | Tree Compression with Top Trees. | Philip Bille, Inge Li Grtz, Gad M. Landau, Oren Weimann |
| 2013 | Sparse Suffix Tree Construction in Small Space. | Philip Bille, Johannes Fischer, Inge Li Grtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhj |
| 2013 | Approximation Algorithms for the Joint Replenishment Problem with Deadlines. | Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young |
| 2013 | An Algebraic Characterization of Testable Boolean CSPs. | Arnab Bhattacharyya, Yuichi Yoshida |
| 2013 | Complexity of Two-Variable Logic on Finite Trees. | Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieronski, Rastislav Lenhardt, Filip Mazowiecki, James Worrell |
| 2013 | Time-Efficient Quantum Walks for 3-Distinctness. | Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frdric Magniez |
| 2013 | Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds. | Luca Becchetti, Vincenzo Bonifaci, Michael Dirnberger, Andreas Karrenbauer, Kurt Mehlhorn |
| 2013 | Search-Space Size in Contraction Hierarchies. | Reinhard Bauer, Tobias Columbus, Ignaz Rutter, Dorothea Wagner |
| 2013 | Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems. | MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Vahid Liaghat |
| 2013 | A Maximal Entropy Stochastic Process for a Timed Automaton, . | Nicolas Basset |
| 2013 | Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs. | Gilles Barthe, Federico Olmedo |
| 2013 | Sketching for Big Data Recommender Systems Using Fast Pseudo-random Fingerprints. | Yoram Bachrach, Ely Porat |