Portal - STACS 2020

STACS 2020	March 10-13, 2020, Montpellier, France
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) Christophe Paul and Markus Bläser (Eds.)
ISBN 978-3-95977-140-5, LIPICS Vol. 154	ISSN 1868-8969

Additional Information

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

Authors

Arunachalam, Srinivasan

Farach-Colton, Martín

Salavatipour, Mohammad R.

Starikovskaya, Tatiana

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Paul, Christophe ; Bläser, Markus

Abstract | Document (1,182 KB) | BibTeX

Statistical Physics and Algorithms (Invited Talk)

Authors: Randall, Dana

Abstract | Document (315 KB) | BibTeX

Weisfeiler and Leman’s Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk)

Authors: Grohe, Martin

Abstract | Document (188 KB) | BibTeX

Computability, Complexity and Programming with Ordinary Differential Equations (Invited Talk)

Authors: Bournez, Olivier

Abstract | Document (581 KB) | BibTeX

Graphical Models: Queries, Complexity, Algorithms (Tutorial)

Authors: Cooper, Martin C. ; de Givry, Simon ; Schiex, Thomas

Abstract | Document (635 KB) | BibTeX

Inapproximability Results for Scheduling with Interval and Resource Restrictions

Authors: Maack, Marten ; Jansen, Klaus

Abstract | Document (560 KB) | BibTeX

An Automaton Group with PSPACE-Complete Word Problem

Authors: Wächter, Jan Philipp ; Weiß, Armin

Abstract | Document (645 KB) | BibTeX

A Trichotomy for Regular Trail Queries

Authors: Martens, Wim ; Niewerth, Matthias ; Trautner, Tina

Abstract | Document (567 KB) | BibTeX

Descriptive Complexity on Non-Polish Spaces

Authors: Callard, Antonin ; Hoyrup, Mathieu

Abstract | Document (498 KB) | BibTeX

NP-Completeness, Proof Systems, and Disjoint NP-Pairs

Authors: Dose, Titus ; Glaßer, Christian

Abstract | Document (529 KB) | BibTeX

String Indexing with Compressed Patterns

Authors: Bille, Philip ; Gørtz, Inge Li ; Steiner, Teresa Anna

Abstract | Document (518 KB) | BibTeX

An FPT Algorithm for Minimum Additive Spanner Problem

Authors: Kobayashi, Yusuke

Abstract | Document (648 KB) | BibTeX

New Bounds for Randomized List Update in the Paid Exchange Model

Authors: Albers, Susanne ; Janke, Maximilian

Abstract | Document (624 KB) | BibTeX

On Covering Segments with Unit Intervals

Authors: Bergren, Dan ; Eiben, Eduard ; Ganian, Robert ; Kanj, Iyad

Abstract | Document (616 KB) | BibTeX

Decidability and Periodicity of Low Complexity Tilings

Authors: Kari, Jarkko ; Moutot, Etienne

Abstract | Document (603 KB) | BibTeX

The Tandem Duplication Distance Is NP-Hard

Authors: Lafond, Manuel ; Zhu, Binhai ; Zou, Peng

Abstract | Document (523 KB) | BibTeX

Existential Length Universality

Authors: Gawrychowski, Paweł ; Lange, Martin ; Rampersad, Narad ; Shallit, Jeffrey ; Szykuła, Marek

Abstract | Document (594 KB) | BibTeX

On the Termination of Flooding

Authors: Hussak, Walter ; Trehan, Amitabh

Abstract | Document (919 KB) | BibTeX

Generalised Pattern Matching Revisited

Authors: Dudek, Bartłomiej ; Gawrychowski, Paweł ; Starikovskaya, Tatiana

Abstract | Document (664 KB) | BibTeX

Parameterized Pre-Coloring Extension and List Coloring Problems

Authors: Gutin, Gregory ; Majumdar, Diptapriyo ; Ordyniak, Sebastian ; Wahlström, Magnus

