FCT 2019

22nd International Symposium on Fundamentals of Computation Theory

The Symposium on Fundamentals of Computation Theory was established in 1977 for researchers interested in all aspects of theoretical computer science, particularly in algorithms, complexity, formal and logical methods. It is held as a biennial series of conferences.

It is a biennial series of conferences and was previously held in Copenhagen, Denmark in 2019. 

 

 

 

Algorithms

  • algorithm design and optimization
  • data structures
  • combinatorics and analysis of algorithms
  • randomized algorithms
  • approximation algorithms
  • parameterized and exact algorithms
  • computational algebra and number theory
  • computational geometry
  • parallel algorithms
  • distributed algorithms and protocols
  • online algorithms
  • streaming algorithms
  • algorithmic game theory
  • computational foundations of machine learning
  • computational biology

Complexity

  • models of computation
  • computational complexity
  • decidability
  • Boolean/algebraic circuits and functions
  • randomized computation
  • derandomization
  • interactive proofs
  • computational foundations of cryptography
  • quantum computation
  • complexity theory
  • lower bounds
  • counting complexity

Formal methods

  • algebraic and categorical methods
  • automata and formal languages
  • database theory
  • foundations of concurrency and distributed systems
  • logic and model checking
  • models of reactive, hybrid, and stochastic systems
  • principles of programming languages
  • program analysis and transformation
  • security
  • specification, refinement, and verification
  • type systems
  • ad hoc, dynamic, and evolving systems

 

 

  • Libor Barto, Charles University
  • Bernard Chazelle, Princeton University
  • Kousha Etessami, University of Edinburgh
  • Torben Hagerup, University of Augsburg

 

 

The list of accepted papers:

Hernán González-Aguilar, David Orden, Pablo Pérez-Lantero, David Rappaport, Carlos Seara, Javier Tejel and Jorge Urrutia: Maximum Rectilinear Convex Subsets

Sankardeep Chakraborty, Anish Mukherjee and Srinivasa Rao Satti: Space Efficient Algorithms for Breadth-Depth Search

Vikraman Arvind, Frank Fuhlbrück, Johannes Koebler and Oleg Verbitsky. On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Walen and Wiktor Zuba: Circular Pattern Matching with k Mismatches

Markus Lohrey and Sebastian Maneth: Largest Common Prefix of a Regular Tree Languages

Alexander Kozachinskiy and Alexander Shen: Two Characterizations of Finite State Dimension

Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei, Jerome Monnot and Florian Sikora: Extension of Some Edge Graph Problems: Standard and Parameterized Complexity

Christian Coester, Thomas Schwentick and Martin Schuster: Winning Strategies for Streaming Rewriting Games

Riccardo Dondi and Manuel Lafond: Tractability of Covering a Graph with Clubs

Frank Gurski, Dominique Komander and Carolin Rehs: Computing Digraph Width Measures on Directed Co-Graphs

Miroslaw Kowaluk and Andrzej Lingas: Rare Siblings Speed-up Deterministic Detection and Counting of Small Pattern Graphs

Dominique Schmitt: Bivariate B-splines from Convex Pseudo-Circle Configurations

Gianluca De Marco, Tomasz Jurdzinski and Dariusz Kowalski: Optimal Channel Utilization with Limited Feedback

Bireswar Das, Shivdutt Sharma and P. R. Vaidyanathan: Succinct Representation of Finite Groups

Duygu Vietz and Egon Wanke: The Fault-Tolerant Metric Dimension of Cographs

Andreas Bärtschi and Stephan Eidenbenz: Deterministic Preparation of Dicke States

Iago A. Carvalho, Thomas Erlebach and Kleitos Papadopoulos: An Efficient Algorithm for the Fast Delivery Problem 

Titus Dose: Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle

Jesus Dominguez and Maribel Fernandez: Nominal Syntax with Atom Substitutions: Matching, Unification, Rewriting

Marek Klonowski, Dariusz Kowalski, Jaroslaw Mirek and Prudence Wong: Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel

Carl Feghali, Matthew Johnson, Giacomo Paesani and Daniel Paulusma: On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest

 

 

 

 

 

 

Program committee

  • Marthe Bonamy, National Center for Scientific Research (CNRS), Bordeaux
  • Irene Finocchi, Sapienza University of Rome
  • Leszek Gąsieniec, University of Liverpool (co-chair)
  • William Harris, Galois Inc.
  • Mika Hirvensalo, University of Turku
  • Štěpán Holub, Charles University in Prague
  • Jesper Jansson, Hong Kong Polytechnic University (co-chair)
  • Jyrki Katajainen, University of Copenhagen (co-chair, currently unavailable)
  • Ralf Klasing, CNRS and University of Bordeaux
  • Rastislav Královič, Comenius University in Bratislava
  • Stefan Kratsch, Humboldt University of Berlin
  • Erik Jan van Leeuwen, Utrecht University
  • Christos Levcopoulos, Lund University (co-chair)
  • Florin Manea, Kiel University
  • Toby Murray, University of Melbourne
  • Aris Pagourtzis, National Technical University of Athens
  • Wojciech Plandowski, University of Warsaw
  • Nitin Saxena Indian, Institute of Technology Kanpur
  • Jeffrey Shallit, University of Waterloo
  • Jesper Larsson Träff, TU Wien (Vienna University of Technology)
  • Peter Widmayer, ETH Zürich

Steering committee

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

Organizing committee

Thomas Hildebrandt - University of Copenhagen

 

 

 

 

 

 

 

 

 

 

 

 

  • FCT 2023, Trier, Germany
  • FCT 2021, Athens, Greece
  • FCT 2019, Copenhagen, Denmark
  • FCT 2017, Bordeaux, France (Proceedings published by Springer, LNCS volume 10472)
  • FCT 2015, Gdańsk, Poland (Proceedings published by Springer, LNCS volume 9210)
  • FCT 2013, Liverpool, United Kingdom (Proceedings published by Springer, LNCS volume 8070)
  • FCT 2011, Oslo, Norway (Proceedings published by Springer, LNCS volume 6914)
  • FCT 2009, Wrocław, Poland (Proceedings published by Springer, LNCS volume 5699)
  • FCT 2007, Budapest, Hungary (Proceedings published by Springer, LNCS volume 4639)
  • FCT 2005, Lübeck, Germany (Proceedings published by Springer, LNCS volume 3623)
  • FCT 2003, Malmö, Sweden (Proceedings published by Springer, LNCS volume 2751)
  • FCT 2001, Riga, Latvia (Proceedings published by Springer, LNCS volume 2138)
  • FCT 1999, Iasi, Romania (Proceedings published by Springer, LNCS volume 1684)
  • FCT 1997, Krąków, Poland (Proceedings published by Springer, LNCS volume 1279)
  • FCT 1995, Dresden, Germany (Proceedings published by Springer, LNCS volume 965)
  • FCT 1993, Szeged, Hungary (Proceedings published by Springer, LNCS volume 710)
  • FCT 1991, Gosen, Germany (Proceedings published by Springer, LNCS volume 529)
  • FCT 1989, Szeged, Hungary (Proceedings published by Springer, LNCS volume 380)
  • FCT 1987, Kazan, Russia (Proceedings published by Springer, LNCS volume 278)
  • FCT 1985, Cottbus, Germany (Proceedings published by Springer, LNCS volume 199)
  • FCT 1983, Borgholm, Sweden (Proceedings published by Springer, LNCS volume 158)
  • FCT 1981, Szeged, Hungary (Proceedings published by Springer, LNCS volume 117)
  • FCT 1979, Wendisch-Rietz, Germany (Proceedings published by Akademie-Verlag)
  • FCT 1977, Poznań-Kórnik, Poland (Proceedings published by Springer, LNCS volume 56)

 

 

 

Contact

Thomas Hildebrandt, professor
Dept. of Computer Science
University of Copenhagen
hilde@di.ku.dk

Sponsors

  • Springer
  • Journal of Computer and System Science (special issue)
  • European Association for Theoretical Computer Science (EATCS)
  • SCANDIC (official hotel partner)
  • Department of Computer Science, University of Copenhagen