FSTTCS 2025

FSTTCS 2025 is the 45th conference on Foundations of Software Technology and Theoretical Computer Science. It is organised by IARCS, the Indian Association for Research in Computing Science, in association with ACM India. It is a forum for presenting original results in foundational aspects of Computer Science and Software Technology.

FSTTCS 2025 will be held in BITS Pilani, K K Birla Goa Campus during December 17–19, 2025. The conference is being organized as an in-person event.

List of Topics

Track A

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

Track B

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

We particularly welcome papers in Programming Languages and Formal Methods Tor Track B.

Submission Guidelines

Submissions must be in electronic form via EasyChair using the LIPIcs LaTeX style file available here. Submissions must not exceed 15 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.

Reviewing for FSTTCS 2025 is double-blind. Hence, authors must make a reasonable effort to ensure that their identity is not easily revealed from the submission itself. Specifically, kindly replace your name and affiliation on the first page with the submission number and do not include any acknowledgements in your submission. Also, authors should cite their prior work in a neutral manner (i.e., instead of saying “We showed”, please write “XYZ et al. showed”). Submitting a paper that is available at a public preprint server (such as, arXiv) is admissible. In that case, please do not cite that version of your work in the submission itself. Submissions violating the page limit or the double-blind policy may face desk rejection.

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 in person at the conference.

Submission link: https://easychair.org/my/conference?conf=fsttcs2025

Important Dates

  • Pre-conference workshops: December 14 – 16, 2025
  • FSTTCS 2025: December 17 – 19, 2025
  • Post-conference workshops: December 20, 2025

