| 2019 | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, July 9-12, 2019 Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi |
| 2019 | A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal |
| 2019 | A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games. Dani Dorfman, Haim Kaplan, Uri Zwick |
| 2019 | A Kleene Theorem for Nominal Automata. Paul Brunet, Alexandra Silva |
| 2019 | A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. Martin Grohe, Sandra Kiefer |
| 2019 | A Mahler's Theorem for Word Functions. Jean-Éric Pin, Christophe Reutenauer |
| 2019 | A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. Alina Ene, Huy L. Nguyen |
| 2019 | A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. Bingkai Lin |
| 2019 | A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round. Alex B. Grilo |
| 2019 | A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, Sumedha Uniyal |
| 2019 | A Type System for Interactive JSON Schema Inference (Extended Abstract). Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani |
| 2019 | AC Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal |
| 2019 | Algorithmically Efficient Syntactic Characterization of Possibility Domains. Josep Díaz, Lefteris M. Kirousis, Sofia Kokonezi, John Livieratos |
| 2019 | Algorithms and Hardness for Diameter in Dynamic Graphs. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein |
| 2019 | Amplification with One NP Oracle Query. Thomas Watson |
| 2019 | An Improved FPTAS for 0-1 Knapsack. Ce Jin |
| 2019 | Approximate Counting of k-Paths: Deterministic and in Polynomial Space. Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi |
| 2019 | Approximately Good and Modern Matchings (Invited Talk). Ola Svensson |
| 2019 | Approximation Algorithms for Min-Distance Problems. Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu |
| 2019 | Approximations of Isomorphism and Logics with Linear-Algebraic Operators. Anuj Dawar, Erich Grädel, Wied Pakusa |
| 2019 | Auction Design under Interdependent Values (Invited Talk). Michal Feldman |
| 2019 | Automata Learning and Galois Connections (Invited Talk). Frits W. Vaandrager |
| 2019 | Automatic Semigroups vs Automaton Semigroups. Matthieu Picantin |
| 2019 | Beating Fredman-Komlós for Perfect k-Hashing. Venkatesan Guruswami, Andrii Riazanov |
| 2019 | Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman |
| 2019 | Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu |
| 2019 | Boundedness of Conjunctive Regular Path Queries. Pablo Barceló, Diego Figueira, Miguel Romero |
| 2019 | Büchi Objectives in Countable MDPs. Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke |
| 2019 | Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. Kyriakos Axiotis, Christos Tzamos |
| 2019 | Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis |
| 2019 | Completeness of Graphical Languages for Mixed States Quantum Mechanics. Titouan Carette, Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart |
| 2019 | Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi |
| 2019 | Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis |
| 2019 | Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set. Nabil H. Mustafa |
| 2019 | Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. Andreas Björklund, Ryan Williams |
| 2019 | Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph. Chaoping Xing, Chen Yuan |
| 2019 | Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. Venkatesan Guruswami, Lingfei Jin, Chaoping Xing |
| 2019 | Counting Answers to Existential Questions. Holger Dell, Marc Roth, Philip Wellnitz |
| 2019 | Covering Metric Spaces by Few Trees. Yair Bartal, Nova Fandina, Ofer Neiman |
| 2019 | Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi |
| 2019 | Covert Computation in Self-Assembled Circuits. Angel A. Cantu, Austin Luchsinger, Robert Schweller, Tim Wylie |
| 2019 | Decomposition of Map Graphs with Applications. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi |
| 2019 | Determinant Equivalence Test over Finite Fields and over Q. Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha |
| 2019 | Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. Noga Alon, Shiri Chechik, Sarel Cohen |
| 2019 | Deterministic Leader Election in Programmable Matter. Yuval Emek, Shay Kutten, Ron Lavi, William K. Moses Jr. |
| 2019 | Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp. Christof Löding, Anton Pirogov |
| 2019 | Dichotomy for Symmetric Boolean PCSPs. Miron Ficak, Marcin Kozik, Miroslav Olsák, Szymon Stankiewicz |
| 2019 | Differential Logical Relations, Part I: The Simply-Typed Case. Ugo Dal Lago, Francesco Gavazzo, Akira Yoshimizu |
| 2019 | Dismantlability, Connectedness, and Mixing in Relational Structures. Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, Benoît Larose |
| 2019 | Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication. Mohsen Ghaffari, Ali Sayyadi |
| 2019 | Distributed Detection of Cliques in Dynamic Networks. Matthias Bonne, Keren Censor-Hillel |
| 2019 | Distributed Reconfiguration of Maximal Independent Sets. Keren Censor-Hillel, Mikaël Rabie |
| 2019 | Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps. Mikkel Thorup, Or Zamir, Uri Zwick |
| 2019 | Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation. William Kuszmaul |
| 2019 | Energy Consumption of Group Search on a Line. Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, Sunil M. Shende |
| 2019 | Equivalence of Finite-Valued Streaming String Transducers Is Decidable. Anca Muscholl, Gabriele Puppis |
| 2019 | Estimating the Frequency of a Clustered Signal. Xue Chen, Eric Price |
| 2019 | Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication. Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone |
| 2019 | Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. Siddharth Gupta, Adrian Kosowski, Laurent Viennot |
| 2019 | Exploration of High-Dimensional Grids by Finite Automata. Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov |
| 2019 | FO = FO Marie Fortin |
| 2019 | Faster Algorithms for All Pairs Non-Decreasing Paths Problem. Ran Duan, Ce Jin, Hongxun Wu |
| 2019 | Faster Algorithms for All-Pairs Bounded Min-Cuts. Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel Wolleb-Graf |
| 2019 | Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs. Guillaume Ducoffe |
| 2019 | Finding Tutte Paths in Linear Time. Therese Biedl, Philipp Kindermann |
| 2019 | Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. Amir Abboud |
| 2019 | Fixed Point Computation Problems and Facets of Complexity (Invited Talk). Mihalis Yannakakis |
| 2019 | From Nondeterministic to Multi-Head Deterministic Finite-State Transducers. Martin Raszyk, David A. Basin, Dmitriy Traytel |
| 2019 | From Normal Functors to Logarithmic Space Queries. Lê Thành Dung Nguyên, Cécilia Pradic |
| 2019 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2019 | Geometric Multicut. Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote |
| 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 | How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs? Eleni C. Akrida, George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis, Viktor Zamaraev |
| 2019 | Improvements in Quantum SDP-Solving with Applications. Joran van Apeldoorn, András Gilyén |
| 2019 | Independent Sets in Vertex-Arrival Streams. Graham Cormode, Jacques Dark, Christian Konrad |
| 2019 | Information-Theoretic and Algorithmic Thresholds for Group Testing. Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick |
| 2019 | Local Search Breaks 1.75 for Graph Balancing. Klaus Jansen, Lars Rohwedder |
| 2019 | Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. Alexandr Andoni, Clifford Stein, Peilin Zhong |
| 2019 | Lower Bounds for Multiplication via Network Coding. Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen |
| 2019 | Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff |
| 2019 | Maintaining Perfect Matchings at Low Cost. Jannik Matuschke, Ulrike Schmidt-Kraepelin, José Verschae |
| 2019 | Matroid Coflow Scheduling. Sungjin Im, Benjamin Moseley, Kirk Pruhs, Manish Purohit |
| 2019 | Minimizing GFG Transition-Based Automata. Bader Abu Radi, Orna Kupferman |
| 2019 | Monadic Decomposability of Regular Relations. Pablo Barceló, Chih-Duo Hong, Xuan Bach Le, Anthony W. Lin, Reino Niskanen |
| 2019 | Multi-Round Cooperative Search Games with Multiple Players. Amos Korman, Yoav Rodeh |
| 2019 | Near-Linear Time Algorithm for n-fold ILPs via Color Coding. Klaus Jansen, Alexandra Lassota, Lars Rohwedder |
| 2019 | Network Investment Games with Wardrop Followers. Daniel Schmand, Marc Schröder, Alexander Skopalik |
| 2019 | Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol. Frederik Mallmann-Trenn, Yannic Maus, Dominik Pajak |
| 2019 | Non-Clairvoyant Precedence Constrained Scheduling. Naveen Garg, Anupam Gupta, Amit Kumar, Sahil Singla |
| 2019 | On Adaptive Algorithms for Maximum Matching. Falko Hegerfeld, Stefan Kratsch |
| 2019 | On All Things Star-Free. Thomas Place, Marc Zeitoun |
| 2019 | On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies. Ioannis Caragiannis, Angelo Fanelli |
| 2019 | On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. Julian Dörfler, Christian Ikenmeyer, Greta Panova |
| 2019 | On Reachability Problems for Low-Dimensional Matrix Semigroups. Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, James Worrell |
| 2019 | On the Complexity of Local Graph Transformations. Christian Scheideler, Alexander Setzer |
| 2019 | On the Complexity of String Matching for Graphs. Massimo Equi, Roberto Grossi, Veli Mäkinen, Alexandru I. Tomescu |
| 2019 | On the Complexity of Value Iteration. Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez, Mahsa Shirmohammadi |
| 2019 | On the Fixed-Parameter Tractability of Capacitated Clustering. Vincent Cohen-Addad, Jason Li |
| 2019 | Optimal Regular Expressions for Permutations. Antonio Molina Lovett, Jeffrey O. Shallit |
| 2019 | Optimal Short Cycle Decomposition in Almost Linear Time. Merav Parter, Eylon Yogev |
| 2019 | Optimal Strategies for Patrolling Fences. Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister |
| 2019 | Path Contraction Faster Than 2 Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale |
| 2019 | Periodic Bandits and Wireless Network Selection. Shunhao Oh, Anuja Meetoo Appavoo, Seth Gilbert |
| 2019 | Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader. Dariusz R. Kowalski, Miguel A. Mosteiro |
| 2019 | Polynomially Ambiguous Probabilistic Automata on Restricted Languages. Paul C. Bell |
| 2019 | Quantum Chebyshev's Inequality and Applications. Yassine Hamoudi, Frédéric Magniez |
| 2019 | Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, Xiaodi Wu |
| 2019 | Query-To-Communication Lifting for BPP Using Inner Product. Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi |
| 2019 | Querying a Matrix Through Matrix-Vector Products. Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang |
| 2019 | Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. Thomas Sauerwald, Luca Zanetti |
| 2019 | Randomness and Intractability in Kolmogorov Complexity. Igor Carboni Oliveira |
| 2019 | Reachability for Branching Concurrent Stochastic Games. Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis |
| 2019 | Restricted Max-Min Allocation: Approximation and Integrality Gap. Siu-Wing Cheng, Yuchen Mao |
| 2019 | Retracting Graphs to Cycles. Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram |
| 2019 | Robust Communication-Optimal Distributed Clustering Algorithms. Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff |
| 2019 | Satisfiability Thresholds for Regular Occupation Problems. Konstantinos Panagiotou, Matija Pasch |
| 2019 | Scalable and Jointly Differentially Private Packing. Zhiyi Huang, Xue Zhu |
| 2019 | Scheduling to Approximate Minimization Objectives on Identical Machines. Benjamin Moseley |
| 2019 | Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. David P. Woodruff, Guang Yang |
| 2019 | Sequentiality of String-to-Context Transducers. Pierre-Alain Reynier, Didier Villevalois |
| 2019 | Short Proofs Are Hard to Find. Ian Mertz, Toniann Pitassi, Yuanhao Wei |
| 2019 | Sign-Rank Can Increase Under Intersection. Mark Bun, Nikhil S. Mande, Justin Thaler |
| 2019 | Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE. Laura Ciobanu, Murray Elder |
| 2019 | Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. Andreas Björklund, Petteri Kaski, Ryan Williams |
| 2019 | Stochastic Graph Exploration. Aris Anagnostopoulos, Ilan Reuven Cohen, Stefano Leonardi, Jakub Lacki |
| 2019 | Stochastic Online Metric Matching. Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc |
| 2019 | String-to-String Interpretations With Polynomial-Size Output. Mikolaj Bojanczyk, Sandra Kiefer, Nathan Lhote |
| 2019 | Sum-Of-Squares Bounds via Boolean Function Analysis. Adam Kurpisz |
| 2019 | Symmetry and Similarity (Invited Talk). Martin Grohe |
| 2019 | Temporal Cliques Admit Sparse Spanners. Arnaud Casteigts, Joseph G. Peters, Jason Schoeters |
| 2019 | Termination of Linear Loops over the Integers. Mehran Hosseini, Joël Ouaknine, James Worrell |
| 2019 | Testing the Complexity of a Valued CSP Language. Vladimir Kolmogorov |
| 2019 | The Arboricity Captures the Complexity of Sampling Edges. Talya Eden, Dana Ron, Will Rosenbaum |
| 2019 | The Complexity of Approximating the Matching Polynomial in the Complex Plane. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic |
| 2019 | The Hairy Ball Problem is PPAD-Complete. Paul W. Goldberg, Alexandros Hollender |
| 2019 | The Minimum Cost Query Problem on Matroids with Uncertainty Areas. Arturo Merino, José A. Soto |
| 2019 | The Norms of Graph Spanners. Eden Chlamtác, Michael Dinitz, Thomas Robinson |
| 2019 | The Parametric Complexity of Lossy Counter Machines. Sylvain Schmitz |
| 2019 | The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. Shantanav Chakraborty, András Gilyén, Stacey Jeffery |
| 2019 | The Satisfiability Threshold for Non-Uniform Random 2-SAT. Tobias Friedrich, Ralf Rothenberger |
| 2019 | Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein |
| 2019 | Tight Bounds for Online Weighted Tree Augmentation. Joseph (Seffi) Naor, Seeun William Umboh, David P. Williamson |
| 2019 | Tight FPT Approximations for k-Median and k-Means. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, Jason Li |
| 2019 | Toward a Dichotomy for Approximation of H-Coloring. Akbar Rafiey, Arash Rafiey, Thiago Santos |
| 2019 | Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint. Alina Ene, Huy L. Nguyen |
| 2019 | Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi |
| 2019 | Two Moves per Time Step Make a Difference. Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, Jakob T. Spooner |
| 2019 | Two New Results About Quantum Exact Learning. Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf |
| 2019 | Two Party Distribution Testing: Communication and Security. Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki |
| 2019 | Unique End of Potential Line. John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani |
| 2019 | Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth |
| 2019 | Varieties of Data Languages. Henning Urbat, Stefan Milius |
| 2019 | When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time. Sepehr Assadi, Shay Solomon |