| 2019 | (1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time. Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, Shay Solomon |
| 2019 | A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists. Chi-Kit Lam, C. Gregory Plaxton |
| 2019 | A 1.5-Approximation for Path TSP. Rico Zenklusen |
| 2019 | A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. Aaron Bernstein, Sebastian Forster, Monika Henzinger |
| 2019 | A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey |
| 2019 | A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs. Nathaniel Lahn, Sharath Raghvendra |
| 2019 | A Faster External Memory Priority Queue with DecreaseKeys. Shunhua Jiang, Kasper Green Larsen |
| 2019 | A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. Rebecca Hoberg, Thomas Rothvoss |
| 2019 | A Nearly-Linear Bound for Chasing Nested Convex Bodies. C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee |
| 2019 | A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond. Martin Nägele, Rico Zenklusen |
| 2019 | A New Path from Splay to Dynamic Optimality. Caleb C. Levy, Robert E. Tarjan |
| 2019 | A PTAS for Euclidean TSP with Hyperplane Neighborhoods. Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, Kevin Schewior |
| 2019 | A PTAS for ℓp-Low Rank Approximation. Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff |
| 2019 | A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. Uriel Feige, Janardhan Kulkarni, Shi Li |
| 2019 | A Subquadratic Approximation Scheme for Partition. Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk |
| 2019 | A sort of an adversary. Haim Kaplan, Or Zamir, Uri Zwick |
| 2019 | A tight Erdős-Pósa function for planar minors. Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond |
| 2019 | A time- and space-optimal algorithm for the many-visits TSP. André Berger, László Kozma, Matthias Mnich, Roland Vincze |
| 2019 | A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall |
| 2019 | Adaptive Sparse Recovery with Limited Adaptivity. Akshay Kamath, Eric Price |
| 2019 | Algorithms for #BIS-hard problems on expander graphs. Matthew Jenssen, Peter Keevash, Will Perkins |
| 2019 | Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta |
| 2019 | An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. Joshua Brakensiek, Venkatesan Guruswami |
| 2019 | An Equivalence Class for Orthogonal Vectors. Lijie Chen, Ryan Williams |
| 2019 | An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2019 | An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. Rebecca Reiffenhäuser |
| 2019 | Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing. Gautam Kamath, Christos Tzamos |
| 2019 | Analysis of Ward's Method. Anna Großwendt, Heiko Röglin, Melanie Schmidt |
| 2019 | Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract]. Irit Dinur, Yuval Filmus, Prahladh Harsha |
| 2019 | Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2019 | Approximability of the Six-vertex Model. Jin-Yi Cai, Tianyu Liu, Pinyan Lu |
| 2019 | Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
| 2019 | Approximating (k, ℓ)-center clustering for curves. Kevin Buchin, Anne Driemel, Joachim Gudmundsson, Michael Horton, Irina Kostitsyna, Maarten Löffler, Martijn Struijs |
| 2019 | Approximating LCS in Linear Time: Beating the √n Barrier. MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Xiaorui Sun |
| 2019 | Assignment Mechanisms under Distributional Constraints. Itai Ashlagi, Amin Saberi, Ali Shameli |
| 2019 | Beating Greedy for Stochastic Bipartite Matching. Buddhima Gamlath, Sagar Kale, Ola Svensson |
| 2019 | Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms. Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling, Hengjia Wei |
| 2019 | Can We Overcome the n log n Barrier for Oblivious Sorting? Wei-Kai Lin, Elaine Shi, Tiancheng Xie |
| 2019 | Cheeger Inequalities for Submodular Transformations. Yuichi Yoshida |
| 2019 | Colored range closest-pair problem under general distance functions. Jie Xue |
| 2019 | Communication Complexity of Discrete Fair Division. Benjamin Plaut, Tim Roughgarden |
| 2019 | Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna |
| 2019 | Computing Height Persistence and Homology Generators in R Tamal K. Dey |
| 2019 | Computing all Wardrop Equilibria parametrized by the Flow Demand. Max Klimm, Philipp Warode |
| 2019 | Constructive Polynomial Partitioning for Algebraic Curves in R Boris Aronov, Esther Ezra, Joshua Zahl |
| 2019 | Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity. Fahad Panolan, Saket Saurabh, Meirav Zehavi |
| 2019 | Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein |
| 2019 | Correlation-Robust Analysis of Single Item Auction. Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang |
| 2019 | Derandomized Balanced Allocation. Xue Chen |
| 2019 | Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid. Niv Buchbinder, Moran Feldman, Mohit Garg |
| 2019 | Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time. Sayan Bhattacharya, Janardhan Kulkarni |
| 2019 | Dimension-independent Sparse Fourier Transform. Michael Kapralov, Ameya Velingker, Amir Zandieh |
| 2019 | Distributed Algorithms Made Secure: A Graph Theoretic Approach. Merav Parter, Eylon Yogev |
| 2019 | Distributed Maximal Independent Set using Small Messages. Mohsen Ghaffari |
| 2019 | Distributed Triangle Detection via Expander Decomposition. Yi-Jun Chang, Seth Pettie, Hengjie Zhang |
| 2019 | Dynamic Double Auctions: Towards First Best. Santiago R. Balseiro, Vahab S. Mirrokni, Renato Paes Leme, Song Zuo |
| 2019 | Dynamic Edge Coloring with Improved Approximation. Ran Duan, Haoqing He, Tianyi Zhang |
| 2019 | Efficient Algorithms and Lower Bounds for Robust Linear Regression. Ilias Diakonikolas, Weihao Kong, Alistair Stewart |
| 2019 | Efficiently Approximating Edit Distance Between Pseudorandom Strings. William Kuszmaul |
| 2019 | Elastic Caching. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi |
| 2019 | Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. Eli Fox-Epstein, Philip N. Klein, Aaron Schild |
| 2019 | Every Collinear Set in a Planar Graph Is Free. Vida Dujmovic, Fabrizio Frati, Daniel Gonçalves, Pat Morin, Günter Rote |
| 2019 | Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty. Hendrik Fichtenberger, Pan Peng, Christian Sohler |
| 2019 | Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS. Zachary Friggstad, Kamyar Khodamoradi, Mohammad R. Salavatipour |
| 2019 | Exact Distance Oracles for Planar Graphs with Failing Vertices. Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka |
| 2019 | Expander Decomposition and Pruning: Faster, Stronger, and Simpler. Thatchaphol Saranurak, Di Wang |
| 2019 | Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones. Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz |
| 2019 | Extremal and probabilistic results for order types. Jie Han, Yoshiharu Kohayakawa, Marcelo Tadeu Sales, Henrique Stagni |
| 2019 | Fast Modular Subset Sum using Linear Sketching. Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, Hongxun Wu |
| 2019 | Fast greedy for linear matroids. Huy L. Nguyen |
| 2019 | Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. Karl Bringmann, Marvin Künnemann, Philip Wellnitz |
| 2019 | Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time. David Eppstein, Bruce A. Reed |
| 2019 | Fine-grained Complexity Meets IP = PSPACE. Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein |
| 2019 | Flow-Cut Gaps and Face Covers in Planar Graphs. Robert Krauthgamer, James R. Lee, Havana Rika |
| 2019 | Foundations of Differentially Oblivious Algorithms. T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, Elaine Shi |
| 2019 | Four-coloring P6-free graphs. Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong |
| 2019 | Front Matter. |
| 2019 | Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. Karl Bringmann, Marvin Künnemann, André Nusser |
| 2019 | Full Tilt: Universal Constructors for General Shapes with Uniform External Forces. Jose Balanza-Martinez, Austin Luchsinger, David Caballero, Rene Reyes, Angel A. Cantu, Robert Schweller, Luis Angel Garcia, Tim Wylie |
| 2019 | Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon |
| 2019 | Fully Polynomial-Time Approximation Schemes for Fair Rent Division. Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi |
| 2019 | Greedy spanners are optimal in doubling metrics. Glencora Borradaile, Hung Le, Christian Wulff-Nilsen |
| 2019 | Hardness of Approximation for Morse Matching. Ulrich Bauer, Abhishek Rathod |
| 2019 | Hierarchical Clustering better than Average-Linkage. Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh |
| 2019 | High-Dimensional Robust Mean Estimation in Nearly-Linear Time. Yu Cheng, Ilias Diakonikolas, Rong Ge |
| 2019 | How to guess an n-digit number. Zilin Jiang, Nikita Polyanskii |
| 2019 | I/O-Efficient Algorithms for Topological Sort and Related Problems. Nairen Cao, Jeremy T. Fineman, Katina Russell, Eugene Yang |
| 2019 | Improved Bounds for Randomly Sampling Colorings via Linear Programming. Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle |
| 2019 | Improved Topological Approximations by Digitization. Aruni Choudhary, Michael Kerber, Sharath Raghvendra |
| 2019 | Improving the smoothed complexity of FLIP for max cut problems. Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran |
| 2019 | Interval Vertex Deletion Admits a Polynomial Kernel. Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, Meirav Zehavi |
| 2019 | Iterative Refinement for ℓp-norm Regression. Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva |
| 2019 | Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time. Shashwat Garg, Janardhan Kulkarni, Shi Li |
| 2019 | List Decoding with Double Samplers. Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma |
| 2019 | Losing Treewidth by Separating Subsets. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk |
| 2019 | Low Congestion Cycle Covers and Their Applications. Merav Parter, Eylon Yogev |
| 2019 | Lower Bounds for Oblivious Data Structures. Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen |
| 2019 | Lower bounds for text indexing with mismatches and differences. Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya |
| 2019 | Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. MohammadTaghi Hajiaghayi, Saeed Seddighin, Xiaorui Sun |
| 2019 | Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities. Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin |
| 2019 | Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities and Multiple Sources and Sinks. Yipu Wang |
| 2019 | Metrical task systems on trees via mirror descent and unfair gluing. Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee |
| 2019 | Minimizing Interference Potential Among Moving Entities. Daniel Busto, William S. Evans, David G. Kirkpatrick |
| 2019 | Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions. Kyle Fox, Debmalya Panigrahi, Fred Zhang |
| 2019 | Multi-unit Supply-monotone Auctions with Bayesian Valuations. Yuan Deng, Debmalya Panigrahi |
| 2019 | Nash Flows Over Time with Spillback. Leon Sering, Laura Vargas Koch |
| 2019 | Near Optimal Algorithms For The Single Source Replacement Paths Problem. Shiri Chechik, Sarel Cohen |
| 2019 | Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse |
| 2019 | Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces. Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen |
| 2019 | New Lower Bounds for the Number of Pseudoline Arrangements. Adrian Dumitrescu, Ritankar Mandal |
| 2019 | Non-empty Bins with Simple Tabulation Hashing. Anders Aamand, Mikkel Thorup |
| 2019 | Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma. David G. Harris |
| 2019 | On Approximating (Sparse) Covering Integer Programs. Chandra Chekuri, Kent Quanrud |
| 2019 | On Constant Multi-Commodity Flow-Cut Gaps for Families of Directed Minor-Free Graphs. Ario Salmasi, Anastasios Sidiropoulos, Vijay Sridhar |
| 2019 | On Facility Location with General Lower Bounds. Shi Li |
| 2019 | On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald |
| 2019 | On r-Simple k-Path and Related Problems Parameterized by k/r. Gregory Z. Gutin, Magnus Wahlström, Meirav Zehavi |
| 2019 | On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes). Rohit Gurjar, Nisheeth K. Vishnoi |
| 2019 | On the Spanning and Routing Ratio of Theta-Four. Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, Michiel H. M. Smid |
| 2019 | On the Structure of Unique Shortest Paths in Graphs. Greg Bodwin |
| 2019 | On the discrepancy of random low degree set systems. Nikhil Bansal, Raghu Meka |
| 2019 | On the rank of a random binary matrix. Colin Cooper, Alan M. Frieze, Wesley Pegden |
| 2019 | Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons. Eunjin Oh |
| 2019 | Optimal Ball Recycling. Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton, Rob Johnson, Meng-Tsung Tsai |
| 2019 | Optimal Construction of Compressed Indexes for Highly Repetitive Texts. Dominik Kempa |
| 2019 | Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model. Shiri Chechik, Doron Mukhtar |
| 2019 | Optimal Las Vegas Approximate Near Neighbors in ℓp. Alexander Wei |
| 2019 | Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. Jelani Nelson, Huacheng Yu |
| 2019 | Optimal Lower Bounds for Sketching Graph Cuts. Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan |
| 2019 | Optimizing quantum optimization algorithms via faster quantum gradient computation. András Gilyén, Srinivasan Arunachalam, Nathan Wiebe |
| 2019 | Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. Jin-Yi Cai, Artem Govorov |
| 2019 | Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications. AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford |
| 2019 | Polynomial Planar Directed Grid Theorem. Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer |
| 2019 | Polynomial bounds for centered colorings on proper minor-closed graph classes. Michal Pilipczuk, Sebastian Siebertz |
| 2019 | Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs. MohammadHossein Bateni, Alireza Farhadi, MohammadTaghi Hajiaghayi |
| 2019 | Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs. Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk |
| 2019 | Popular Matching in Roommates Setting is NP-hard. Sushmita Gupta, Pranabendu Misra, Saket Saurabh, Meirav Zehavi |
| 2019 | Popular Matchings and Limits to Tractability. Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, Xingyu Zhang |
| 2019 | Pricing for Online Resource Allocation: Intervals and Paths. Shuchi Chawla, J. Benjamin Miller, Yifeng Teng |
| 2019 | Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication. Matti Karppa, Petteri Kaski |
| 2019 | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 Timothy M. Chan |
| 2019 | Prophet Secretary Through Blind Strategies. José Correa, Raimundo Saona, Bruno Ziliotto |
| 2019 | Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design. Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat |
| 2019 | Pseudorandomness for read-k DNF formulas. Rocco A. Servedio, Li-Yang Tan |
| 2019 | Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs |
| 2019 | Quantum algorithms and approximating polynomials for composed functions with shared inputs. Mark Bun, Robin Kothari, Justin Thaler |
| 2019 | Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices. Georgios Amanatidis, Pieter Kleer |
| 2019 | Relative Error Tensor Low Rank Approximation. Zhao Song, David P. Woodruff, Peilin Zhong |
| 2019 | Reproducibility and Pseudo-Determinism in Log-Space. Ofer Grossman, Yang P. Liu |
| 2019 | SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension. Kevin Buchin, Tim Ophelders, Bettina Speckmann |
| 2019 | SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay |
| 2019 | Seeded Graph Matching via Large Neighborhood Statistics. Elchanan Mossel, Jiaming Xu |
| 2019 | Short Cycles via Low-Diameter Decompositions. Yang P. Liu, Sushant Sachdeva, Zejun Yu |
| 2019 | Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. Mohsen Ghaffari, Jara Uitto |
| 2019 | Spectral Sparsification of Hypergraphs. Tasuku Soma, Yuichi Yoshida |
| 2019 | Stochastic Matching with Few Queries: New Algorithms and Tools. Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani |
| 2019 | Stochastic Submodular Cover with Limited Adaptivity. Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna |
| 2019 | Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method. Marco Molinaro |
| 2019 | Strategies for Stable Merge Sorting. Sam Buss, Alexander Knop |
| 2019 | Sublinear Algorithms for (Δ + 1) Vertex Coloring. Sepehr Assadi, Yu Chen, Sanjeev Khanna |
| 2019 | Submodular Function Maximization in Parallel via the Multilinear Relaxation. Chandra Chekuri, Kent Quanrud |
| 2019 | Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity. Matthew Fahrbach, Vahab S. Mirrokni, Morteza Zadimoghaddam |
| 2019 | Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. Alina Ene, Huy L. Nguyen |
| 2019 | Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets. Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu |
| 2019 | Testing Halfspaces over Rotation-Invariant Distributions. Nathaniel Harms |
| 2019 | Testing Matrix Rank, Optimally. Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang |
| 2019 | The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. Subhash Khot, Assaf Naor |
| 2019 | The Complexity of Approximately Counting Retractions. Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný |
| 2019 | The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain. Monaldo Mastrolilli |
| 2019 | The I/O complexity of Toom-Cook integer multiplication. Gianfranco Bilardi, Lorenzo De Stefani |
| 2019 | The Maximum Number of Minimal Dominating Sets in a Tree. Günter Rote |
| 2019 | The streaming k-mismatch problem. Raphaël Clifford, Tomasz Kociumaka, Ely Porat |
| 2019 | The threshold for SDP-refutation of random regular NAE-3SAT. Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen |
| 2019 | Theorems of Carathéodory, Helly, and Tverberg without dimension. Karim A. Adiprasito, Imre Bárány, Nabil H. Mustafa |
| 2019 | Tight Bounds for ℓp Oblivious Subspace Embeddings. Ruosong Wang, David P. Woodruff |
| 2019 | Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, Yuhao Zhang |
| 2019 | Tight Revenue Gaps among Simple Mechanisms. Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, Tao Xiao |
| 2019 | Towards Instance-Optimal Private Query Release. Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke |
| 2019 | Towards Tight(er) Bounds for the Excluded Grid Theorem. Julia Chuzhoy, Zihan Tan |
| 2019 | Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, Pawel Parys |
| 2019 | Vector clique decompositions. Raphael Yuster |
| 2019 | Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees. Amir Nayyeri, Benjamin Raichel |
| 2019 | XOR Codes and Sparse Learning Parity with Noise. Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan |
| 2019 | Zeros of Holant problems: locations and algorithms. Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang |
| 2019 | k-Servers with a Smile: Online Algorithms via Projections. Niv Buchbinder, Anupam Gupta, Marco Molinaro, Joseph (Seffi) Naor |