| 2015 | Improved Region-Growing and Combinatorial Algorithms for | Guru Guruganesh, Laura Sanit, Chaitanya Swamy |
| 2015 | Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading. | Zeyu Guo, He Sun |
| 2015 | The switch Markov chain for sampling irregular graphs (Extended Abstract). | Catherine S. Greenhill |
| 2015 | Approximate Range Emptiness in Constant Time and Optimal Space. | Mayank Goswami, Allan Grnlund Jrgensen, Kasper Green Larsen, Rasmus Pagh |
| 2015 | A Stable Marriage Requires Communication. | Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum |
| 2015 | Connectivity in Random Forests and Credit Networks. | Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang |
| 2015 | LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes. | Badih Ghazi, Euiwoong Lee |
| 2015 | 2-Edge Connectivity in Directed Graphs. | Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis |
| 2015 | Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. | Ran Gelles, Bernhard Haeupler |
| 2015 | Set membership with a few bit probes. | Mohit Garg, Jaikumar Radhakrishnan |
| 2015 | Spider covers for prize-collecting network activation problem. | Takuro Fukunaga |
| 2015 | Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm. | Mathew C. Francis, Pavol Hell, Juraj Stacho |
| 2015 | Density and regularity theorems for semi-algebraic hypergraphs. | Jacob Fox, Jnos Pach, Andrew Suk |
| 2015 | Solving | Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh |
| 2015 | Robust hamiltonicity of random directed graphs | Asaf Ferber, Rajko Nenadov, Ueli Peter, Andreas Noever, Nemanja Skoric |
| 2015 | A Simple | Moran Feldman, Ola Svensson, Rico Zenklusen |
| 2015 | Combinatorial Auctions via Posted Prices. | Michal Feldman, Nick Gravin, Brendan Lucier |
| 2015 | Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly. | Sndor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller |
| 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 | Geometric | Sylvester David Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeek, Hakan Yildiz |
| 2015 | (2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. | Michael Elkin, Seth Pettie, Hsin-Hao Su |
| 2015 | A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. | Michael Elkin, Seth Pettie |
| 2015 | On the Complexity of Computing an Equilibrium in Combinatorial Auctions. | Shahar Dobzinski, Hu Fu, Robert D. Kleinberg |
| 2015 | The Simplex Algorithm is NP-mighty. | Yann Disser, Martin Skutella |
| 2015 | A Unified Framework for Clustering Constrained Data without Locality Property. | Hu Ding, Jinhui Xu |