24th International Symposium on Fundamentals of Computation Theory, FCT 2023

September 18-21, 2023, Trier, Germany

News

  • Venue: All talks will be in room C10 on Campus 1, Univ. Trier. Rooms C2, C3 and C4 will be also available for common research during the conference and the subsequent workshop. All the rooms are in the C building (see Campus 1 map). A more detailed conference program is available below.
  • Registration is now open. For the authors of accepted papers, we request that at least one author will register with "full registration". Non-full online registrations are for free. Only to fully-registered participants, printed proceedings can be delivered. We will close the registration server on THU, Sept. 14th, 2023.
  • List of accepted papers appears below.
  • Titles of the invited talks have been added below to the speakers.
  • The submission server is closed now. We are currently evaluating the submissions. As planned, notifications will be sent out by mid-July.
  • Thanks for submitting original research in Theoretical Computer Science, formatted using LNCS style: at most 14 pages (including references) plus a clearly marked appendix. Firm abstract deadline: May 26th, 2023; full papers must be submitted until June 1st, 2023. The reviewing is single-blind.
  • We plan to have a 1-day informal workshop on “Graph Labelling in Computer Science” (GLiCS) after the conference, on September, 22nd. Details will be fixed soon.
  • Special Issue for the best papers of FCT 2023 approved with the prestigious Journal of Computer and System Sciences.
  • Four invited speakers have confirmed their participation, details below.
  • Further algorithmic papers will be invited for another Special Issue with Algorithms.
  • Publication of conference proceedings as an LNCS volume of the ARCoSS subline approved by Springer.
  • There will be a best paper and a best student paper award sponsored by the publisher Springer.
  • We are grateful for a further special sponsorship of the conference from the publisher MDPI.

Detailed Program

SUN, Sept. 17th:

MON, Sept. 18th, in C10:

  • 8:20-9:00 Registration
  • 9:00-9:20 Opening of the Conference
  • 9:20-10:35 Session C1: Three contributed talks, showing the breadth of the topics <Chair: F. Frei>
    • Kodai Tanaka, Takaaki Mizuki: Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku
    • Sewon Park: Verified Exact Real Computation with Nondeterministic Functions and Limits
    • Zack Fitzsimmons, Edith Hemaspaandra: Complexity of Conformant Election Manipulation
  • 10:35-11:05 Coffee Break
  • 11:05-12:20 Session C2: Three contributed talks: Pattern in Graphs <A. Hakanen>
    • Nick Brettell, Jelle Oostveen, Daniel Paulusma, Erik Jan van Leeuwen, Sukanya Pandey: Computing Subset Vertex Covers in H-Free Graphs
    • Ajinkya Gaikwad, Soumen Maity: Parameterized Complexity of Th+1-Free Edge Deletion Problem
    • Dipayan Chakraborty, RB Sandeep: Contracting Edges to Destroy a Pattern: A Complexity Study
  • 12.20-14:05 Lunch, including coffee
  • 14:05-15:20 Session C3: Three contributed talks: Computational Geometry <EJ van Leeuwen>
    • William Evans, David Kirkpatrick: Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time
    • Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teyuyama, Binhai Zhu: On Computing a Center Persistence Diagram
    • Daniela Bubboloni, Costanza Catalano, Andrea Marino, Ana Silva: On Computing Optimal Temporal Branchings
  • 15:20-15:25 Short Break
  • 15:25-16:00 Session BPA 1: Michael Levet, Joshua A. Grochow: On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman <T. Yamakami>
  • 16:00-16:05 Short Break
  • 16:05-17:35 Session I1:  Invited Talk of Lila Kari: Word Frequency and Machine Learning for Biodiversity Informatics
  • 17:35-17:40 Short Break <T. Yamakami>
  • 17:40-18:00 Open Problems? Closing of the Day

