Portal - ICALP 2019

ICALP 2019	July 9-12, 2019, Patras, Greece
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi (Eds.)
ISBN 978-3-95977-109-2, LIPICS Vol. 132	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 74 MB)
Search Publication Server

Authors

Anagnostopoulos, Aris

Ancona, Bertie

Andoni, Alexandr

Appavoo, Anuja Meetoo

Arunachalam, Srinivasan

Assadi, Sepehr

Awasthi, Pranjal

Axiotis, Kyriakos

Baazizi, Mohamed-Amine

Baier, Christel

Bakshi, Ainesh

Balaji, Nikhil

Balcan, Maria-Florina

Brandão, Fernando G. S. L.

Chakraborty, Shantanav

Chakraborty, Sourav

Chalopin, Jérémie

Chattopadhyay, Arkadev

Chatzigiannakis, Ioannis

Freksen, Casper Benjamin

Georgiou, Konstantinos

Guruswami, Venkatesan

Haeupler, Bernhard

Hahn-Klimroth, Max

Hambardzumyan, Lianna

Hollender, Alexandros

Italiano, Giuseppe F.

Mallmann-Trenn, Frederik

Melissourgos, Themistoklis

Molina Lovett, Antonio

Moran, Shay

Moseley, Benjamin

Moses Jr., William K.

Mosteiro, Miguel A.

Muscholl, Anca

Mustafa, Nabil H.

Myrisiotis, Dimitrios

Mäkinen, Veli

Naor, Joseph (Seffi)

Narayanan, Lata

Natarajan Ramamoorthy, Sivaramakrishnan

Neiman, Ofer

Nguyen, Huy L.

Nguyen, Lê Thành Dung

Nikoletseas, Sotiris

Niskanen, Reino

Nosatzki, Negev Shekel

Novotný, Petr

Oh, Shunhao

Oliveira, Igor Carboni

Panagiotou, Konstantinos

Raptopoulos, Christoforos

Raszyk, Martin

Reutenauer, Christophe

Reynier, Pierre-Alain

Saptharishi, Ramprasad

Scheideler, Christian

Schmand, Daniel

Schmid, Markus L.

Schmidt-Kraepelin, Ulrike

Tomescu, Alexandru I.

Williams, Virginia Vassilevska

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Baier, Christel ; Chatzigiannakis, Ioannis ; Flocchini, Paola ; Leonardi, Stefano

Abstract | Document (434 KB) | BibTeX

Auction Design under Interdependent Values (Invited Talk)

Authors: Feldman, Michal

Abstract | Document (199 KB) | BibTeX

Symmetry and Similarity (Invited Talk)

Authors: Grohe, Martin

Abstract | Document (181 KB) | BibTeX

Approximately Good and Modern Matchings (Invited Talk)

Authors: Svensson, Ola

Abstract | Document (177 KB) | BibTeX

Automata Learning and Galois Connections (Invited Talk)

Authors: Vaandrager, Frits

Abstract | Document (182 KB) | BibTeX

Fixed Point Computation Problems and Facets of Complexity (Invited Talk)

Authors: Yannakakis, Mihalis

Abstract | Document (173 KB) | BibTeX

Complexity-Theoretic Limitations on Blind Delegated Quantum Computation

Authors: Aaronson, Scott ; Cojocaru, Alexandru ; Gheorghiu, Alexandru ; Kashefi, Elham

Abstract | Document (577 KB) | BibTeX

Faster Algorithms for All-Pairs Bounded Min-Cuts

Authors: Abboud, Amir ; Georgiadis, Loukas ; Italiano, Giuseppe F. ; Krauthgamer, Robert ; Parotsidis, Nikos ; Trabelsi, Ohad ; Uznanski, Przemyslaw ; Wolleb-Graf, Daniel

Abstract | Document (629 KB) | BibTeX

Fine-Grained Reductions and Quantum Speedups for Dynamic Programming

Authors: Abboud, Amir

Abstract | Document (467 KB) | BibTeX

Geometric Multicut

Authors: Abrahamsen, Mikkel ; Giannopoulos, Panos ; Löffler, Maarten ; Rote, Günter

Abstract | Document (633 KB) | BibTeX

Lower Bounds for Multiplication via Network Coding

Authors: Afshani, Peyman ; Freksen, Casper Benjamin ; Kamma, Lior ; Larsen, Kasper Green