Abstract | Document (562 KB) | BibTeX

Oracle Complexity Classes and Local Measurements on Physical Hamiltonians

Authors: Gharibian, Sevag ; Piddock, Stephen ; Yirka, Justin

Abstract | Document (785 KB) | BibTeX

Secret Key Agreement from Correlated Data, with No Prior Information

Authors: Zimand, Marius

Abstract | Document (439 KB) | BibTeX

Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before

Authors: Gańczorz, Michał

Abstract | Document (649 KB) | BibTeX

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

Authors: Izumi, Taisuke ; Le Gall, François ; Magniez, Frédéric

Abstract | Document (529 KB) | BibTeX

Lower Bounds for Arithmetic Circuits via the Hankel Matrix

Authors: Fijalkow, Nathanaël ; Lagarde, Guillaume ; Ohlmann, Pierre ; Serre, Olivier

Abstract | Document (624 KB) | BibTeX

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

Authors: Bläsius, Thomas ; Fischbeck, Philipp ; Friedrich, Tobias ; Katzmann, Maximilian

Abstract | Document (725 KB) | BibTeX

Domino Problem Under Horizontal Constraints

Authors: Aubrun, Nathalie ; Esnay, Julien ; Sablik, Mathieu

Abstract | Document (528 KB) | BibTeX

Computing Maximum Matchings in Temporal Graphs

Authors: Mertzios, George B. ; Molter, Hendrik ; Niedermeier, Rolf ; Zamaraev, Viktor ; Zschoche, Philipp

Abstract | Document (576 KB) | BibTeX

Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths

Authors: Guinard, Brieuc ; Korman, Amos

Abstract | Document (494 KB) | BibTeX

Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space

Authors: Hegerfeld, Falko ; Kratsch, Stefan

Abstract | Document (658 KB) | BibTeX

Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements

Authors: Funakoshi, Mitsuru ; Pape-Lange, Julian

Abstract | Document (537 KB) | BibTeX

Maximum Matchings in Geometric Intersection Graphs

Authors: Bonnet, Édouard ; Cabello, Sergio ; Mulzer, Wolfgang

Abstract | Document (587 KB) | BibTeX

Unambiguous Separators for Tropical Tree Automata

Authors: Colcombet, Thomas ; Lombardy, Sylvain

Abstract | Document (457 KB) | BibTeX

Asymptotic Quasi-Polynomial Time Approximation Scheme for Resource Minimization for Fire Containment

Authors: Rahgoshay, Mirmahdi ; Salavatipour, Mohammad R.

Abstract | Document (494 KB) | BibTeX

Streaming Complexity of Spanning Tree Computation

Authors: Chang, Yi-Jun ; Farach-Colton, Martín ; Hsu, Tsan-Sheng ; Tsai, Meng-Tsung

Abstract | Document (557 KB) | BibTeX

Shortest Reconfiguration of Colorings Under Kempe Changes

Authors: Bonamy, Marthe ; Heinrich, Marc ; Ito, Takehiro ; Kobayashi, Yusuke ; Mizuta, Haruka ; Mühlenthaler, Moritz ; Suzuki, Akira ; Wasa, Kunihiro

Abstract | Document (697 KB) | BibTeX

Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Authors: Hols, Eva-Maria C. ; Kratsch, Stefan ; Pieterse, Astrid

Abstract | Document (633 KB) | BibTeX

Near-Optimal Complexity Bounds for Fragments of the Skolem Problem

Authors: Akshay, S. ; Balaji, Nikhil ; Murhekar, Aniket ; Varma, Rohith ; Vyas, Nikhil

Abstract | Document (626 KB) | BibTeX

Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths

Authors: Kratsch, Stefan ; Nelles, Florian

Abstract | Document (570 KB) | BibTeX

Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

Authors: Wrona, Michał

Abstract | Document (506 KB) | BibTeX