Invited Speakers

  • Parosh Aziz Abdulla, Uppsala University & Mälardalen University

    Quantum Circuit Verification – A Potential Roadmap

    Quantum technologies are progressing at an extraordinary pace and are poised to transform numerous sectors both nationally and globally. Among them, quantum computing stands out for its potential to revolutionize areas such as cryptography, optimization, and the simulation of quantum systems, offering dramatic speed-ups for specific classes of problems.

    As quantum devices evolve and become increasingly pervasive, guaranteeing their correctness is of paramount importance. This necessitates the development of rigorous methods and tools to analyze and verify their behavior. However, the construction of such verification frameworks presents fundamental challenges. Quantum phenomena such as superposition and entanglement give rise to computational behaviors that differ profoundly from those of classical systems, leading to inherently probabilistic models and exponentially large state spaces, even for relatively small programs.

    Addressing these challenges requires building on the extensive expertise of the formal methods community in classical program verification, while incorporating recent advances and collaborative efforts in quantum systems. An interesting challenge for the verification community is to design and implement novel verification frameworks that transfer the key strengths of classical verification, such as expressive specification, precise error detection, automation, and scalability, to the quantum domain. We expect that the results of this research will play a crucial role in enabling the dependable deployment of quantum technologies across a wide range of future applications.

    Speaker Bio

    Parosh Aziz Abdulla is a Professor at the Department of Information Technology at Uppsala University. His research interests include formal methods, automata theory and logic in computer science, program verification, and model checking. He was a co-recipient of the LICS Test-of-Time Award in 2016 for his 1996 paper on the verification of well quasi-ordered programs, and a co-recipient of the CAV Award in 2017 for his contributions to the verification of programs with infinite state spaces. He has authored more than 200 publications and has received over ten best paper awards, including awards from the European Association for Software Science and Technology at ETAPS, the European Association for Theoretical Computer Science at ETAPS 2010 and ICALP 2001, and the European Association for Programming Languages and Systems at ETAPS 2000.

  • Bernd Finkbeiner, CISPA Helmholtz Center for Information Security and Technical University of Munich

    Hyperproperties as Design Principles: Information-Flow Guided Synthesis and Explainability in Distributed Systems

    Information flow is central to the design of distributed and multi-agent systems, and its formal analysis naturally leads to hyperproperties – requirements over sets of executions. This talk presents two developments that use hyperproperties to address core challenges in synthesis and verification.

    First, we introduce information-flow assumptions, which capture the epistemic requirements a specification imposes on components in a distributed system. Unlike traditional behavioral assumptions, they characterize which information must be available rather than how it is produced. This yields a new compositional approach to distributed synthesis. Second, we discuss the specification and verification of explainability, understood as a positive information-flow requirement ensuring that agents can know why certain effects occur. Using epistemic temporal logic enriched with counterfactual reasoning, we obtain expressive system-level specifications that interact naturally with privacy constraints. Together, these results illustrate how hyperproperties offer a unifying foundation for designing and analyzing trustworthy distributed and multi-agent systems.

    Speaker Bio

    Bernd Finkbeiner is a tenured faculty member at the CISPA Helmholtz Center for Information Security and a full professor of Computer Science at the Technical University of Munich. He received his Ph.D. from Stanford University in 2003 under the supervision of Zohar Manna. He then joined Saarland University, where he founded the Reactive Systems Group. In 2020, he became a faculty member at CISPA, and in 2025, he was appointed professor at TUM.

    Bernd Finkbeiner received an ERC Consolidator Grant for his work on reactive synthesis and an ERC Advanced Grant for his research on hyperproperties. His current work focuses on verification, synthesis, monitoring, and program repair, with the goal of improving the reliability and security of software and cyber-physical systems.

  • Nicole Immorlica, Yale University & Microsoft Research New England

    Agentic Markets

    Large language models have enabled humans to speak to machines in natural language. This lowers communication barriers between humans and machines and generates the potential for humans to delegate large complex tasks to machines. This talk explores the economic implications of such a technology for markets. Motivated by AI agents like OpenAI's Operator and Amazon's Rufus, we envision a world where AI agents buy and sell on behalf of consumers and firms in an agentic market. We argue that such a market has the potential to improve outcomes by finding better matches. However, this requires an open marketplace with user-aligned agents, agents that overcome position biases, and a mechanism to monetize the platforms that host the markets. This talk surveys these and related issues.

    Speaker Bio

    Nicole Immorlica is a professor at Yale University and a researcher at Microsoft. Nicole's research interest is in the design and operation of sociotechnical systems. Using tools and modeling concepts from both theoretical computer science and economics, Nicole hopes to explain, predict, and shape behavioral patterns in various online and offline systems, markets, and games. She is the recipient of a number of fellowships and awards including ACM Fellow, Society for the Advancement of Economic Theory (SAET) Fellow, the Sloan Fellowship, the Microsoft Faculty Fellowship and the NSF CAREER Award. She has served on several boards including the ACM SIGecom executive board, the editorial board of Games and Economic Behavior, and the INFORMS Auction and Market Design board.

  • Pravesh K Kothari, Princeton University

    Algorithms from Combinatorics, Combinatorics from Algorithms

    I will present the surprising interplay between algorithm design in semirandom models and well-studied questions in extremal combinatorics and coding theory. I will focus on the examples of Max k-SAT and Max Clique and present new spectral methods that resolve classical questions in finding (conjecturally) optimal algorithms for these problems in semirandom models and, at the same time, make progress on well-studied (rainbow) girth problems in hypergraph combinatorics, Hamada's conjecture on block designs, and bounds on locally decodable and correctable codes in coding theory.

    Speaker Bio

    Pravesh K Kothari received his Ph. D. from the University of Texas at Austin in 2016 after a Bachelor's degree from Indian Institute of Technology, Kanpur. He is currently an Assistant Professor in the Computer Science Department at Princeton University. Earlier, from 2019-2023, he was an Assistant Professor in the Computer Science Department at Carnegie Mellon University. Dr. Kothari was a Research Instructor of Computer Science jointly hosted by the Institute for Advanced Study, Princeton and the Department of Computer Science at Princeton University from 2016-19.

    Dr. Kothari's research interests span several topics in theoretical computer science such as convex optimization and applications to algorithm design, algorithms and lower bounds for statistical estimation and average-case combinatorial optimization, and spectral methods and connections to random matrix theory, coding theory and extremal combinatorics.

    Dr. Kothari is a recipient of the Presburger Award (2024), IIT Kanpur Young Alumnus Award (2023), Sloan Fellowship (2022), NSF Career Award (2021), and Simons Award for Graduate students in Theoretical Computer Science (2014).

  • Barna Saha, University of California San Diego

    Role of Structured Matrices in Fine-Grained Algorithm Design

    Fine-grained complexity attempts to precisely determine the time complexity of a problem and has emerged as a guide for algorithm design in recent times. Some of the central problems in fine-grain complexity deals with computation of distances. For example, computing all pairs shortest paths in a weighted graph, computing edit distance between two sequences or two trees, and computing distance of a sequence from a context free language. Many of these problems reduce to computation of matrix products over various algebraic structures, predominantly over the (min,+) semiring. Obtaining a truly subcubic algorithm for (min,+) product is one of the outstanding open questions in computer science.

    Interestingly many of the aforementioned distance computation problems have some additional structural properties. Specifically, when we perturb the inputs slightly, we do not expect a huge change in the output. This simple yet powerful observation has led to better algorithms for many problems for which we were able to improve the running time after several decades. This includes problems such as the Language Edit Distance, RNA folding, and Dyck Edit Distance. Indeed, this structure in the problem leads to matrices that have the Lipschitz property, and we gave the first truly subcubic time algorithm for computing (min,+) product over such Lipschitz matrices. Follow-up work by several researchers obtained improved bounds for monotone matrices, and for (min,+) convolution under similar structures leading to improved bounds for a series of optimization problems. These result in not just faster algorithms for exact computation but also for approximation algorithms. In particular, we show how fast (min,+) product computation over monotone matrices can lead to better additive approximation algorithms for computing all pairs shortest paths on unweighted undirected graphs, leading to improvements after twenty four years.

    Speaker Bio

    Barna Saha is an endowed chair professor at UC San Diego Computer Science and Engineering (CSE) and the Halıcıoğlu Data Science Institute (HDSI). Before joining UC San Diego, she was a tenured Associate Professor at UC Berkeley. Saha's primary research focus is on Theoretical Computer Science, specifically Algorithm Design. She is passionate about outreach and teaching, and seeing students succeed from all backgrounds. She is a recipient of the Presidential Early Career Award (PECASE)- the highest honor given by the White House to early career scientists, a Sloan fellowship, an NSF CAREER Award, and multiple industry & paper awards.

  • Georg Zetzsche<, MPI-SWS, Kaiserslautern

    Unboundedness Problems for Formal Languages

    Informally, unboundedness problems are decision problems that ask about the existence of infinitely many words (satisfying certain properties) in a formal language. For example: Is a given language infinite? Or: Does a given language have super-polynomial growth? These came into focus in recent years because of their connections to downward closure computation and separability problems. Although unboundedness problems may seem difficult at first, it turns out that there are techniques that are at the same time conceptually very simple, but also apply to a surprisingly wide variety of language classes. The talk will survey recent results (and techniques) concerning unboundedness problems.

    Speaker Bio

    Georg Zetzsche is a tenured faculty member at the Max Planck Institute for Software Systems (MPI-SWS) in Germany, where he leads the research group on Models of Computation. He obtained his PhD at University of Kaiserslautern in 2015. Before joining MPI-SWS in 2018, he was a postdoc at LSV (ENS Paris-Saclay) and IRIF (Université Paris-Diderot). His research interests lie in Automata Theory, Formal Languages, Logic, Decidability, Complexity, and Algorithmic Group Theory. He received the 2025 Salomaa Prize, a Starting Grant from the European Research Council (ERC), a Distinguished Dissertation Award from the European Association for Theoretical Computer Science (EATCS), and several best paper awards at ETAPS, ICALP, and POPL.

Workshops

Accepted Papers

Click here to view the list of accepted papers.

Conference Programme

Click here to view the conference programme.

Conference Proceedings

Click here to access the FSTTCS 2025 proceedings.

Programme Committee

Track A

Track B

Organizing Committee

Publicity Chairs

Local Information

Click here for details about local arrangements and information about registration.

Contact the organisers at fsttcs2025@goa.bits-pilani.ac.in for any further enquiries.

Registration

Click here to register for FSTTCS 2025 and workshops.