Abstract | Document (511 KB) | BibTeX

Path Contraction Faster Than 2^n

Authors: Agrawal, Akanksha ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Tale, Prafullkumar

Abstract | Document (5,696 KB) | BibTeX

Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles

Authors: Alon, Noga ; Chechik, Shiri ; Cohen, Sarel

Abstract | Document (554 KB) | BibTeX

Algorithms and Hardness for Diameter in Dynamic Graphs

Authors: Ancona, Bertie ; Henzinger, Monika ; Roditty, Liam ; Williams, Virginia Vassilevska ; Wein, Nicole

Abstract | Document (515 KB) | BibTeX

Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity

Authors: Andoni, Alexandr ; Stein, Clifford ; Zhong, Peilin

Abstract | Document (540 KB) | BibTeX

Two Party Distribution Testing: Communication and Security

Authors: Andoni, Alexandr ; Malkin, Tal ; Nosatzki, Negev Shekel

Abstract | Document (581 KB) | BibTeX

Two New Results About Quantum Exact Learning

Authors: Arunachalam, Srinivasan ; Chakraborty, Sourav ; Lee, Troy ; Paraashar, Manaswi ; de Wolf, Ronald

Abstract | Document (531 KB) | BibTeX

When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time

Authors: Assadi, Sepehr ; Solomon, Shay

Abstract | Document (566 KB) | BibTeX

Robust Communication-Optimal Distributed Clustering Algorithms

Authors: Awasthi, Pranjal ; Bakshi, Ainesh ; Balcan, Maria-Florina ; White, Colin ; Woodruff, David P.

Abstract | Document (542 KB) | BibTeX

Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms

Authors: Axiotis, Kyriakos ; Tzamos, Christos

Abstract | Document (531 KB) | BibTeX

Covering Metric Spaces by Few Trees

Authors: Bartal, Yair ; Fandina, Nova ; Neiman, Ofer

Abstract | Document (540 KB) | BibTeX

Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication

Authors: Bernardini, Giulia ; Gawrychowski, Pawel ; Pisanti, Nadia ; Pissis, Solon P. ; Rosone, Giovanna

Abstract | Document (626 KB) | BibTeX

The Complexity of Approximating the Matching Polynomial in the Complex Plane

Authors: Bezáková, Ivona ; Galanis, Andreas ; Goldberg, Leslie Ann ; Stefankovic, Daniel

Abstract | Document (520 KB) | BibTeX

Finding Tutte Paths in Linear Time

Authors: Biedl, Therese ; Kindermann, Philipp

Abstract | Document (895 KB) | BibTeX

Approximate Counting of k-Paths: Deterministic and in Polynomial Space

Authors: Björklund, Andreas ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (652 KB) | BibTeX

Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors

Authors: Björklund, Andreas ; Williams, Ryan

Abstract | Document (512 KB) | BibTeX

Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction

Authors: Björklund, Andreas ; Kaski, Petteri ; Williams, Ryan

Abstract | Document (442 KB) | BibTeX

Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Authors: Brandão, Fernando G. S. L. ; Kalev, Amir ; Li, Tongyang ; Lin, Cedric Yen-Yu ; Svore, Krysta M. ; Wu, Xiaodi

Abstract | Document (504 KB) | BibTeX

A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round

Authors: Grilo, Alex B.

Abstract | Document (529 KB) | BibTeX

Dismantlability, Connectedness, and Mixing in Relational Structures

Authors: Briceño, Raimundo ; Bulatov, Andrei A. ; Dalmau, Víctor ; Larose, Benoît

Abstract | Document (518 KB) | BibTeX

Sign-Rank Can Increase Under Intersection

Authors: Bun, Mark ; Mande, Nikhil S. ; Thaler, Justin

Abstract | Document (540 KB) | BibTeX

Covert Computation in Self-Assembled Circuits

Authors: Cantu, Angel A. ; Luchsinger, Austin ; Schweller, Robert ; Wylie, Tim

Abstract | Document (1,656 KB) | BibTeX

Randomness and Intractability in Kolmogorov Complexity

Authors: Oliveira, Igor Carboni

Abstract | Document (525 KB) | BibTeX

The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation

Authors: Chakraborty, Shantanav ; Gilyén, András ; Jeffery, Stacey