TUE, Sept. 19th, in C10:

  • 8:20-10:00 Session C4: Four contributed talks: Graph Algorithms and FPT <RB Sandeep>
    • Carlos Alegría, Justin Dallant, Pablo Pérez-Lantero, Carlos Seara: The Rectilinear Convex Hull of Line Segments
    • Uéverton Souza, Dieter Rautenbach, Johannes Rauch: Exact and Parameterized Algorithms for the Independent Cutset Problem
    • Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen: Distance-based Covering Problems for Graphs of Given Cyclomatic Number
    • Emmanuel Sam, Benjamin  Bergougnoux, Petr Golovach, Nello Blaser, Nello Blaser: Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
  • 10:00-10:30 Coffee Break
  • 10:30-12:00 Session C5: Three contributed talks: Algebraic Flavors <D. Kirkpatrick>
    • Samy Abbes: Convergence of Distributions on Paths
    • Nicolas Bitar, Nathalie Aubrun: Domino Snake Problems on Groups
    • Lamar Chidiac, Santiago Guzman-Pro, Anthony Youssef, Winfried Hochstättler: An Efficient Computation of the Rank Function of a Positroid
    • Update on Open Problems
  • 12:00-13:30  Lunch, including coffee
  • 13:30-14:00: What is Graph Labeling? GLiCS Announcement and one contributed talk <H. Fernau>
    • Feston Kastrati, Wendy Myrvold, Lucas Panjer, Aaron Williams: Cordial Forests
  • 14:00-14:25 Coffee Break
  • 14:25-15:00 Session BPA 2: Zohair Raza Hassan, Edith Hemaspaandra, Stanisław Radziszowski: The Complexity of (Pk, Pl)-Arrowing <B. Zhu>
  • 15:00-15:15 Short Coffee Break
  • 15:15-16:45 Session I2: Invited Talk of Claire Mathieu: Approximation Algorithms for Vehicle Routing <B. Zhu>
  • 16:45-17:00 Short Break
  • 17:00-18:00 Business Meeting of FCT

WED, Sept. 20th, in C10:

  • 8:20-10:00 Session C6: Four contributed talks: Automata Theory <H. Fernau>
    • Martin Berglund, Henrik Björklund, Johanna Björklund: Parsing Unranked Tree Languages, Folded Once
    • Antonio Al Serhali, Joachim Niehren: Subtree Projection for Stepwise Hedge Automata
    • Tomoyuki Yamakami: Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
    • Philip Kaelbling, Dakotah Lambert, Jeffrey Heinz: Robust Identification in the Limit from Incomplete Positive Data
  • 10:00-10:30 Coffee Break
  • 10:30-12:00 Session I3: Invited Talk of Stefan Glock: Hamilton Cycles in Pseudorandom Graphs <A. Rafiey>
  • 12:00-13:15  Lunch
  • 13:15 Conference Photo
  • 13:20- Walking Downtown
  • 15:00-17:00 Guided Tours
  • 18:00-18:30 Walk to Conference Dinner Location
  • 18:30- Conference Dinner

THU, Sept. 21st, in C10:

  • 8:20-09:35 Session C7: Three contributed talks: Computations on Graph Classes <C. Seara>
    • Van Bang Le, Christian Rosenke: Computing Optimal Leaf Roots of Chordal Cographs in Linear Time
    • Matyáš Křišťan, Jakub Svoboda: Shortest Dominating Set Reconfiguration under Token Sliding
    • Jeff Kinne, Arash Rafiey, Akbar Rafiey, Mohammad Sorkhpar: Vertex Ordering with Precedence Constraints
  • 09:35-10:05 Coffee Break
  • 10:05-11.30 Session C8: Three contributed talks on strings and friends and more open questions? <D. Dereniowski>
    • Dietrich Kuske, Chris Köcher: Forwards- and Backwards-Reachability for Cooperating Multi-Pushdown Systems
    • Pamela Fleischmann, Jonas Höfer, Annika Huch, Dirk Nowotka: α-β-Factorization and the Binary Case of Simon’s Congruence
    • Fabian Frei, David Wehner: Bounds for c-Ideal Hashing
  • 11:30-13:00 Lunch
  • 13:00-13:35 Session BPA 3: Johanna Björklund: The Impact of State Merging on Predictive Accuracy in Probabilistic Tree Automata: Dietze's Conjecture Revisited <J. Niehren>
  • 13:35-14:00 Coffee Break
  • 14:00-15:30 Session I4: Invited Talk of Karl Bringmann: Fine-Grained Complexity of Knapsack Problems <J. Niehren>
  • 15:30-15:40 Farewell Announcements
  • 15:40- Free Time for Research

FRI, Sept. 22nd, in C10, C2, C3, C4: Common Research (GLiCS)

