STACS 2023 March 7-9, 2023, Hamburg, Germany

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)



Petra Berenbrink and Patricia Bouyer and Anuj Dawar and Mamadou Moustapha Kanté (Eds.)
ISBN 978-3-95977-266-2, LIPICS Vol. 254 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 18 MB)
Search Publication Server

Authors
  • Aichinger, Erhard
  • Akhmedov, Maxim
  • Alexandru, Cezar-Mihail
  • Amanatidis, Georgios
  • Amarilli, Antoine
  • Babenko, Maxim
  • Baumann, Pascal
  • Bausch, Johannes
  • Berenbrink, Petra
  • Bergougnoux, Benjamin
  • Bergé, Pierre
  • Bläser, Markus
  • Bläsius, Thomas
  • Bojikian, Narek
  • Bonnet, Édouard
  • Bouyer, Patricia
  • Bshouty, Nader H.
  • Cairo, Massimo
  • Capelli, Florent
  • Carayol, Arnaud
  • Chawin, Dror
  • Chede, Sravanthi
  • Chekan, Vera
  • Chillara, Suryajith
  • Chrobak, Marek
  • Clemente, Lorenzo
  • Dawar, Anuj
  • Dong, Ruiwen
  • Donten-Bury, Maria
  • Duchon, Philippe
  • Dufay, Marc
  • Dvořák, Pavel
  • Dvořák, Zdeněk
  • Déprés, Hugues
  • El Maalouly, Nicolas
  • Enright, Jessica
  • Filiot, Emmanuel
  • Friedrich, Tobias
  • Gharibian, Sevag
  • Giocanti, Ugo
  • Gledel, Valentin
  • Green Larsen, Kasper
  • Grichener, Coral
  • Grünbacher, Simon
  • Gąsieniec, Leszek
  • Haney, Samuel
  • Haviv, Ishay
  • Heeger, Klaus
  • Hegerfeld, Falko
  • Henzinger, Monika
  • Huang, Shengyu
  • Jaakkola, Reijo
  • Jecker, Ismaël
  • Kanté, Mamadou Moustapha
  • Kaplan, Haim
  • Katzmann, Maximilian
  • Khan, Shahbaz
  • Kleer, Pieter
  • Koana, Tomohiro
  • Koechlin, Florent
  • Komarath, Balagopal
  • Konrad, Christian
  • Korhonen, Tuukka
  • Kratsch, Stefan
  • Kumar, Anant
  • Kuusisto, Antti
  • Le Gall, François
  • Lehtinen, Karoliina
  • Li, Haohong
  • Liaee, Mehraneh
  • Liu, Chih-Hung
  • Los, Dimitrios
  • Lévêque, Benjamin
  • Löding, Christof
  • Majewski, Konrad
  • Mathieu, Claire
  • Mayer, Hendrik
  • Mazowiecki, Filip
  • Meeks, Kitty
  • Meyer, Roland
  • Mishra, Suchismita
  • Miyamoto, Masayuki
  • Modanese, Augusto
  • Molter, Hendrik
  • Monet, Mikaël
  • Møller Høgsgaard, Mikael
  • Mühlenthaler, Moritz
  • Naidu, Kheeran K.
  • Nandakumar, Satyadev
  • Nederlof, Jesper
  • Neumann, Stefan
  • Nicaud, Cyril
  • Nichterlein, André
  • Niedermeier, Rolf
  • Nishimura, Harumichi
  • Nova Fandina, Ora
  • Ohsaka, Naoto
  • Oijid, Nacim
  • Olkowski, Jędrzej
  • Ossona de Mendez, Patrice
  • Panigrahi, Debmalya
  • Paperman, Charles
  • Pilipczuk, Michał
  • Pulari, Subin
  • Rajaraman, Rajmohan
  • Richomme, Gwenaël
  • Rizzi, Romeo
  • Rosenfeld, Matthieu
  • Rotenberg, Eva
  • Rutschmann, Daniel
  • Rychlicki, Mateusz
  • Räcke, Harald
  • Sadeh, Yaniv
  • Salvati, Sylvain
  • Sauerwald, Thomas
  • Schmid, Stefan
  • Schmidt, Sebastian
  • Sethia, Aditi
  • Shpilka, Amir
  • Shringi, Devansh
  • Shukla, Anil
  • Sokołowski, Marek
  • Soyez-Martin, Claire
  • Spirakis, Paul G.
  • Stachowiak, Grzegorz
  • Stephan, Daniel
  • Steward, Arun
  • Strozecki, Yann
  • Sundaram, Ravi
  • Suzan, Thomas
  • Thomassé, Stéphan
  • Tomescu, Alexandru I.
  • Vardi, Moshe Y.
  • Vilander, Miikka
  • Watrigant, Rémi
  • Watson, James D.
  • Winter, Sarah
  • Węgrzycki, Karol
  • Xia, Ge
  • Young, Neal E.
  • Zetzsche, Georg
  • Zhou, Hang
  • Zirondelli, Elia C.
  • Zschoche, Philipp
  • Zych-Pawlewicz, Anna
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Berenbrink, Petra ; Bouyer, Patricia ; Dawar, Anuj ; Kanté, Mamadou Moustapha

    Abstract | Document (670 KB) | BibTeX

    A Brief History of History-Determinism (Invited Talk)
    Authors: Lehtinen, Karoliina

    Abstract | Document (397 KB) | BibTeX

    Amortised Analysis of Dynamic Data Structures (Invited Talk)
    Authors: Rotenberg, Eva

    Abstract | Document (401 KB) | BibTeX

    Logical Algorithmics: From Theory to Practice (Invited Talk)
    Authors: Vardi, Moshe Y.

    Abstract | Document (385 KB) | BibTeX

    The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term
    Authors: Aichinger, Erhard ; Grünbacher, Simon

    Abstract | Document (782 KB) | BibTeX

    Packing Odd Walks and Trails in Multiterminal Networks
    Authors: Akhmedov, Maxim ; Babenko, Maxim

    Abstract | Document (910 KB) | BibTeX

    Improved Weighted Matching in the Sliding Window Model
    Authors: Alexandru, Cezar-Mihail ; Dvořák, Pavel ; Konrad, Christian ; Naidu, Kheeran K.

    Abstract | Document (1,014 KB) | BibTeX

    Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals
    Authors: Amanatidis, Georgios ; Kleer, Pieter

    Abstract | Document (789 KB) | BibTeX

    Enumerating Regular Languages with Bounded Delay
    Authors: Amarilli, Antoine ; Monet, Mikaël

    Abstract | Document (821 KB) | BibTeX

    Regular Separability in Büchi VASS
    Authors: Baumann, Pascal ; Meyer, Roland ; Zetzsche, Georg

    Abstract | Document (933 KB) | BibTeX

    Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
    Authors: Bergé, Pierre ; Bonnet, Édouard ; Déprés, Hugues ; Watrigant, Rémi

    Abstract | Document (869 KB) | BibTeX

    Tight Lower Bounds for Problems Parameterized by Rank-Width
    Authors: Bergougnoux, Benjamin ; Korhonen, Tuukka ; Nederlof, Jesper

    Abstract | Document (1,217 KB) | BibTeX

    On the Multilinear Complexity of Associative Algebras
    Authors: Bläser, Markus ; Mayer, Hendrik ; Shringi, Devansh

    Abstract | Document (786 KB) | BibTeX

    Strongly Hyperbolic Unit Disk Graphs
    Authors: Bläsius, Thomas ; Friedrich, Tobias ; Katzmann, Maximilian ; Stephan, Daniel

    Abstract | Document (1,146 KB) | BibTeX

    Tight Bounds for Connectivity Problems Parameterized by Cutwidth
    Authors: Bojikian, Narek ; Chekan, Vera ; Hegerfeld, Falko ; Kratsch, Stefan

    Abstract | Document (833 KB) | BibTeX

    Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication
    Authors: Bonnet, Édouard ; Giocanti, Ugo ; Ossona de Mendez, Patrice ; Thomassé, Stéphan

    Abstract | Document (903 KB) | BibTeX

    Non-Adaptive Proper Learning Polynomials
    Authors: Bshouty, Nader H.

    Abstract | Document (758 KB) | BibTeX

    Cut Paths and Their Remainder Structure, with Applications
    Authors: Cairo, Massimo ; Khan, Shahbaz ; Rizzi, Romeo ; Schmidt, Sebastian ; Tomescu, Alexandru I. ; Zirondelli, Elia C.

    Abstract | Document (968 KB) | BibTeX

    Geometric Amortization of Enumeration Algorithms
    Authors: Capelli, Florent ; Strozecki, Yann

    Abstract | Document (909 KB) | BibTeX

    One Drop of Non-Determinism in a Random Deterministic Automaton
    Authors: Carayol, Arnaud ; Duchon, Philippe ; Koechlin, Florent ; Nicaud, Cyril

    Abstract | Document (664 KB) | BibTeX

    Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
    Authors: Chawin, Dror ; Haviv, Ishay

    Abstract | Document (685 KB) | BibTeX

    Extending Merge Resolution to a Family of QBF-Proof Systems
    Authors: Chede, Sravanthi ; Shukla, Anil

    Abstract | Document (1,262 KB) | BibTeX

    On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
    Authors: Chillara, Suryajith ; Grichener, Coral ; Shpilka, Amir

    Abstract | Document (841 KB) | BibTeX

    Online Paging with Heterogeneous Cache Slots
    Authors: Chrobak, Marek ; Haney, Samuel ; Liaee, Mehraneh ; Panigrahi, Debmalya ; Rajaraman, Rajmohan ; Sundaram, Ravi ; Young, Neal E.

    Abstract | Document (1,621 KB) | BibTeX

    On Rational Recursive Sequences
    Authors: Clemente, Lorenzo ; Donten-Bury, Maria ; Mazowiecki, Filip ; Pilipczuk, Michał

    Abstract | Document (1,075 KB) | BibTeX

    Semigroup Intersection Problems in the Heisenberg Groups
    Authors: Dong, Ruiwen

    Abstract | Document (952 KB) | BibTeX

    Solving Homogeneous Linear Equations over Polynomial Semirings
    Authors: Dong, Ruiwen

    Abstract | Document (794 KB) | BibTeX

    An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees
    Authors: Dufay, Marc ; Mathieu, Claire ; Zhou, Hang

    Abstract | Document (829 KB) | BibTeX

    Representation of Short Distances in Structurally Sparse Graphs
    Authors: Dvořák, Zdeněk

    Abstract | Document (763 KB) | BibTeX

    Exact Matching: Algorithms and Related Problems
    Authors: El Maalouly, Nicolas

    Abstract | Document (848 KB) | BibTeX

    Counting Temporal Paths
    Authors: Enright, Jessica ; Meeks, Kitty ; Molter, Hendrik

    Abstract | Document (824 KB) | BibTeX

    Barriers for Faster Dimensionality Reduction
    Authors: Nova Fandina, Ora ; Møller Høgsgaard, Mikael ; Green Larsen, Kasper

    Abstract | Document (745 KB) | BibTeX

    A Regular and Complete Notion of Delay for Streaming String Transducers
    Authors: Filiot, Emmanuel ; Jecker, Ismaël ; Löding, Christof ; Winter, Sarah

    Abstract | Document (852 KB) | BibTeX

    New Clocks, Optimal Line Formation and Self-Replication Population Protocols
    Authors: Gąsieniec, Leszek ; Spirakis, Paul G. ; Stachowiak, Grzegorz

    Abstract | Document (2,114 KB) | BibTeX

    Avoidance Games Are PSPACE-Complete
    Authors: Gledel, Valentin ; Oijid, Nacim

    Abstract | Document (811 KB) | BibTeX

    Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
    Authors: Heeger, Klaus ; Nichterlein, André ; Niedermeier, Rolf

    Abstract | Document (892 KB) | BibTeX

    Dynamic Maintenance of Monotone Dynamic Programs and Applications
    Authors: Henzinger, Monika ; Neumann, Stefan ; Räcke, Harald ; Schmid, Stefan

    Abstract | Document (852 KB) | BibTeX

    Approximate Selection with Unreliable Comparisons in Optimal Expected Time
    Authors: Huang, Shengyu ; Liu, Chih-Hung ; Rutschmann, Daniel

    Abstract | Document (882 KB) | BibTeX

    Relating Description Complexity to Entropy
    Authors: Jaakkola, Reijo ; Kuusisto, Antti ; Vilander, Miikka

    Abstract | Document (814 KB) | BibTeX

    Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
    Authors: Koana, Tomohiro

    Abstract | Document (897 KB) | BibTeX

    Finding and Counting Patterns in Sparse Graphs
    Authors: Komarath, Balagopal ; Kumar, Anant ; Mishra, Suchismita ; Sethia, Aditi

    Abstract | Document (735 KB) | BibTeX

    Maximum Matching via Maximal Matching Queries
    Authors: Konrad, Christian ; Naidu, Kheeran K. ; Steward, Arun

    Abstract | Document (855 KB) | BibTeX

    Distributed Quantum Interactive Proofs
    Authors: Le Gall, François ; Miyamoto, Masayuki ; Nishimura, Harumichi

    Abstract | Document (869 KB) | BibTeX

    Reconfiguration of Digraph Homomorphisms
    Authors: Lévêque, Benjamin ; Mühlenthaler, Moritz ; Suzan, Thomas

    Abstract | Document (906 KB) | BibTeX

    An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance
    Authors: Li, Haohong ; Xia, Ge

    Abstract | Document (720 KB) | BibTeX

    Tight Bounds for Repeated Balls-Into-Bins
    Authors: Los, Dimitrios ; Sauerwald, Thomas

    Abstract | Document (980 KB) | BibTeX

    Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number
    Authors: Majewski, Konrad ; Pilipczuk, Michał ; Sokołowski, Marek

    Abstract | Document (997 KB) | BibTeX

    Sublinear-Time Probabilistic Cellular Automata
    Authors: Modanese, Augusto

    Abstract | Document (902 KB) | BibTeX

    Real Numbers Equally Compressible in Every Base
    Authors: Nandakumar, Satyadev ; Pulari, Subin

    Abstract | Document (820 KB) | BibTeX

    Gap Preserving Reductions Between Reconfiguration Problems
    Authors: Ohsaka, Naoto

    Abstract | Document (1,051 KB) | BibTeX

    Dynamic Data Structures for Parameterized String Problems
    Authors: Olkowski, Jędrzej ; Pilipczuk, Michał ; Rychlicki, Mateusz ; Węgrzycki, Karol ; Zych-Pawlewicz, Anna

    Abstract | Document (1,024 KB) | BibTeX

    An Algebraic Approach to Vectorial Programs
    Authors: Paperman, Charles ; Salvati, Sylvain ; Soyez-Martin, Claire

    Abstract | Document (1,017 KB) | BibTeX

    Reconstructing Words Using Queries on Subwords or Factors
    Authors: Richomme, Gwenaël ; Rosenfeld, Matthieu

    Abstract | Document (729 KB) | BibTeX

    Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm
    Authors: Sadeh, Yaniv ; Kaplan, Haim

    Abstract | Document (995 KB) | BibTeX

    The Complexity of Translationally Invariant Problems Beyond Ground State Energies
    Authors: Watson, James D. ; Bausch, Johannes ; Gharibian, Sevag

    Abstract | Document (947 KB) | BibTeX

    Restless Temporal Path Parameterized Above Lower Bounds
    Authors: Zschoche, Philipp

    Abstract | Document (794 KB) | BibTeX

    		  



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