Succinct Population Protocols for Presburger Arithmetic

Authors: Blondin, Michael ; Esparza, Javier ; Genest, Blaise ; Helfrich, Martin ; Jaax, Stefan

Abstract | Document (610 KB) | BibTeX

A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem

Authors: Duraj, Lech

Abstract | Document (618 KB) | BibTeX

Fixed-Parameter Algorithms for Unsplittable Flow Cover

Authors: Cristi, Andrés ; Mari, Mathieu ; Wiese, Andreas

Abstract | Document (561 KB) | BibTeX

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

Authors: Fuhlbrück, Frank ; Köbler, Johannes ; Verbitsky, Oleg

Abstract | Document (575 KB) | BibTeX

Better Approximations for General Caching and UFP-Cover Under Resource Augmentation

Authors: Cristi, Andrés ; Wiese, Andreas

Abstract | Document (481 KB) | BibTeX

Improved Bounds on Fourier Entropy and Min-Entropy

Authors: Arunachalam, Srinivasan ; Chakraborty, Sourav ; Koucký, Michal ; Saurabh, Nitin ; de Wolf, Ronald

Abstract | Document (613 KB) | BibTeX

Information Distance Revisited

Authors: Bauwens, Bruno

Abstract | Document (436 KB) | BibTeX

On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Authors: Chillara, Suryajith

Abstract | Document (580 KB) | BibTeX

Observation and Distinction. Representing Information in Infinite Games

Authors: Berwanger, Dietmar ; Doyen, Laurent

Abstract | Document (522 KB) | BibTeX

How Fast Can You Escape a Compact Polytope?

Authors: D'Costa, Julian ; Lefaucheux, Engel ; Ouaknine, Joël ; Worrell, James

Abstract | Document (489 KB) | BibTeX

The SDP Value for Random Two-Eigenvalue CSPs

Authors: Mohanty, Sidhanth ; O'Donnell, Ryan ; Paredes, Pedro

Abstract | Document (926 KB) | BibTeX

Asymptotic Divergences and Strong Dichotomy

Authors: Huang, Xiang ; Lutz, Jack H. ; Mayordomo, Elvira ; Stull, Donald M.

Abstract | Document (530 KB) | BibTeX

Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs

Authors: Dhannya, S. M. ; Narayanaswamy, N. S.

Abstract | Document (592 KB) | BibTeX

Constant-Time Dynamic (Δ+1)-Coloring

Authors: Henzinger, Monika ; Peng, Pan

Abstract | Document (612 KB) | BibTeX

Cryptocurrency Mining Games with Economic Discount and Decreasing Rewards

Authors: Arenas, Marcelo ; Reutter, Juan ; Toussaint, Etienne ; Ugarte, Martín ; Vial, Francisco ; Vrgoč, Domagoj

Abstract | Document (517 KB) | BibTeX

Randomness and Initial Segment Complexity for Probability Measures

Authors: Nies, André ; Stephan, Frank

Abstract | Document (448 KB) | BibTeX

Computing Shrub-Depth Decompositions

Authors: Gajarský, Jakub ; Kreutzer, Stephan

Abstract | Document (692 KB) | BibTeX

Typical Sequences Revisited - Computing Width Parameters of Graphs

Authors: Bodlaender, Hans L. ; Jaffke, Lars ; Telle, Jan Arne

Abstract | Document (981 KB) | BibTeX

Grundy Coloring & Friends, Half-Graphs, Bicliques

Authors: Aboulker, Pierre ; Bonnet, Édouard ; Kim, Eun Jung ; Sikora, Florian

Abstract | Document (622 KB) | BibTeX

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

Authors: Vyas, Nikhil ; Williams, R. Ryan

Abstract | Document (592 KB) | BibTeX

Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

Authors: Torán, Jacobo ; Wörz, Florian

Abstract | Document (565 KB) | BibTeX

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

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)