Abstract | Document (481 KB) | BibTeX

Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes

Authors: Chalopin, Jérémie ; Chepoi, Victor ; Moran, Shay ; Warmuth, Manfred K.

Abstract | Document (663 KB) | BibTeX

Query-To-Communication Lifting for BPP Using Inner Product

Authors: Chattopadhyay, Arkadev ; Filmus, Yuval ; Koroth, Sajin ; Meir, Or ; Pitassi, Toniann

Abstract | Document (450 KB) | BibTeX

Estimating the Frequency of a Clustered Signal

Authors: Chen, Xue ; Price, Eric

Abstract | Document (568 KB) | BibTeX

Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes

Authors: Cheng, Kuan ; Jin, Zhengzhong ; Li, Xin ; Wu, Ke

Abstract | Document (485 KB) | BibTeX

Restricted Max-Min Allocation: Approximation and Integrality Gap

Authors: Cheng, Siu-Wing ; Mao, Yuchen

Abstract | Document (537 KB) | BibTeX

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Authors: Cheraghchi, Mahdi ; Kabanets, Valentine ; Lu, Zhenjian ; Myrisiotis, Dimitrios

Abstract | Document (643 KB) | BibTeX

The Norms of Graph Spanners

Authors: Chlamtác, Eden ; Dinitz, Michael ; Robinson, Thomas

Abstract | Document (498 KB) | BibTeX

On the Fixed-Parameter Tractability of Capacitated Clustering

Authors: Cohen-Addad, Vincent ; Li, Jason

Abstract | Document (513 KB) | BibTeX

Tight FPT Approximations for k-Median and k-Means

Authors: Cohen-Addad, Vincent ; Gupta, Anupam ; Kumar, Amit ; Lee, Euiwoong ; Li, Jason

Abstract | Document (555 KB) | BibTeX

Information-Theoretic and Algorithmic Thresholds for Group Testing

Authors: Coja-Oghlan, Amin ; Gebhard, Oliver ; Hahn-Klimroth, Max ; Loick, Philipp

Abstract | Document (512 KB) | BibTeX

On Reachability Problems for Low-Dimensional Matrix Semigroups

Authors: Colcombet, Thomas ; Ouaknine, Joël ; Semukhin, Pavel ; Worrell, James

Abstract | Document (520 KB) | BibTeX

Independent Sets in Vertex-Arrival Streams

Authors: Cormode, Graham ; Dark, Jacques ; Konrad, Christian

Abstract | Document (549 KB) | BibTeX

Approximation Algorithms for Min-Distance Problems

Authors: Dalirrooyfard, Mina ; Williams, Virginia Vassilevska ; Vyas, Nikhil ; Wein, Nicole ; Xu, Yinzhan ; Yu, Yuancheng

Abstract | Document (519 KB) | BibTeX

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems

Authors: Dalirrooyfard, Mina ; Williams, Virginia Vassilevska ; Vyas, Nikhil ; Wein, Nicole

Abstract | Document (492 KB) | BibTeX

Faster Algorithms for All Pairs Non-Decreasing Paths Problem

Authors: Duan, Ran ; Jin, Ce ; Wu, Hongxun

Abstract | Document (514 KB) | BibTeX

Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

Authors: Ducoffe, Guillaume

Abstract | Document (544 KB) | BibTeX

Algorithmically Efficient Syntactic Characterization of Possibility Domains

Authors: Díaz, Josep ; Kirousis, Lefteris ; Kokonezi, Sofia ; Livieratos, John

Abstract | Document (451 KB) | BibTeX

On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions

Authors: Dörfler, Julian ; Ikenmeyer, Christian ; Panova, Greta

Abstract | Document (524 KB) | BibTeX

The Arboricity Captures the Complexity of Sampling Edges

Authors: Eden, Talya ; Ron, Dana ; Rosenbaum, Will

Abstract | Document (561 KB) | BibTeX

A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Authors: Ene, Alina ; Nguyen, Huy L.

Abstract | Document (535 KB) | BibTeX

Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint

Authors: Ene, Alina ; Nguyen, Huy L.

Abstract | Document (528 KB) | BibTeX

On the Complexity of String Matching for Graphs

Authors: Equi, Massimo ; Grossi, Roberto ; Mäkinen, Veli ; Tomescu, Alexandru I.

