| 2015 | (2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. Michael Elkin, Seth Pettie, Hsin-Hao Su |
| 2015 | 2-Edge Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis |
| 2015 | A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]. Sungjin Im, Shi Li, Benjamin Moseley, Eric Torng |
| 2015 | A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State. Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott |
| 2015 | A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. Michael Elkin, Seth Pettie |
| 2015 | A Simple Moran Feldman, Ola Svensson, Rico Zenklusen |
| 2015 | A Stable Marriage Requires Communication. Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum |
| 2015 | A Unified Framework for Clustering Constrained Data without Locality Property. Hu Ding, Jinhui Xu |
| 2015 | A dynamic model of barter exchange. Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria |
| 2015 | A new characterization of maximal repetitions by Lyndon trees. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta |
| 2015 | A note on the ring loading problem. Martin Skutella |
| 2015 | A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. Timothy Naumovitz, Michael E. Saks |
| 2015 | A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem. Anna Adamaszek, Andreas Wiese |
| 2015 | Algorithmic regularity for polynomials and applications. Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani |
| 2015 | An Andrew Chi-Chih Yao |
| 2015 | An Improved Approximation for Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh |
| 2015 | An algorithmic framework for obtaining lower bounds for random Ramsey problems Rajko Nenadov, Nemanja Skoric, Angelika Steger |
| 2015 | An exact characterization of tractable demand patterns for maximum disjoint path problems. Dániel Marx, Paul Wollan |
| 2015 | Approximate Nearest Line Search in High Dimensions. Sepideh Mahabadi |
| 2015 | Approximate Range Emptiness in Constant Time and Optimal Space. Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh |
| 2015 | Approximate resilience, monotonicity, and the complexity of agnostic learning. Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer |
| 2015 | Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy). Sampath Kannan, Jamie Morgenstern, Aaron Roth, Zhiwei Steven Wu |
| 2015 | Approximating Hereditary Discrepancy via Small Width Ellipsoids. Aleksandar Nikolov, Kunal Talwar |
| 2015 | Approximating independent sets in sparse graphs. Nikhil Bansal |
| 2015 | Approximating the best Nash Equilibrium in Mark Braverman, Young Kun-Ko, Omri Weinstein |
| 2015 | Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation. Sayan Bandyapadhyay, Santanu Bhowmick, Kasturi R. Varadarajan |
| 2015 | Bayesian Truthful Constantinos Daskalakis, S. Matthew Weinberg |
| 2015 | Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. Rahul Santhanam, Richard Ryan Williams |
| 2015 | Bi-Factor Approximation Algorithms for Hard Capacitated Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase |
| 2015 | Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. Ran Gelles, Bernhard Haeupler |
| 2015 | Cell-probe bounds for online edit distance and other pattern matching problems. Raphaël Clifford, Markus Jalsenius, Benjamin Sach |
| 2015 | Characterization of cutoff for reversible Markov chains. Riddhipratim Basu, Jonathan Hermon, Yuval Peres |
| 2015 | Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. Bart M. P. Jansen, Dániel Marx |
| 2015 | Combinatorial Algorithm for Restricted Max-Min Fair Allocation. Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson |
| 2015 | Combinatorial Auctions via Posted Prices. Michal Feldman, Nick Gravin, Brendan Lucier |
| 2015 | Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. Niv Buchbinder, Moran Feldman, Roy Schwartz |
| 2015 | Compatible Connectivity-Augmentation of Planar Disconnected Graphs. Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmovic, Fabrizio Frati, Pat Morin |
| 2015 | Connectivity in Random Forests and Credit Networks. Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang |
| 2015 | Contagious Sets in Expanders. Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman |
| 2015 | Decomposing a Graph Into Expanding Subgraphs. Guy Moshkovitz, Asaf Shapira |
| 2015 | Degree-3 Treewidth Sparsifiers. Chandra Chekuri, Julia Chuzhoy |
| 2015 | Density and regularity theorems for semi-algebraic hypergraphs. Jacob Fox, János Pach, Andrew Suk |
| 2015 | Detecting Weakly Simple Polygons. Hsien-Chih Chang, Jeff Erickson, Chao Xu |
| 2015 | Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano |
| 2015 | Distributed Computation of Large-scale Graph Problems. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson |
| 2015 | Dynamic Facility Location via Exponential Clocks. Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson |
| 2015 | Efficient and Robust Persistent Homology for Measures. Mickaël Buchet, Frédéric Chazal, Steve Y. Oudot, Donald R. Sheehy |
| 2015 | FPTAS for Counting Monotone CNF. Jingcheng Liu, Pinyan Lu |
| 2015 | Fast Algorithms for Online Stochastic Convex Programming. Shipra Agrawal, Nikhil R. Devanur |
| 2015 | Fast Generation of Random Spanning Trees and the Effective Resistance Metric. Aleksander Madry, Damian Straszak, Jakub Tarnawski |
| 2015 | Fast Lattice Point Enumeration with Minimal Overhead. Daniele Micciancio, Michael Walter |
| 2015 | Finding Four-Node Subgraphs in Triangle Time. Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, Huacheng Yu |
| 2015 | Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm. Mathew C. Francis, Pavol Hell, Juraj Stacho |
| 2015 | Four terminal planar Delta-Wye reducibility via rooted Lino Demasi, Bojan Mohar |
| 2015 | Front Matter. |
| 2015 | Geometric Sylvester David Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeek, Hakan Yildiz |
| 2015 | Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading. Zeyu Guo, He Sun |
| 2015 | Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ Saladi Rahul |
| 2015 | Improved Bounds for the Flat Wall Theorem. Julia Chuzhoy |
| 2015 | Improved Region-Growing and Combinatorial Algorithms for Guru Guruganesh, Laura Sanità, Chaitanya Swamy |
| 2015 | Internal Pattern Matching Queries in a Text and Applications. Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2015 | LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes. Badih Ghazi, Euiwoong Lee |
| 2015 | Learning Privately with Labeled and Unlabeled Examples. Amos Beimel, Kobbi Nissim, Uri Stemmer |
| 2015 | Learning from satisfying assignments. Anindya De, Ilias Diakonikolas, Rocco A. Servedio |
| 2015 | Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang |
| 2015 | Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract). Ian Post, Chaitanya Swamy |
| 2015 | Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma. David G. Harris |
| 2015 | Minimum Forcing Sets for Miura Folding Patterns. Brad Ballinger, Mirela Damian, David Eppstein, Robin Y. Flatland, Jessica Ginepro, Thomas C. Hull |
| 2015 | Minors and Dimension. Bartosz Walczak |
| 2015 | More Applications of the Polynomial Method to Algorithm Design. Amir Abboud, Richard Ryan Williams, Huacheng Yu |
| 2015 | New Approximation Schemes for Unsplittable Flow on a Path. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese |
| 2015 | New Approximations for Broadcast Scheduling via Variants of α-point Rounding. Sungjin Im, Maxim Sviridenko |
| 2015 | On (1, Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li |
| 2015 | On Survivable Set Connectivity. Parinya Chalermsook, Fabrizio Grandoni, Bundit Laekhanukit |
| 2015 | On Termination of Integer Linear Loops. Joël Ouaknine, João Sousa Pinto, James Worrell |
| 2015 | On Uniform Capacitated Shi Li |
| 2015 | On largest volume simplices and sub-determinants. Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer |
| 2015 | On the Complexity of Computing an Equilibrium in Combinatorial Auctions. Shahar Dobzinski, Hu Fu, Robert D. Kleinberg |
| 2015 | On the Quickest Flow Problem in Dynamic Networks - A Parametric Min-Cost Flow Approach. Maokai Lin, Patrick Jaillet |
| 2015 | On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves. János Pach, Natan Rubin, Gábor Tardos |
| 2015 | Online Network Design Algorithms via Hierarchical Decompositions. Seeun Umboh |
| 2015 | Online Principal Components Analysis. Christos Boutsidis, Dan Garber, Zohar Shay Karnin, Edo Liberty |
| 2015 | Online Stochastic Matching with Unequal Probabilities. Aranyak Mehta, Bo Waggoner, Morteza Zadimoghaddam |
| 2015 | Online Submodular Maximization with Preemption. Niv Buchbinder, Moran Feldman, Roy Schwartz |
| 2015 | Optimal approximation for submodular and supermodular optimization with bounded curvature. Maxim Sviridenko, Jan Vondrák, Justin Ward |
| 2015 | Optimal detection of intersections between convex polyhedra. Luis Barba, Stefan Langerman |
| 2015 | Parameterized Streaming: Maximal Matching and Vertex Cover. Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, Morteza Monemizadeh |
| 2015 | Perfect Bayesian Equilibria in Repeated Sales. Nikhil R. Devanur, Yuval Peres, Balasubramanian Sivan |
| 2015 | Phase Transitions in Random Dyadic Tilings and Rectangular Dissections. Sarah Cannon, Sarah Miracle, Dana Randall |
| 2015 | Plurality Consensus in the Gossip Model. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri |
| 2015 | Pricing Online Decisions: Beyond Auctions. Ilan Reuven Cohen, Alon Eden, Amos Fiat, Lukasz Jez |
| 2015 | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 Piotr Indyk |
| 2015 | Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri |
| 2015 | Rejecting jobs to Minimize Load and Maximum Flow-time. Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar |
| 2015 | Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online T.-H. Hubert Chan, Fei Chen, Shaofeng H.-C. Jiang |
| 2015 | Robust Price of Anarchy Bounds via LP and Fenchel Duality. Janardhan Kulkarni, Vahab S. Mirrokni |
| 2015 | Robust Probabilistic Inference. Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz |
| 2015 | Robust hamiltonicity of random directed graphs Asaf Ferber, Rajko Nenadov, Ueli Peter, Andreas Noever, Nemanja Skoric |
| 2015 | Robust randomized matchings. Jannik Matuschke, Martin Skutella, José A. Soto |
| 2015 | Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel. Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons |
| 2015 | Set membership with a few bit probes. Mohit Garg, Jaikumar Radhakrishnan |
| 2015 | Sharp Bounds on Formation-free Sequences. Seth Pettie |
| 2015 | Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing. Daniel Dadush, Nicolas Bonifas |
| 2015 | Sketching for Kenneth L. Clarkson, David P. Woodruff |
| 2015 | Solving Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh |
| 2015 | Spatial mixing and the connective constant: Optimal bounds. Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, Yitong Yin |
| 2015 | Speeding up the Four Russians Algorithm by About One More Logarithmic Factor. Timothy M. Chan |
| 2015 | Sperner's Colorings, Hypergraph Labeling Problems and Fair Division. Maryam Mirzakhani, Jan Vondrák |
| 2015 | Spider covers for prize-collecting network activation problem. Takuro Fukunaga |
| 2015 | Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak |
| 2015 | Streaming Lower Bounds for Approximating MAX-CUT. Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2015 | Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Venkatesan Guruswami, Euiwoong Lee |
| 2015 | Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams |
| 2015 | Surprise probabilities in Markov chains. James Norris, Yuval Peres, Alex Zhai |
| 2015 | Testing Identity of Structured Distributions. Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin |
| 2015 | Testing Poisson Binomial Distributions. Jayadev Acharya, Constantinos Daskalakis |
| 2015 | The Complexity of Estimating Rényi Entropy. Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, Himanshu Tyagi |
| 2015 | The Parameterized Complexity of Bingkai Lin |
| 2015 | The Polyhedron-Hitting Problem. Ventsislav Chonev, Joël Ouaknine, James Worrell |
| 2015 | The Simplex Algorithm is NP-mighty. Yann Disser, Martin Skutella |
| 2015 | The Speed of Evolution. Nisheeth K. Vishnoi |
| 2015 | The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games. Krishnendu Chatterjee, Rasmus Ibsen-Jensen |
| 2015 | The amortized cost of finding the minimum. Haim Kaplan, Or Zamir, Uri Zwick |
| 2015 | The matching polytope does not admit fully-polynomial size relaxation schemes. Gábor Braun, Sebastian Pokutta |
| 2015 | The optimal absolute ratio for online bin packing. János Balogh, József Békési, György Dósa, Jirí Sgall, Rob van Stee |
| 2015 | The size of the core in assignment markets. Yash Kanoria, Daniela Sabán, Jay Sethuraman |
| 2015 | The switch Markov chain for sampling irregular graphs (Extended Abstract). Catherine S. Greenhill |
| 2015 | Tight Bounds on Vertex Connectivity Under Vertex Sampling. Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn |
| 2015 | Tight lower bound for the channel assignment problem. Arkadiusz Socala |
| 2015 | Tighter Low-rank Approximation via Sampling the Leveraged Element. Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi |
| 2015 | Towards a Characterization of Constant-Factor Approximable Min CSPs. Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran |
| 2015 | Triangulation Refinement and Approximate Shortest Paths in Weighted Regions. Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron |
| 2015 | Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly. Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller |
| 2015 | Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel. Zeyuan Allen Zhu, Lorenzo Orecchia |
| 2015 | Wavelet Trees Meet Suffix Trees. Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya |
| 2015 | Welfare Maximization with Production Costs: A Primal Dual Approach. Zhiyi Huang, Anthony Kim |
| 2015 | Zigzag Persistence via Reflections and Transpositions. Clément Maria, Steve Y. Oudot |