Invited Speakers

  • Karl Bringmann, MPI Saarbrücken, Germany: Fine-Grained Complexity of Knapsack Problems
  • Stefan Glock, Univ. Passau, Germany: Hamilton Cycles in Pseudorandom Graphs
  • Lila Kari, Univ. Waterloo, Canada: Word Frequency and Machine Learning for Biodiversity Informatics
  • Claire Mathieu, Univ. Sorbonne Paris, CNRS, France: Approximation Algorithms for Vehicle Routing

Accepted Papers

  • Samy Abbes: Convergence of Distributions on Paths
  • Antonio Al Serhali, Joachim Niehren: Subtree Projection for Stepwise Hedge Automata
  • Carlos Alegría, Justin Dallant, Pablo Pérez-Lantero, Carlos Seara: The Rectilinear Convex Hull of Line Segments
  • Nicolas Bitar, Nathalie Aubrun: Domino Snake Problems on Groups
  • Martin Berglund, Henrik Björklund, Johanna Björklund: Parsing Unranked Tree Languages, Folded Once
  • Johanna Björklund: The Impact of State Merging on Predictive Accuracy in Probabilistic Tree Automata: Dietze's Conjecture Revisited
  • Nick Brettell, Jelle Oostveen, Daniel Paulusma, Erik Jan van Leeuwen, Sukanya Pandey: Computing Subset Vertex Covers in H-Free Graphs
  • Daniela Bubboloni, Costanza Catalano, Andrea Marino, Ana Silva: On Computing Optimal Temporal Branchings
  • Dipayan Chakraborty, RB Sandeep: Contracting Edges to Destroy a Pattern: A Complexity Study
  • Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen: Distance-based Covering Problems for Graphs of Given Cyclomatic Number
  • Lamar Chidiac, Santiago Guzman-Pro, Anthony Youssef, Winfried Hochstättler: An Efficient Computation of the Rank Function of a Positroid
  • William Evans, David Kirkpatrick: Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time
  • Zack Fitzsimmons, Edith Hemaspaandra: Complexity of Conformant Election Manipulation
  • Pamela Fleischmann, Jonas Höfer, Annika Huch, Dirk Nowotka: α-β-Factorization and the Binary Case of Simon’s Congruence
  • Fabian Frei, David Wehner: Bounds for c-Ideal Hashing
  • Ajinkya Gaikwad, Soumen Maity: Parameterized Complexity of T_{h+1}-Free Edge Deletion Problem
  • Michael Levet, Joshua A. Grochow: On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
  • Zohair Raza Hassan, Edith Hemaspaandra, Stanisław Radziszowski: The Complexity of (P_k, P_l)-Arrowing
  • Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teyuyama, Binhai Zhu: On Computing a Center Persistence Diagram
  • Philip Kaelbling, Dakotah Lambert, Jeffrey Heinz: Robust Identification in the Limit from Incomplete Positive Data
  • Feston Kastrati, Wendy Myrvold, Lucas Panjer, Aaron Williams: Cordial Forests
  • Jeff Kinne, Arash Rafiey, Akbar Rafiey, Mohammad Sorkhpar: Vertex ordering with precedence constraints
  • Dietrich Kuske, Chris Köcher: Forwards- and Backwards-Reachability for Cooperating Multi-Pushdown Systems
  • Matyáš Křišťan, Jakub Svoboda: Shortest Dominating Set Reconfiguration under Token Sliding
  • Van Bang Le, Christian Rosenke: Computing Optimal Leaf Roots of Chordal Cographs in Linear Time
  • Sewon Park: Verified Exact Real Computation with Nondeterministic Functions and Limits
  • Uéverton Souza, Dieter Rautenbach, Johannes Rauch: Exact and Parameterized Algorithms for the Independent Cutset Problem
  • Emmanuel Sam, Benjamin  Bergougnoux, Petr Golovach, Nello Blaser: Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
  • Kodai Tanaka, Takaaki Mizuki: Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku
  • Tomoyuki Yamakami: Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata

In the list above, the selected best papers are highlighted in bold, while the best student paper is underlined.

Important Dates

  • May 26th, 2023, AOE: Abstract submission deadline (firm)
  • June 1st, 2023, AOE: Paper submission deadline (firm)
  • July 17th, 2023: Author notifications
  • July 24th, 2023, AOE: Final papers due
  • September 18th-21st, 2023: FCT conference dates

Venue

  • University of Trier, Campus 1
  • If you intend to come, please decide where to stay on your own: either down-town or closer to the university.

