Portal - STACS 2023

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

Bergougnoux, Benjamin

Kanté, Mamadou Moustapha

Møller Høgsgaard, Mikael

Ossona de Mendez, Patrice

Tomescu, Alexandru I.

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

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