FSTTCS 2025
45th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
- Main Conference: December 17–19, 2025
- Venue: BITS Pilani, K K Birla Goa Campus
45th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
| Wednesday, December 17, 2025 | ||
| 0800 – 0900 | Registration | |
| 0900 – 0910 | Opening Remarks (LT1) | |
| 0910 – 1010 |
Invited Talk 1 Chair: Ruta Mehta Venue: LT1 |
|
|
Nicole Immorlica Agentic Markets |
||
| 1010 – 1030 | Break | |
| 1030 – 1130 |
Session A1 (Quantum Computing I) Chair: Akshay Bansal Venue: DLT8 |
Session B1 (Automata) Chair: Sunil Simon Venue: DLT10 |
|
Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon Marshall, Ronak Ramachandran PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements |
Ayaan Bedi and Karoliina Lehtinen Explorability in Pushdown Automata |
|
|
Elena Grigorescu, Vatsal Jha, Eric Samperton On the hardness of approximating distances of quantum codes |
Shibashis Guha, Anirban Majumdar, Prince Mathew and A V Sreejith Scalable Learning of One-Counter Automata via State-Merging Algorithms |
|
|
Erika Andersson, Akshay Bansal, James Peat, Jamie Sikora, Jiawei Wu Quantum protocols for Rabin oblivious transfer |
||
| 1130 – 1140 | Break | |
| 1140 – 1240 |
Session A2 (Algebraic & Boolean Complexity) Chair: Ramprasad Saptharishi Venue: DLT8 |
Session B2 (Probabilistic Systems ) Chair: S Akshay Venue: DLT10 |
|
Ramya C., Pratik Shastri On the Hardness of Order Finding and Equivalence Testing for ROABPs |
Laurent Bienvenu, Hugo Gimbert and Subin Pulari The Agafonov and Schnorr-Stimm theorems for probabilistic automata |
|
|
G. V. Sumukha Bharadwaj, S. Raja Randomized Black-Box PIT for Small Depth ±-Regular Non-commutative Circuits |
Ali Asadi, Léonard Brice, Krishnendu Chatterjee and K. S. Thejaswini ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games |
|
|
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff The Algebraic Cost of a Boolean Sum |
||
| 1240 – 1400 | Lunch | |
| 1400 – 1500 |
Invited Talk 2 Chair: Madhavan Mukund Venue: LT1 |
|
|
Parosh Aziz Abdulla Quantum Circuit Verification — A Potential Roadmap |
||
| 1500 – 1530 | Break | |
| 1530 – 1700 |
Session A3 (Clustering, Combinatorics & Algorithms) Chair: Arpit Agarwal Venue: DLT8 |
Session B3 (Complexity) Chair: Sreejith A V Venue: DLT10 |
|
Antonio Blanca, Zhezheng Song Cutoff for the Swendsen–Wang dynamics on the complete graph |
Anuj Dawar and Aidan Evans Characterizing NC1 with Typed Monoids |
|
|
Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, Ilya Volkovich Communication Complexity of Equality and Error-Correcting Codes |
Joey Chen, Bjoern Kjos-Hanssen, Ivan Koswara, Linus Richter and Frank Stephan Languages of Words of Low Automatic Complexity Are Hard to Compute |
|
|
Mathew Francis and Veena Prabhakarn Token Sliding Independent Set Reconfiguration on Block Graphs |
Donghyun Lim and Martin Ziegler Degrees of Second and Higher-Order Polynomials |
|
|
Deeparnab Chakrabarty, Jonathan Conroy, Ankita Sarkar Clustering in Varying Metrics |
||
| Thursday, December 18, 2025 | ||
| 0900 – 1000 |
Invited Talk 3 Chair: Subhajit Roy Venue: LT1 |
|
|
Bernd Finkbeiner Hyperproperties as Design Principles: Information-Flow Guided Synthesis and Explainability in Distributed Systems |
||
| 1000 – 1030 | Break | |
| 1030 – 1130 |
Session A4 (Graph Algorithms I) Chair: Jaikumar Radhakrishnan Venue: DLT8 |
Session B4 (Distributed Systems) Chair: Pascal Weil Venue: DLT10 |
|
Yashaswini Mathur, Prafullkumar Tale A Finer View of the Parameterized Landscape of Labeled Graph Contractions |
Amrita Suresh and Nobuko Yoshida Unreliability in Practical Subclasses of Communicating Systems |
|
|
Ariel Sapir, Liam Roditty Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms |
Nehul Jain and Bharat Adsul Distributed games with a central decision maker |
|
|
Dipan Dey, Telikepalli Kavitha Fault-Tolerant Approximate Distance Oracles with a Source Set |
||
| 1130 – 1140 | Break | |
| 1140 – 1240 |
Session A5 (Fair Division I) Chair: Arindam Khan Venue: DLT8 |
Session B5 (Graph Algebra and Hyperlogics) Chair: Paul Gastin Venue: DLT10 |
|
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui Simultaneous Fair Allocation of Indivisible Items Across Multiple Dimensions |
Marius Bozga, Radu Iosif and Florian Zuleger. Iterating Non-Aggregative Structure Compositions |
|
|
Umang Bhaskar, Yeshwant Pandit Extending EFX Allocations to Further Multi-Graph Classes |
Marek Chalupa, Thomas Henzinger and Ana Oliveira da Costa Flavors of Quantifiers in Hyperlogics |
|
|
Ajaykrishnan E. S., Daniel Lokshtanov Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division |
||
| 1240 – 1400 | Lunch | |
| 1400 – 1500 |
Invited Talk 4 Chair: Umang Bhaskar Venue: LT1 |
|
|
Barna Saha Role of Structured Matrices in Fine-Grained Algorithm Design |
||
| 1500 – 1530 | Break | |
| 1530 – 1650 |
Session A6 (Distributed / Networks) Chair: Nikhil Mande Venue: DLT8 |
Session B6 (Security and Resilience) Chair: Deepak D'Souza Venue: DLT10 |
|
Yi-Jun Chang, Yanyu Chen, Gopinath Mishra Overlay Network Construction: Improved Overall and Node-Wise Message Complexity |
Aniket Mishra and Abhishek Bichhawat Fall-through Semantics for Mitigating Timing-based Side Channel Leaks |
|
|
Thomas Erlebach, Naveen Garg, Sukriti Gupta, Amitabh Trehan Approximating Optimal Broadcast of Files in a Hose-Model Network |
Arif Ali Ap, Jasine Babu and Deepa Sara John A Correct by Construction Fault Tolerant Voter for Input Selection of a Control System |
|
|
Chaitanya Nalam, Thatchaphol Saranurak Finding small dijoins in transitive closure time |
RHPL panel discussion (DLT9) | |
|
Sina Kalantarzadeh, Nikhil Kumar Improved Upper Bounds on Multiflow–Multicut Gaps in Cactus Graphs |
||
| 1730 – 1830 | IARCS business meeting | |
| 1900 onwards | Conference Banquet | |
| Friday, December 19, 2025 | ||
| 0900 – 1000 |
Invited Talk 5 Chair: Meena Mahajan Venue: LT1 |
|
|
Pravesh K Kothari Algorithms from Combinatorics, Combinatorics from Algorithms |
||
| 1000 – 1030 | Break | |
| 1030 – 1130 |
Session A7 (Fair Division II – Matching) Chair: Ruta Mehta Venue: DLT8 |
Session B7 (Timed Systems) Chair: B. Srivathsan Venue: DLT10 |
|
Shayan Taherijam, Rohith Reddy Gangam, Vijay Vazirani Fair Rent Division: New Budget and Rent Constraints |
Gilles Geeraerts, Frédéric Herbreteau, Jean-François Raskin and Alexis Reynouard A Zone-Based Algorithm for Timed Parity Games |
|
|
Haricharan Balasundaram, J. B. Krishnashree, Girija Limaye, Meghana Nasre Stability Notions for Hospital Residents with Sizes |
Étienne André, Swen Jacobs, Shyam Karra and Ocan Sankur Parameterized Verification of Timed Networks with Clock Invariants |
|
|
Pallavi Jain, Palash Jha, Shubham Solanki Fairness and Efficiency in Two-Sided Matching Markets |
||
| 1130 – 1140 | Break | |
| 1140 – 1240 |
Session A8 (Graph Algorithms II: Structural & Parameterized) Chair: Pravesh Kothari Venue: DLT8 |
Session B8 (Games) Chair: K S Thejaswini Venue: DLT10 |
|
Archit Chauhan, Samir Datta, M. Praveen Parallel Complexity of Depth-First-Search and Maximal path |
Sophie Pinchinat and Rylo Ashmore Cat Herding Played on Infinite Trees |
|
|
Neeldhara Misra, Saraswati Nanoti A Characterization of Spartan Graphs and New Lower Bounds for Eternal Vertex Cover |
Dietmar Berwanger, Laurent Doyen and Thomas Soullard Synthesising Full-Information Protocols |
|
|
Satyabrata Jana, Soumen Mandal, Ashutosh Rai, Saket Saurabh Improved Approximation for Pathwidth One Vertex Deletion and Parameterized Complexity of its Variants |
||
| 1240 – 1400 | Lunch | |
| 1400 – 1500 |
Invited Talk 6 Chair: C Aiswarya Venue: LT1 |
|
|
Georg Zetzsche Unboundedness Problems for Formal Languages |
||
| 1500 – 1530 | Break | |
| 1530 – 1700 |
Session A9 (Quantum & Hardness II) Chair: Ramprasad Saptharishi Venue: DLT8 |
Session B9 (Logic) Chair: Prakash Saivasan Venue: DLT10 |
|
Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Kumar Sinhababu IPS Lower Bounds for Formulas and Sum of ROABPs |
Abhimanyu Choudhury and Meena Mahajan On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems |
|
|
Ziad Ismaili Alaoui, Nikhil Mande Hardness of Finding Kings and Strong Kings |
Ashwin Bhaskar and M. Praveen Regulating Synchronous Data Exchange to Meet Control Flow and Data Specifications |
|
|
Om Prakash, Vikram Sharma On the Roots of Independence Polynomial: Quantifying The Gap |
Alejandro Díaz-Caro and Octavio Malherbe Beyond Monads and Biproducts: A Uniform Interpretation of Parallelism in Intuitionistic Logic |
|
|
Rosemary Adejoh, Andreas Jakoby, Sneha Mohanty, Christian Schindelhauer How Pinball Wizards Simulate a Turing Machine |
||