Abstract | Document (704 KB) | BibTeX

Unique End of Potential Line

Authors: Fearnley, John ; Gordon, Spencer ; Mehta, Ruta ; Savani, Rahul

Abstract | Document (489 KB) | BibTeX

Dichotomy for Symmetric Boolean PCSPs

Authors: Ficak, Miron ; Kozik, Marcin ; Olsák, Miroslav ; Stankiewicz, Szymon

Abstract | Document (442 KB) | BibTeX

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

Authors: Filmus, Yuval ; Hambardzumyan, Lianna ; Hatami, Hamed ; Hatami, Pooya ; Zuckerman, David

Abstract | Document (479 KB) | BibTeX

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (496 KB) | BibTeX

Decomposition of Map Graphs with Applications

Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (636 KB) | BibTeX

The Satisfiability Threshold for Non-Uniform Random 2-SAT

Authors: Friedrich, Tobias ; Rothenberger, Ralf

Abstract | Document (508 KB) | BibTeX

Determinant Equivalence Test over Finite Fields and over Q

Authors: Garg, Ankit ; Gupta, Nikhil ; Kayal, Neeraj ; Saha, Chandan

Abstract | Document (582 KB) | BibTeX

Non-Clairvoyant Precedence Constrained Scheduling

Authors: Garg, Naveen ; Gupta, Anupam ; Kumar, Amit ; Singla, Sahil

Abstract | Document (465 KB) | BibTeX

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Authors: Gavinsky, Dmitry ; Lee, Troy ; Santha, Miklos ; Sanyal, Swagato

Abstract | Document (602 KB) | BibTeX

The Hairy Ball Problem is PPAD-Complete

Authors: Goldberg, Paul W. ; Hollender, Alexandros

Abstract | Document (464 KB) | BibTeX

AC^0[p] Lower Bounds Against MCSP via the Coin Problem

Authors: Golovnev, Alexander ; Ilango, Rahul ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina ; Tal, Avishay

Abstract | Document (533 KB) | BibTeX

Stochastic Online Metric Matching

Authors: Gupta, Anupam ; Guruganesh, Guru ; Peng, Binghui ; Wajc, David

Abstract | Document (527 KB) | BibTeX

Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields

Authors: Guruswami, Venkatesan ; Jin, Lingfei ; Xing, Chaoping

Abstract | Document (469 KB) | BibTeX

Quantum Chebyshev's Inequality and Applications

Authors: Hamoudi, Yassine ; Magniez, Frédéric

Abstract | Document (630 KB) | BibTeX

Retracting Graphs to Cycles

Authors: Haney, Samuel ; Liaee, Mehraneh ; Maggs, Bruce M. ; Panigrahi, Debmalya ; Rajaraman, Rajmohan ; Sundaram, Ravi

Abstract | Document (560 KB) | BibTeX

On Adaptive Algorithms for Maximum Matching

Authors: Hegerfeld, Falko ; Kratsch, Stefan

Abstract | Document (608 KB) | BibTeX

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

Authors: Hrubes, Pavel ; Natarajan Ramamoorthy, Sivaramakrishnan ; Rao, Anup ; Yehudayoff, Amir

Abstract | Document (513 KB) | BibTeX

Scalable and Jointly Differentially Private Packing

Authors: Huang, Zhiyi ; Zhu, Xue

Abstract | Document (492 KB) | BibTeX

Local Search Breaks 1.75 for Graph Balancing

Authors: Jansen, Klaus ; Rohwedder, Lars

Abstract | Document (562 KB) | BibTeX

Near-Linear Time Algorithm for n-fold ILPs via Color Coding

Authors: Jansen, Klaus ; Lassota, Alexandra ; Rohwedder, Lars

Abstract | Document (501 KB) | BibTeX

An Improved FPTAS for 0-1 Knapsack

Authors: Jin, Ce

Abstract | Document (456 KB) | BibTeX

Testing the Complexity of a Valued CSP Language

Authors: Kolmogorov, Vladimir

Abstract | Document (562 KB) | BibTeX

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

Authors: Kumar, Mrinal ; Oliveira, Rafael ; Saptharishi, Ramprasad

Abstract | Document (529 KB) | BibTeX

Sum-Of-Squares Bounds via Boolean Function Analysis

Authors: Kurpisz, Adam