Program Committee

  • Akanksha Agrawal, IITM Chennai, India
  • Evripidis Bampis, Sorbonne Univ., France
  • Hans Bodlaender, Univ. Utrecht, The Netherlands
  • Ahmed Bouajjani, Univ. Paris Diderot, France
  • Bogdan Chlebus, Augusta Univ., USA
  • Ugo Dal Lago, Univ. Bologna, Italy
  • Vida Dujmovic, Univ. Ottawa, Canada
  • Leah Epstein, Univ. Haifa, Israel
  • Piotr Faliszewski, AGH Univ. Science and Technology, Krakow, Poland
  • Henning Fernau, Univ. Trier, Germany (co-chair)
  • Robert Ganian, TU Vienna, Austria
  • Klaus Jansen, Univ. Kiel, Germany (co-chair)
  • Artur Jeż, Univ. Wrocław, Poland
  • Mamadou Kanté, Univ. Clermont Auvergne, France
  • Arindam Khan, IIS Bangalore, India
  • Ralf Klasing, CNRS, Univ. Bordeaux, France
  • Jan Kratochvíl, Charles Univ. Prague, Czech Republic
  • Sławomir Lasota, Univ. Warsaw, Poland
  • Florin Manea, Univ. Göttingen, Germany
  • Tomáš Masopust, Palacky Univ. Olomouc, Czech Republic
  • Matthias Mnich, TU Hamburg, Germany
  • Nelma Moreira, Univ. Porto, Portugal
  • Norbert Müller, Univ. Trier, Germany
  • Yoshio Okamoto, Univ. Electro-Commun., Japan
  • Sang-il Oum, IBS / KAIST, South Korea
  • Kenta Ozeki, Yokohama Nat. Univ., Japan
  • Markus Schmid, HU Berlin, Germany
  • Uéverton Souza, Univ. Federal Fluminense, Brazil
  • Frank Stephan, NUS, Singapore
  • José Verschae, Univ. Católica de Chile, Chile
  • Boting Yang, Univ. Regina, Canada
  • Guochuan Zhang, Univ. Zhejiang, China
  • Binhai Zhu, Montana State Univ., USA

List of Topics (Not Exclusive)

  • Algorithmic Game Theory, Complexity of Games
  • Algorithmic Learning Theory
  • Algorithmic Randomness
  • Algorithms and Data Structures
  • Algorithms for Big Data
  • Approximation Algorithms
  • Automata Theory
  • Average-Case Analysis 
  • Combinatorics and Graph Theory
  • Combinatorial Generation, Enumeration and Counting
  • Combinatorial Optimization
  • Combinatorial Reconfiguration
  • Combinatorics of Words
  • Complexity Theory
  • Computable Analysis
  • Computational Biology
  • Computational Geometry
  • Computational Learning Theory
  • Computational Social Choice
  • Computability, Recursion Theory
  • Concurrency
  • Data Compression
  • Database Theory
  • Descriptional Complexity 
  • Discrete Event Systems, including Petri Nets
  • Discrete Optimization
  • Distributed, Parallel and Network Algorithms
  • Energy-Aware Algorithms
  • Fine-grained Complexity
  • Formal Languages
  • Formal Specification and Verification
  • Foundations of Artificial Intelligence
  • Graph Algorithms and Modelling with Graphs
  • Graph Drawing and Graph Labeling
  • Grammatical Inference
  • Integer and Linear Programming
  • Logic in Computer Science
  • Matroid Theory
  • Model-Checking Algorithms
  • Network Theory and Temporal Graphs
  • Online Algorithms
  • Parameterized and Exact Algorithms
  • Parameterized Complexity
  • Probabilistic and Randomized Algorithms
  • Program Semantics
  • Scheduling
  • String Algorithms
  • Telecommunication Algorithms
  • Theorem Provers and Automated Reasoning
  • Voting Theory
  • Width Parameters

Organizing Committee

  • Henning Fernau, University of Trier, University of Trier, Germany
  • Philipp Kindermann, University of Trier, University of Trier, Germany
  • Zhidan Feng, University of Trier, Germany
  • Kevin Mann, University of Trier, Germany

Steering Committee

  • Bogdan Chlebus, University of Colorado, US
  • Marek Karpinski (chair), University of Bonn, Germany
  • Andrzej Lingas, Lund University, Sweden
  • Miklos Santha, CNRS and University Paris Diderot, France
  • Eli Upfal, Brown University, US