PROGRAM
Days: Sunday, August 21st Monday, August 22nd Tuesday, August 23rd Wednesday, August 24th Thursday, August 25th Friday, August 26th
Sunday, August 21st
View this program: with abstractssession overviewtalk overview
Monday, August 22nd
View this program: with abstractssession overviewtalk overview
10:00-10:40Coffee Break
10:40-12:00 Session 4A
Chair:
Location: Lecture Room FH5
| 10:40 | Complexity of the Cluster Vertex Deletion problem on H-free graphs (abstract) |
| 11:05 | Exact Matching in Graphs of Bounded Independence Number (abstract) |
| 11:30 | Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters (abstract) |
10:40-12:00 Session 4B
Chair:
Location: Lecture Room FH6
| 10:40 | Regular Monoidal Languages (abstract) |
| 11:05 | A robust class of languages of 2-nested words (abstract) |
| 11:30 | On extended boundary sequences of morphic and Sturmian words (abstract) |
12:20-14:00Lunch Break
14:00-15:40 Session 5A
Chair:
Location: Lecture Room FH5
| 14:00 | Graph Similarity Based on Matrix Norms (abstract) |
| 14:25 | Approximation algorithms for covering vertices by long paths (abstract) |
| 14:50 | Reducing the Vertex Cover Number via Edge Contractions (abstract) |
| 15:15 | Conflict-free Coloring on Claw-free graphs and Interval graphs (abstract) |
14:00-15:40 Session 5B
Chair:
Location: Lecture Room FH6
| 14:00 | Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs (abstract) |
| 14:25 | Skolem Meets Schanuel (abstract) PRESENTER: Joris Nieuwveld |
| 14:50 | Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems (abstract) |
| 15:15 | On the Skolem Problem for Reversible Sequences (abstract) |
15:40-16:10Coffee Break
16:10-17:30 Session 6A
Chair:
Location: Lecture Room FH5
| 16:10 | On Upward-Planar L-Drawings of Graphs (abstract) PRESENTER: Sabine Cornelsen |
| 16:35 | Extending Partial Representations of Circle Graphs in Near-Linear Time (abstract) |
| 17:00 | RAC Drawings of Graphs with Low Degree (abstract) PRESENTER: Julia Katheder |
16:10-17:30 Session 6B
Chair:
Location: Lecture Room FH6
| 16:10 | Continuous rational functions are deterministic regular (abstract) |
| 16:35 | Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order (abstract) |
| 17:00 | Learning Deterministic Visibly Pushdown Automata under Accessible Stack (abstract) PRESENTER: Jakub Michaliszyn |
Tuesday, August 23rd
View this program: with abstractssession overviewtalk overview
10:00-10:40Coffee Break
10:40-12:00 Session 8A
Chair:
Location: Lecture Room FH5
| 10:40 | On Synthesizing Computable Skolem Functions for First Order Logic (abstract) |
| 11:05 | Computing the Minimum Bottleneck Moving Spanning Tree (abstract) |
| 11:30 | Weighted counting of matchings in unbounded-treewidth graph families (abstract) |
10:40-12:00 Session 8B
Chair:
Location: Lecture Room FH6
| 10:40 | Automating OBDD proofs is NP-hard (abstract) |
| 11:05 | The Pseudo-Reachability Problem for Affine Dynamical Systems (abstract) |
| 11:30 | Streaming word problems (abstract) |
12:00-14:00Lunch Break
14:00-15:40 Session 9A
Chair:
Location: Lecture Room FH5
| 14:00 | Cohomology in Constraint Satisfaction and Structure Isomorphism (abstract) |
| 14:25 | Bounded Degree Nonnegative Counting CSP (abstract) |
| 14:50 | Higher-Order Quantified Boolean Satisfiability (abstract) PRESENTER: Alessio Mansutti |
| 15:15 | CNF Encodings of Parity (abstract) |
14:00-15:40 Session 9B
Chair:
Location: Lecture Room FH6
| 14:00 | Comonadic semantics for hybrid logic (abstract) |
| 14:25 | Higher-order causal theories are models of BV-logic (abstract) |
| 14:50 | Towards a Model Theory of Ordered Logics: Expressivity and Interpolation (abstract) PRESENTER: Bartosz Bednarczyk |
| 15:15 | Generalized Bundled Fragments of First-order Modal Logic (abstract) |
15:40-16:10Coffee Break
16:10-17:15 Session 10: VCLA Award Ceremony and Anniversary (Co-located Event)
Consists of a general introduction, a talk by Tuukka Korhonen on "Finding Optimal Tree Decompositions", and a talk by Jasper Slusallek on “Algorithms and Lower Bounds for Finding (Exact-Weight) Subgraphs of Bounded Treewidth”.
Location: Lecture Room FH5
17:15-18:00Drinks and sweets
Wednesday, August 24th
View this program: with abstractssession overviewtalk overview
10:10-10:40Coffee Break
10:40-12:00 Session 13A
Chair:
Location: Lecture Room FH5
| 10:40 | A Universal Skolem Set of Positive Lower Density (abstract) |
| 11:05 | Boundaries to Single-Agent Stability in Additively Separable Hedonic Games (abstract) |
| 11:30 | The Complexity of Periodic Energy Minimisation (abstract) |
10:40-12:00 Session 13B
Location: Lecture Room FH6
| 10:40 | SAT-based Circuit Local Improvement (abstract) |
| 11:05 | Enumeration Classes Defined by Circuits (abstract) |
| 11:30 | Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits (abstract) |
12:00-14:00Lunch Break
14:00-15:40 Session 14A
Chair:
Location: Lecture Room FH5
| 14:00 | Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard (abstract) |
| 14:25 | On Kernels for d-Path Vertex Cover (abstract) |
| 14:50 | An exact algorithm for Knot-free Vertex Deletion (abstract) |
| 15:15 | Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets (abstract) |
14:00-15:40 Session 14B
Chair:
Location: Lecture Room FH6
| 14:00 | Sample compression schemes for balls in graphs (abstract) |
| 14:25 | Not all Strangers are the Same: The Impact of Tolerance in Schelling Games (abstract) PRESENTER: Maria Kyropoulou |
| 14:50 | Membership problems in finite groups (abstract) |
| 15:15 | On Algorithms Based on Finitely Many Homomorphism Counts (abstract) |
Thursday, August 25th
View this program: with abstractssession overviewtalk overview
09:00-10:15 Session 15A
Chair:
Location: Lecture Room FH5
| 09:00 | Improved Approximation Algorithms for the Traveling Tournament Problem (abstract) PRESENTER: Jingyang Zhao |
| 09:25 | Constant-factor approximation algorithm for binary search in trees with monotonic query times (abstract) |
| 09:50 | Rabbits approximate, cows compute exactly! (abstract) |
09:00-10:15 Session 15B
Location: Lecture Room FH6
| 09:00 | A Complexity Approach to Tree Algebras: the Polynomial Case (abstract) |
| 09:25 | Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set (abstract) |
| 09:50 | Algebraic Representations of Unique Bipartite Perfect Matching (abstract) |
10:15-10:50Coffee Break
10:50-12:10 Session 16A
Chair:
Location: Lecture Room FH5
| 10:50 | New Lower Bounds and Upper Bounds for Listing Avoidable Vertices (abstract) |
| 11:15 | The Hamilton compression of highly symmetric graphs (abstract) |
| 11:40 | On Dynamic α + 1 Arboricity Decomposition and Out-Orientation (abstract) |
10:50-12:10 Session 16B
Location: Lecture Room FH6
| 10:50 | On vanishing sums of roots of unity in polynomial calculus and sum-of-squares (abstract) PRESENTER: Ilario Bonacina |
| 11:15 | Complete ZX-calculi for the stabiliser fragment in odd prime dimensions (abstract) |
| 11:40 | Countdown mu-calculus (abstract) |
12:10-14:00Lunch Break
15:10-16:00 Session 18A
Chair:
Location: Lecture Room FH5
| 15:10 | On the Identity Problem for Unitriangular Matrices of Dimension Four (abstract) |
| 15:35 | On the Binary and Boolean Rank of Regular Matrices (abstract) |
15:10-16:00 Session 18B
Location: Lecture Room FH6
| 15:10 | On Uniformization in the Full Binary Tree (abstract) |
| 15:35 | Tree exploration in dual-memory model (abstract) |
16:00-16:30Coffee Break
16:30-17:45 Session 19A
Location: Lecture Room FH5
| 16:30 | Dispersing Obnoxious Facilities on Graphs by Rounding Distances (abstract) |
| 16:55 | Graph Realization of Distance Sets (abstract) |
| 17:20 | The complexity of computing optimum labelings for temporal connectivity (abstract) PRESENTER: Nina Klobas |
16:30-17:45 Session 19B
Location: Lecture Room FH6
| 16:30 | Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus (abstract) |
| 16:55 | Space-Bounded Unitary Quantum Computation with Postselection (abstract) |
| 17:20 | LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits (abstract) |
Friday, August 26th
View this program: with abstractssession overviewtalk overview
10:00-10:40Coffee Break
10:40-12:20 Session 21A
Chair:
Location: Lecture Room FH5
| 10:40 | Independent set reconfiguration on directed graphs (abstract) |
| 11:05 | Fixed-point cycles and approximate EFX allocations (abstract) |
| 11:30 | On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph (abstract) |
| 11:55 | Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees (abstract) |
10:40-12:20 Session 21B
Chair:
Location: Lecture Room FH6
| 10:40 | Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting (abstract) |
| 11:05 | On the Number of Quantifiers as a Complexity Measure (abstract) |
| 11:30 | Oracle with P = NP ∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP (abstract) |
| 11:55 | Non-Determinism in Lindenmayer Systems and Global Transformations (abstract) |
12:30-14:00Lunch Break