Abstract | Document (497 KB) | BibTeX

Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation

Authors: Kuszmaul, William

Abstract | Document (487 KB) | BibTeX

A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem

Authors: Lin, Bingkai

Abstract | Document (553 KB) | BibTeX

Maintaining Perfect Matchings at Low Cost

Authors: Matuschke, Jannik ; Schmidt-Kraepelin, Ulrike ; Verschae, José

Abstract | Document (493 KB) | BibTeX

The Minimum Cost Query Problem on Matroids with Uncertainty Areas

Authors: Merino, Arturo I. ; Soto, José A.

Abstract | Document (511 KB) | BibTeX

Short Proofs Are Hard to Find

Authors: Mertz, Ian ; Pitassi, Toniann ; Wei, Yuanhao

Abstract | Document (551 KB) | BibTeX

A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

Authors: Mizrachi, Eyal ; Schwartz, Roy ; Spoerhase, Joachim ; Uniyal, Sumedha

Abstract | Document (594 KB) | BibTeX

Scheduling to Approximate Minimization Objectives on Identical Machines

Authors: Moseley, Benjamin

Abstract | Document (521 KB) | BibTeX

Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set

Authors: Mustafa, Nabil H.

Abstract | Document (492 KB) | BibTeX

Tight Bounds for Online Weighted Tree Augmentation

Authors: Naor, Joseph (Seffi) ; Umboh, Seeun William ; Williamson, David P.

Abstract | Document (678 KB) | BibTeX

Optimal Short Cycle Decomposition in Almost Linear Time

Authors: Parter, Merav ; Yogev, Eylon

Abstract | Document (579 KB) | BibTeX

Satisfiability Thresholds for Regular Occupation Problems

Authors: Panagiotou, Konstantinos ; Pasch, Matija

Abstract | Document (488 KB) | BibTeX

Toward a Dichotomy for Approximation of H-Coloring

Authors: Rafiey, Akbar ; Rafiey, Arash ; Santos, Thiago

Abstract | Document (615 KB) | BibTeX

Beating Fredman-Komlós for Perfect k-Hashing

Authors: Guruswami, Venkatesan ; Riazanov, Andrii

Abstract | Document (484 KB) | BibTeX

Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities

Authors: Sauerwald, Thomas ; Zanetti, Luca

Abstract | Document (506 KB) | BibTeX

Querying a Matrix Through Matrix-Vector Products

Authors: Sun, Xiaoming ; Woodruff, David P. ; Yang, Guang ; Zhang, Jialin

Abstract | Document (608 KB) | BibTeX

Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps

Authors: Thorup, Mikkel ; Zamir, Or ; Zwick, Uri

Abstract | Document (454 KB) | BibTeX

Amplification with One NP Oracle Query

Authors: Watson, Thomas

Abstract | Document (536 KB) | BibTeX

Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams

Authors: Woodruff, David P. ; Yang, Guang

Abstract | Document (539 KB) | BibTeX

Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph

Authors: Xing, Chaoping ; Yuan, Chen

Abstract | Document (522 KB) | BibTeX

Improvements in Quantum SDP-Solving with Applications

Authors: van Apeldoorn, Joran ; Gilyén, András

Abstract | Document (523 KB) | BibTeX

Minimizing GFG Transition-Based Automata

Authors: Abu Radi, Bader ; Kupferman, Orna

Abstract | Document (525 KB) | BibTeX

A Type System for Interactive JSON Schema Inference (Extended Abstract)

Authors: Baazizi, Mohamed-Amine ; Colazzo, Dario ; Ghelli, Giorgio ; Sartiani, Carlo

Abstract | Document (578 KB) | BibTeX

On the Complexity of Value Iteration

Authors: Balaji, Nikhil ; Kiefer, Stefan ; Novotný, Petr ; Pérez, Guillermo A. ; Shirmohammadi, Mahsa

Abstract | Document (537 KB) | BibTeX

Monadic Decomposability of Regular Relations

Authors: Barceló, Pablo ; Hong, Chih-Duo ; Le, Xuan-Bach ; Lin, Anthony W. ; Niskanen, Reino

Abstract | Document (533 KB) | BibTeX

Boundedness of Conjunctive Regular Path Queries

Authors: Barceló, Pablo ; Figueira, Diego ; Romero, Miguel

