| 2019 | Information-Theoretic and Algorithmic Thresholds for Group Testing. | Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick |
| 2019 | On the Fixed-Parameter Tractability of Capacitated Clustering. | Vincent Cohen-Addad, Jason Li |
| 2019 | Tight FPT Approximations for k-Median and k-Means. | Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li |
| 2019 | Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE. | Laura Ciobanu, Murray Elder |
| 2019 | The Norms of Graph Spanners. | Eden Chlamtc, Michael Dinitz, Thomas Robinson |
| 2019 | Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. | Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis |
| 2019 | Estimating the Frequency of a Clustered Signal. | Xue Chen, Eric Price |
| 2019 | Restricted Max-Min Allocation: Approximation and Integrality Gap. | Siu-Wing Cheng, Yuchen Mao |
| 2019 | Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. | Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu |
| 2019 | Query-To-Communication Lifting for BPP Using Inner Product. | Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi |
| 2019 | Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. | Jrmie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth |
| 2019 | The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. | Shantanav Chakraborty, Andrs Gilyn, Stacey Jeffery |
| 2019 | Distributed Reconfiguration of Maximal Independent Sets. | Keren Censor-Hillel, Mikal Rabie |
| 2019 | Temporal Cliques Admit Sparse Spanners. | Arnaud Casteigts, Joseph G. Peters, Jason Schoeters |
| 2019 | Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number. | Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Markus L. Schmid |
| 2019 | Completeness of Graphical Languages for Mixed States Quantum Mechanics. | Titouan Carette, Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart |
| 2019 | On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies. | Ioannis Caragiannis, Angelo Fanelli |
| 2019 | Covert Computation in Self-Assembled Circuits. | Angel A. Cantu, Austin Luchsinger, Robert Schweller, Tim Wylie |
| 2019 | Sign-Rank Can Increase Under Intersection. | Mark Bun, Nikhil S. Mande, Justin Thaler |
| 2019 | A Kleene Theorem for Nominal Automata. | Paul Brunet, Alexandra Silva |
| 2019 | Dismantlability, Connectedness, and Mixing in Relational Structures. | Raimundo Briceo, Andrei A. Bulatov, Vctor Dalmau, Benot Larose |
| 2019 | Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. | Fernando G. S. L. Brando, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, Xiaodi Wu |
| 2019 | Distributed Detection of Cliques in Dynamic Networks. | Matthias Bonne, Keren Censor-Hillel |
| 2019 | String-to-String Interpretations With Polynomial-Size Output. | Mikolaj Bojanczyk, Sandra Kiefer, Nathan Lhote |
| 2019 | Approximate Counting of k-Paths: Deterministic and in Polynomial Space. | Andreas Bjrklund, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi |