IARCS, the Indian Association for Research in Computing Science, announces the 39th Foundations of Software Technology and Theoretical Computer Science conference at IIT Bombay. The FSTTCS conference is a forum for presenting original results in foundational aspects of Computer Science and Software Technology.

Representative areas include, but are not limited to, the following.

Track A

  • Algorithms and Data Structures
  • Algorithmic Graph Theory and Combinatorics
  • Approximation Algorithms
  • Combinatorial Optimization
  • Communication Complexity
  • Computational Biology
  • Computational Complexity
  • Computational Geometry
  • Computational Learning Theory
  • Cryptography and Security
  • Data Streaming and Sublinear algorithms
  • Game Theory and Mechanism Design
  • Parallel, Distributed and Online Algorithms
  • Parameterized Complexity
  • Proof Complexity
  • Quantum Computing
  • Randomness in Computing
  • Theoretical Aspects of Mobile and High-Performance Computing

Track B

  • Automata, Games and Formal Languages
  • Logic in Computer Science
  • Modal and Temporal Logics
  • Model Checking and Reactive Synthesis
  • Models of Concurrent, Distributed and Mobile Systems
  • Models of Timed, Reactive, Hybrid and Stochastic Systems
  • Model Theory
  • Principles and Semantics of Programming Languages
  • Program Analysis and Transformation
  • Security protocols
  • Theorem Proving and Decision Procedures

Submissions must be in electronic form via ​EasyChair using the ​LIPIcs LaTeX style file. Submissions must not exceed 12 pages (excluding bibliography), but may include a clearly marked appendix containing technical details. The appendix will be read only at the discretion of the program committee. Simultaneous submissions to journals or other conferences with published proceedings are disallowed.

Accepted papers will be published as proceedings of the conference in the ​Leibniz International Proceedings in Informatics (LIPIcs)​ as a free, open, electronic archive with access to all. Authors will retain full rights over their work. The accepted papers will be published under a ​CC-BY license​. For an accepted paper to be included in the proceedings, one of the authors must commit to presenting the paper at the conference.

  • Submission deadline: July 17, 2019 AoE (firm).
  • Notification to authors: September 13, 2019.
  • Deadline for camera-ready papers: October 1, 2019 AoE.
  • SAT/SMT winter school (co-located with FSTTCS 2019): December 8–10, 2019.
  • Pre-conference workshop: December 10, 2019.
  • FSTTCS 2019: December 11–13, 2019.
  • Post-conference workshop : December 14, 2019.

Track A

Complexity in Algorithmic Game Theory

Since its inception, complexity has played a central role in algorithmic game theory. One of the most foundational results in this field is the PPAD-hardness of computing a Nash equilibrium. The complexity of vote manipulation is another classic, negative result in this context. Indeed, the study of complexity of game-theoretic solution concepts has led to renewed interest in complexity classes, such as PPAD and PLS, as well as the introduction of new classes, e.g., CLS. Besides computational complexity, a rich literature has also emerged that studies other notions such as communication complexity, query complexity, and menu-size complexity.

The objective of this workshop is to bring together interested researchers to learn and discuss results on complexity in game theory. Towards this end, the workshop will combine presentations on recent research and tutorial-style talks, along with discussions on interesting, open problems. The encompassing theme of this workshop is aimed at bringing together a diverse audience.

Extension Complexity and Lifting Theorems

The workshop will focus on two exciting subareas of communication complexity where a lot of progress has been made in the past few years: extension complexity and lifting theorems. Extension complexity is an exciting area at the intersection of combinatorial optimization and communication complexity. The area studies the sizes of the smallest (LP or SDP or more generally convex) extensions of polytopes and the techniques used share a lot in common with communication complexity. Another hot topic in communication complexity nowadays is the study of lifting theorems: lifting hardness from simpler models (usually in query complexity) to more complex models (usually in communication complexity). Such lifting theorems are now known for various models including the ones arising in extension complexity. The workshop will focus on classical results as well as recent progress.

Track B

Trends in Transformations

The beautiful and robust theory of regular languages is based on four fundamental pillars: expressions, automata, logic and algebra. Extensions of the pillars of language theory to transformations(functions or relations) from words has been a very active area of research recently. The aim of this workshop is to bring together researchers and students interested in theory and applications of formal models of transformations (transducers). The workshop will feature tutorial kind of talks as well as recent state of the art results in transducers.

  • Date: December 10, 2019
  • Organizer: S Krishna (IIT Bombay)

GALA: Gems of Automata, Logic and Algebra

This workshop will be targeted towards the participants of FSTTCS 2019, consisting of academicians and graduate students broadly in the area of theoretical computer science, with a focus on classical and recent topics in automata, logic and algebraic techniques in formal methods.

Track A


Track B

Theory group and Formal Methods group, IIT Bombay.