Abstract | Document (586 KB) | BibTeX

Polynomially Ambiguous Probabilistic Automata on Restricted Languages

Authors: Bell, Paul C.

Abstract | Document (465 KB) | BibTeX

String-to-String Interpretations With Polynomial-Size Output

Authors: Bojanczyk, Mikolaj ; Kiefer, Sandra ; Lhote, Nathan

Abstract | Document (3,432 KB) | BibTeX

A Kleene Theorem for Nominal Automata

Authors: Brunet, Paul ; Silva, Alexandra

Abstract | Document (589 KB) | BibTeX

Completeness of Graphical Languages for Mixed States Quantum Mechanics

Authors: Carette, Titouan ; Jeandel, Emmanuel ; Perdrix, Simon ; Vilmart, Renaud

Abstract | Document (554 KB) | BibTeX

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

Authors: Casel, Katrin ; Day, Joel D. ; Fleischmann, Pamela ; Kociumaka, Tomasz ; Manea, Florin ; Schmid, Markus L.

Abstract | Document (617 KB) | BibTeX

Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE

Authors: Ciobanu, Laura ; Elder, Murray

Abstract | Document (607 KB) | BibTeX

Differential Logical Relations, Part I: The Simply-Typed Case

Authors: Dal Lago, Ugo ; Gavazzo, Francesco ; Yoshimizu, Akira

Abstract | Document (566 KB) | BibTeX

Approximations of Isomorphism and Logics with Linear-Algebraic Operators

Authors: Dawar, Anuj ; Grädel, Erich ; Pakusa, Wied

Abstract | Document (535 KB) | BibTeX

Counting Answers to Existential Questions

Authors: Dell, Holger ; Roth, Marc ; Wellnitz, Philip

Abstract | Document (503 KB) | BibTeX

A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games

Authors: Dorfman, Dani ; Kaplan, Haim ; Zwick, Uri

Abstract | Document (626 KB) | BibTeX

Reachability for Branching Concurrent Stochastic Games

Authors: Etessami, Kousha ; Martinov, Emanuel ; Stewart, Alistair ; Yannakakis, Mihalis

Abstract | Document (501 KB) | BibTeX

FO = FO^3 for Linear Orders with Monotone Binary Relations

Authors: Fortin, Marie

Abstract | Document (522 KB) | BibTeX

A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus

Authors: Grohe, Martin ; Kiefer, Sandra

Abstract | Document (660 KB) | BibTeX

Termination of Linear Loops over the Integers

Authors: Hosseini, Mehran ; Ouaknine, Joël ; Worrell, James

Abstract | Document (506 KB) | BibTeX

Büchi Objectives in Countable MDPs

Authors: Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa ; Totzke, Patrick

Abstract | Document (549 KB) | BibTeX

Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp

Authors: Löding, Christof ; Pirogov, Anton

Abstract | Document (565 KB) | BibTeX

Optimal Regular Expressions for Permutations

Authors: Molina Lovett, Antonio ; Shallit, Jeffrey

Abstract | Document (436 KB) | BibTeX

Equivalence of Finite-Valued Streaming String Transducers Is Decidable

Authors: Muscholl, Anca ; Puppis, Gabriele

Abstract | Document (575 KB) | BibTeX

From Normal Functors to Logarithmic Space Queries

Authors: Nguyen, Lê Thành Dung ; Pradic, Pierre

Abstract | Document (587 KB) | BibTeX

Automatic Semigroups vs Automaton Semigroups

Authors: Picantin, Matthieu

Abstract | Document (637 KB) | BibTeX

A Mahler's Theorem for Word Functions

Authors: Pin, Jean-Éric ; Reutenauer, Christophe

Abstract | Document (528 KB) | BibTeX

On All Things Star-Free

Authors: Place, Thomas ; Zeitoun, Marc

Abstract | Document (491 KB) | BibTeX

From Nondeterministic to Multi-Head Deterministic Finite-State Transducers

Authors: Raszyk, Martin ; Basin, David ; Traytel, Dmitriy

Abstract | Document (546 KB) | BibTeX

Sequentiality of String-to-Context Transducers

Authors: Reynier, Pierre-Alain ; Villevalois, Didier

Abstract | Document (648 KB) | BibTeX

The Parametric Complexity of Lossy Counter Machines

Authors: Schmitz, Sylvain

