| 2017 | (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker |
| 2017 | (1 + ∊)-Approximate Shiri Chechik, Sarel Cohen, Amos Fiat, Haim Kaplan |
| 2017 | A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. Ami Paz, Gregory Schwartzman |
| 2017 | A Faster Pseudopolynomial Time Algorithm for Subset Sum. Konstantinos Koiliaris, Chao Xu |
| 2017 | A Framework for Analyzing Resparsification Algorithms. Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva |
| 2017 | A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering. Tobias Christiani |
| 2017 | A Hierarchy of Lower Bounds for Sublinear Additive Spanners. Amir Abboud, Greg Bodwin, Seth Pettie |
| 2017 | A Hybrid Sampling Scheme for Triangle Counting. John Kallaugher, Eric Price |
| 2017 | A Logarithmic Additive Integrality Gap for Bin Packing. Rebecca Hoberg, Thomas Rothvoss |
| 2017 | A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. Karl Bringmann |
| 2017 | A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs. Amir Nayyeri, Benjamin Raichel |
| 2017 | A constant-time algorithm for middle levels Gray codes. Torsten Mütze, Jerri Nummenpalo |
| 2017 | A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number. Clément Maria, Jonathan Spreer |
| 2017 | A tight bound for Green's arithmetic triangle removal lemma in vector spaces. Jacob Fox, László Miklós Lovász |
| 2017 | About the Structure of the Integer Cone and its Application to Bin Packing. Klaus Jansen, Kim-Manuel Klein |
| 2017 | Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance. Timothy Naumovitz, Michael E. Saks, C. Seshadhri |
| 2017 | Adaptive Matrix Vector Product. Santosh S. Vempala, David P. Woodruff |
| 2017 | Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions. Anupam Gupta, Viswanath Nagarajan, Sahil Singla |
| 2017 | Algorithmic and Hardness Results for the Hub Labeling Problem. Haris Angelidakis, Yury Makarychev, Vsevolod Oparin |
| 2017 | An James B. Orlin, Antonio Sedeño-Noda |
| 2017 | An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. Michele Borassi, Pierluigi Crescenzi, Luca Trevisan |
| 2017 | An Efficient Representation for Filtrations of Simplicial Complexes. Jean-Daniel Boissonnat, Karthik C. S. |
| 2017 | An FPTAS for Counting Proper Four-Colorings on Cubic Graphs. Pinyan Lu, Kuan Yang, Chihao Zhang, Minshen Zhu |
| 2017 | An Improved Upper Bound for the Universal TSP on the Grid. George Christodoulou, Alkmini Sgouritsa |
| 2017 | Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. Moses Charikar, Vaggos Chatziafratis |
| 2017 | Approximately Sampling Elements with Fixed Rank in Graded Posets. Prateek Bhakta, Ben Cousins, Matthew Fahrbach, Dana Randall |
| 2017 | Approximating Multicut and the Demand Graph. Chandra Chekuri, Vivek Madan |
| 2017 | Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit |
| 2017 | Approximation Algorithms for Finding Maximum Induced Expanders. Shayan Oveis Gharan, Alireza Rezaei |
| 2017 | Approximation Algorithms for Label Cover and The Log-Density Threshold. Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan |
| 2017 | Approximation and Kernelization for Chordal Vertex Deletion. Bart M. P. Jansen, Marcin Pilipczuk |
| 2017 | Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs. David Adjiashvili |
| 2017 | Beating Brute Force for Systems of Polynomial Equations over Finite Fields. Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu |
| 2017 | Best-Response Dynamics in Combinatorial Auctions with Item Bidding. Paul Dütting, Thomas Kesselheim |
| 2017 | Better Approximations for Tree Sparsity in Nearly-Linear Time. Arturs Backurs, Piotr Indyk, Ludwig Schmidt |
| 2017 | Better upper bounds on the Füredi-Hajnal limits of permutations. Josef Cibulka, Jan Kyncl |
| 2017 | Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. Adrian Kosowski, Laurent Viennot |
| 2017 | Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs. Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz |
| 2017 | Bridging the Capacity Gap Between Interactive and One-Way Communication. Bernhard Haeupler, Ameya Velingker |
| 2017 | Building a Good Team: Secretary Problems and the Supermodular Degree. Moran Feldman, Rani Izsak |
| 2017 | Combinatorial Prophet Inequalities. Aviad Rubinstein, Sahil Singla |
| 2017 | Competitive analysis of the top- Xi Chen, Sivakanth Gopi, Jieming Mao, Jon Schneider |
| 2017 | Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams |
| 2017 | Computing Walrasian Equilibria: Fast Algorithms and Structural Properties. Renato Paes Leme, Sam Chiu-wai Wong |
| 2017 | Computing minimum cuts in hypergraphs. Chandra Chekuri, Chao Xu |
| 2017 | Computing the Fréchet Distance between Real-Valued Surfaces. Kevin Buchin, Tim Ophelders, Bettina Speckmann |
| 2017 | Connectivity Oracles for Graphs Subject to Vertex Failures. Ran Duan, Seth Pettie |
| 2017 | Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities. Shi Li |
| 2017 | Convergence of Incentive-Driven Dynamics in Fisher Markets. Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman |
| 2017 | Core congestion is inherent in hyperbolic networks. Victor Chepoi, Feodor F. Dragan, Yann Vaxès |
| 2017 | Counting matchings in irregular bipartite graphs and random lifts. Marc Lelarge |
| 2017 | Cross-Referenced Dictionaries and the Limits of Write Optimization. Peyman Afshani, Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Mayank Goswami, Meng-Tsung Tsai |
| 2017 | Decidability of the Membership Problem for 2 × 2 integer matrices. Igor Potapov, Pavel Semukhin |
| 2017 | Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold. Éric Colin de Verdière, Salman Parsa |
| 2017 | Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs. Aaron Bernstein, Shiri Chechik |
| 2017 | Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma. David G. Harris |
| 2017 | Distance Sensitive Bloom Filters Without False Negatives. Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen |
| 2017 | Distributed Degree Splitting, Edge Coloring, and Orientations. Mohsen Ghaffari, Hsin-Hao Su |
| 2017 | Doubly Balanced Connected Graph Partitioning. Saleh Soltan, Mihalis Yannakakis, Gil Zussman |
| 2017 | Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir |
| 2017 | ETH Hardness for Densest- Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein |
| 2017 | Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. Michael Elkin, Ofer Neiman |
| 2017 | Eliminating Depth Cycles among Triangles in Three Dimensions. Boris Aronov, Edward Y. Miller, Micha Sharir |
| 2017 | Even Delta-Matroids and the Complexity of Planar Boolean CSPs. Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek |
| 2017 | Explicit Resilient Functions Matching Ajtai-Linial. Raghu Meka |
| 2017 | Exploring an Infinite Space with Finite Memory Scouts. Lihi Cohen, Yuval Emek, Oren Louidor, Jara Uitto |
| 2017 | Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals. Nicole Immorlica, Robert Kleinberg, Brendan Lucier, Morteza Zadomighaddam |
| 2017 | Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations. Robert Hildebrand, Robert Weismantel, Rico Zenklusen |
| 2017 | Fair Coin Flipping: Tighter Analysis and the Many-Party Case. Niv Buchbinder, Iftach Haitner, Nissan Levi, Eliad Tsfadia |
| 2017 | Fair Scheduling via Iterative Quasi-Uniform Sampling. Sungjin Im, Benjamin Moseley |
| 2017 | Fast and Memory-Efficient Algorithms for Evacuation Problems. Miriam Schlöter, Martin Skutella |
| 2017 | Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis |
| 2017 | Faster Online Matrix-Vector Multiplication. Kasper Green Larsen, R. Ryan Williams |
| 2017 | Faster Sublinear Algorithms using Conditional Sampling. Themistoklis Gouleakis, Christos Tzamos, Manolis Zampetakis |
| 2017 | Faster approximation schemes for the two-dimensional knapsack problem. Sandy Heydrich, Andreas Wiese |
| 2017 | Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi |
| 2017 | File Maintenance: When in Doubt, Change the Layout! Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, Pablo Montes |
| 2017 | Find Your Place: Simple Distributed Algorithms for Community Detection. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan |
| 2017 | Firefighting on Trees Beyond Integrality Gaps. David Adjiashvili, Andrea Baggio, Rico Zenklusen |
| 2017 | Front Matter. |
| 2017 | Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
| 2017 | Fully Dynamic Connectivity in Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie |
| 2017 | Fully dynamic all-pairs shortest paths with worst-case update-time revisited. Ittai Abraham, Shiri Chechik, Sebastian Krinninger |
| 2017 | Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna |
| 2017 | Generalized Preconditioning and Undirected Minimum-Cost Flow. Jonah Sherman |
| 2017 | Geodesic Spanners for Points on a Polyhedral Terrain. Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji |
| 2017 | Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. Pavel Hubácek, Eylon Yogev |
| 2017 | Hardness of Permutation Pattern Matching. Vít Jelínek, Jan Kyncl |
| 2017 | High-dimensional approximate Georgia Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, Ioannis Psarros |
| 2017 | Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances. Micha Sharir, Noam Solomon |
| 2017 | Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling. Michael B. Cohen, Cameron Musco, Christopher Musco |
| 2017 | Iterative Partial Rounding for Vertex Cover with Hard Capacities. Mong-Jen Kao |
| 2017 | LAST but not Least: Online Spanners for Buy-at-Bulk. Anupam Gupta, R. Ravi, Kunal Talwar, Seeun William Umboh |
| 2017 | LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP. Daniel Prusa, Tomás Werner |
| 2017 | LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. Nikhil Bansal, Daniel Reichman, Seeun William Umboh |
| 2017 | LP-branching algorithms based on biased graphs. Magnus Wahlström |
| 2017 | LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs. Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli |
| 2017 | LSH Forest: Practical Algorithms Made Theoretical. Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki |
| 2017 | Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. Christoph Berkholz, Martin Grohe |
| 2017 | Linear Size Distance Preservers. Greg Bodwin |
| 2017 | Local Flow Partitioning for Faster Edge Connectivity. Monika Henzinger, Satish Rao, Di Wang |
| 2017 | Local Search for Max-Sum Diversification. Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen |
| 2017 | Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound. Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf |
| 2017 | Low-Rank PSD Approximation in Input-Sparsity Time. Kenneth L. Clarkson, David P. Woodruff |
| 2017 | MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. Venkatesan Guruswami, Ankit Singh Rawat |
| 2017 | Make Up Your Mind: The Price of Online Queries in Differential Privacy. Mark Bun, Thomas Steinke, Jonathan R. Ullman |
| 2017 | Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. Paul Beame, Cyrus Rashtchian |
| 2017 | Matrix Balancing in Rafail Ostrovsky, Yuval Rabani, Arman Yousefi |
| 2017 | Maximally Recoverable Codes for Grid-like Topologies. Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin |
| 2017 | Maximum Scatter TSP in Doubling Metrics. László Kozma, Tobias Mömke |
| 2017 | Metric embeddings with outliers. Anastasios Sidiropoulos, Dingkang Wang, Yusu Wang |
| 2017 | Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits. Lucas Boczkowski, Amos Korman, Emanuele Natale |
| 2017 | Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. Eden Chlamtác, Michael Dinitz, Yury Makarychev |
| 2017 | Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds. Yixin Cao, R. B. Sandeep |
| 2017 | Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems. Chandra Chekuri, Kent Quanrud |
| 2017 | Near-Optimal (Euclidean) Metric Compression. Piotr Indyk, Tal Wagner |
| 2017 | Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ ( Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu |
| 2017 | On Estimating Maximum Matching Size in Graph Streams. Sepehr Assadi, Sanjeev Khanna, Yang Li |
| 2017 | On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. Chaya Keller, Shakhar Smorodinsky, Gábor Tardos |
| 2017 | On Rationality of Nonnegative Matrix Factorization. Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell |
| 2017 | On the Configuration-LP of the Restricted Assignment Problem. Klaus Jansen, Lars Rohwedder |
| 2017 | On the insertion time of random walk cuckoo hashing. Alan M. Frieze, Tony Johansson |
| 2017 | Online Lower Bounds via Duality. Yossi Azar, Ilan Reuven Cohen, Alan Roytman |
| 2017 | Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids. T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang |
| 2017 | Online and Random-order Load Balancing Simultaneously. Marco Molinaro |
| 2017 | Optimal Approximate Polytope Membership. Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
| 2017 | Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten |
| 2017 | Optimal induced universal graphs for bounded-degree graphs. Noga Alon, Rajko Nenadov |
| 2017 | Optimization of Bootstrapping in Circuits. Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, Hang Zhou |
| 2017 | Opting Into Optimal Matchings. Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia, Rohit Vaish |
| 2017 | Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs. Bernhard Haeupler, David G. Harris |
| 2017 | Parameter-free Locality Sensitive Hashing for Spherical Range Reporting. Thomas D. Ahle, Martin Aumüller, Rasmus Pagh |
| 2017 | Parameter-free Topology Inference and Sparsification for Data on Manifolds. Tamal K. Dey, Zhe Dong, Yusu Wang |
| 2017 | Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints. Xue Chen, Yuan Zhou |
| 2017 | Partial and Constrained Level Planarity. Guido Brückner, Ignaz Rutter |
| 2017 | Partitioning a Graph into Small Pieces with Applications to Path Transversal. Euiwoong Lee |
| 2017 | Permutation Property Testing under Different Metrics with Low Query Complexity. Jacob Fox, Fan Wei |
| 2017 | Playing Anonymous Games using Simple Strategies. Yu Cheng, Ilias Diakonikolas, Alistair Stewart |
| 2017 | Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays. Yossi Azar, Ashish Chiplunkar, Haim Kaplan |
| 2017 | Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz |
| 2017 | Popularity, Mixed Matchings, and Self-duality. Chien-Chung Huang, Telikepalli Kavitha |
| 2017 | Probabilistic clustering of high dimensional norms. Assaf Naor |
| 2017 | Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 Philip N. Klein |
| 2017 | Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search. Sariel Har-Peled, Sepideh Mahabadi |
| 2017 | Random Contractions and Sampling for Hypergraph and Hedge Connectivity. Mohsen Ghaffari, David R. Karger, Debmalya Panigrahi |
| 2017 | Random Walks and Evolving Sets: Faster Convergences and Limitations. Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau |
| 2017 | Random Walks with the Minimum Degree Local Rule Have Roee David, Uriel Feige |
| 2017 | Random cluster dynamics for the Ising model is rapidly mixing. Heng Guo, Mark Jerrum |
| 2017 | Reordering Buffers with Logarithmic Diameter Dependency for Trees. Matthias Englert, Harald Räcke |
| 2017 | Robust algorithms with polynomial loss for near-unanimity CSPs. Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal |
| 2017 | Sample-Optimal Density Estimation in Nearly-Linear Time. Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt |
| 2017 | Sampling on the Sphere by Mutually Orthogonal Subspaces. Uri Grupel |
| 2017 | Sandpile prediction on a tree in near linear time. Akshay Ramachandran, Aaron Schild |
| 2017 | Scaling Algorithms for Weighted Matching in General Graphs. Ran Duan, Seth Pettie, Hsin-Hao Su |
| 2017 | Sequential measurements, disturbance and property testing. Aram W. Harrow, Cedric Yen-Yu Lin, Ashley Montanaro |
| 2017 | Simplex Transformations and the Multiway Cut Problem. Niv Buchbinder, Roy Schwartz, Baruch Weizman |
| 2017 | Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits. Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson |
| 2017 | Sorting from Noisier Samples. Aviad Rubinstein, Shai Vardi |
| 2017 | Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time. J. Ian Munro, Gonzalo Navarro, Yakov Nekrich |
| 2017 | Spanning Circuits in Regular Matroids. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh |
| 2017 | Sparse Suffix Tree Construction in Optimal Time and Space. Pawel Gawrychowski, Tomasz Kociumaka |
| 2017 | Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density. Sebastian Morr |
| 2017 | Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. Vitaly Feldman, Cristóbal Guzmán, Santosh S. Vempala |
| 2017 | Stochastic Lingxiao Huang, Jian Li |
| 2017 | Strong Connectivity in Directed Graphs under Failures, with Applications. Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis |
| 2017 | Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs. Sergio Cabello |
| 2017 | Testing for Forbidden Order Patterns in an Array. Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler |
| 2017 | The ( Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos |
| 2017 | The Complexity of Simulation and Matrix Multiplication. Massimo Cairo, Romeo Rizzi |
| 2017 | The Identity Problem for Matrix Semigroups in SL Paul C. Bell, Mika Hirvensalo, Igor Potapov |
| 2017 | The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications. Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, Yannik Stein |
| 2017 | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs. Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, Christian Scheffer |
| 2017 | Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs. Sam Chiu-wai Wong |
| 2017 | Tight Bounds for Online TSP on the Line. Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schlöter, Leen Stougie |
| 2017 | Tight Network Topology Dependent Bounds on Rounds of Communication. Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra |
| 2017 | Time-Space Trade-offs in Population Protocols. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, Ronald L. Rivest |
| 2017 | To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, Hang Zhou |
| 2017 | Totally Unimodular Congestion Games. Alberto Del Pia, Michael Ferris, Carla Michini |
| 2017 | Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces. Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, Tim Wylie |
| 2017 | Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios. Christos Kalaitzis, Ola Svensson, Jakub Tarnawski |
| 2017 | When and Why the Topological Coverage Criterion Works. Nicholas J. Cavanna, Kirk P. Gardner, Donald R. Sheehy |
| 2017 | pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems. Arnab Ganguly, Rahul Shah, Sharma V. Thankachan |