Abstract | Document (605 KB) | BibTeX

Varieties of Data Languages

Authors: Urbat, Henning ; Milius, Stefan

Abstract | Document (510 KB) | BibTeX

How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs?

Authors: Akrida, Eleni C. ; Mertzios, George B. ; Nikoletseas, Sotiris ; Raptopoulos, Christoforos ; Spirakis, Paul G. ; Zamaraev, Viktor

Abstract | Document (523 KB) | BibTeX

Distributed Detection of Cliques in Dynamic Networks

Authors: Bonne, Matthias ; Censor-Hillel, Keren

Abstract | Document (523 KB) | BibTeX

On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies

Authors: Caragiannis, Ioannis ; Fanelli, Angelo

Abstract | Document (447 KB) | BibTeX

Temporal Cliques Admit Sparse Spanners

Authors: Casteigts, Arnaud ; Peters, Joseph G. ; Schoeters, Jason

Abstract | Document (479 KB) | BibTeX

Distributed Reconfiguration of Maximal Independent Sets

Authors: Censor-Hillel, Keren ; Rabie, Mikaël

Abstract | Document (498 KB) | BibTeX

Stochastic Graph Exploration

Authors: Anagnostopoulos, Aris ; Cohen, Ilan R. ; Leonardi, Stefano ; Lacki, Jakub

Abstract | Document (535 KB) | BibTeX

Energy Consumption of Group Search on a Line

Authors: Czyzowicz, Jurek ; Georgiou, Konstantinos ; Killick, Ryan ; Kranakis, Evangelos ; Krizanc, Danny ; Lafond, Manuel ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil

Abstract | Document (591 KB) | BibTeX

Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

Authors: Deligkas, Argyrios ; Fearnley, John ; Melissourgos, Themistoklis ; Spirakis, Paul G.

Abstract | Document (670 KB) | BibTeX

Exploration of High-Dimensional Grids by Finite Automata

Authors: Dobrev, Stefan ; Narayanan, Lata ; Opatrny, Jaroslav ; Pankratov, Denis

Abstract | Document (528 KB) | BibTeX

Deterministic Leader Election in Programmable Matter

Authors: Emek, Yuval ; Kutten, Shay ; Lavi, Ron ; Moses Jr., William K.

Abstract | Document (482 KB) | BibTeX

Two Moves per Time Step Make a Difference

Authors: Erlebach, Thomas ; Kammer, Frank ; Luo, Kelin ; Sajenko, Andrej ; Spooner, Jakob T.

Abstract | Document (547 KB) | BibTeX

Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication

Authors: Ghaffari, Mohsen ; Sayyadi, Ali

Abstract | Document (499 KB) | BibTeX

Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond

Authors: Gupta, Siddharth ; Kosowski, Adrian ; Viennot, Laurent

Abstract | Document (541 KB) | BibTeX

Optimal Strategies for Patrolling Fences

Authors: Haeupler, Bernhard ; Kuhn, Fabian ; Martinsson, Anders ; Petrova, Kalina ; Pfister, Pascal

Abstract | Document (548 KB) | BibTeX

Matroid Coflow Scheduling

Authors: Im, Sungjin ; Moseley, Benjamin ; Pruhs, Kirk ; Purohit, Manish

Abstract | Document (521 KB) | BibTeX

Multi-Round Cooperative Search Games with Multiple Players

Authors: Korman, Amos ; Rodeh, Yoav

Abstract | Document (508 KB) | BibTeX

Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader

Authors: Kowalski, Dariusz R. ; Mosteiro, Miguel A.

Abstract | Document (511 KB) | BibTeX

Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol

Authors: Mallmann-Trenn, Frederik ; Maus, Yannic ; Pajak, Dominik

Abstract | Document (572 KB) | BibTeX

Periodic Bandits and Wireless Network Selection

Authors: Oh, Shunhao ; Appavoo, Anuja Meetoo ; Gilbert, Seth

Abstract | Document (2,157 KB) | BibTeX

On the Complexity of Local Graph Transformations

Authors: Scheideler, Christian ; Setzer, Alexander

Abstract | Document (525 KB) | BibTeX

Network Investment Games with Wardrop Followers

Authors: Schmand, Daniel ; Schröder, Marc ; Skopalik, Alexander

Abstract | Document (437 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)