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
Ziad Ismaili Alaoui and Nikhil Mande
Hardness of Finding Kings and Strong Kings
Nehul Jain and Bharat Adsul
Distributed games with a central decision maker
Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon Marhsall and Ronak Ramachandran
PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas and Amir Yehudayoff
The Algebraic Cost of a Boolean Sum
G V Sumukha Bharadwaj and S Raja
Randomized Black-Box PIT for Small Depth +−Regular Non-commutative Circuits
Yi-Jun Chang, Yanyu Chen and Gopinath Mishra
Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
Shayan Taherijam, Rohith Reddy Gangam and Vijay Vazirani
Fair Rent Division: New Budget and Rent Constraints
Joey Chen, Bjoern Kjos-Hanssen, Ivan Koswara, Linus Richter and Frank Stephan
Languages of Words of Low Automatic Complexity Are Hard to Compute
Yasushi Kawase, Bodhayan Roy and Mohammad Azharuddin Sanpui
Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions
Dietmar Berwanger, Laurent Doyen and Thomas Soullard
Synthesising Full-Information Protocols
Chaitanya Nalam and Thatchaphol Saranurak
Finding small dijoins in transitive closure time.
Gilles Geeraerts, Frédéric Herbreteau, Jean-François Raskin and Alexis Reynouard
A Zone-Based Algorithm for Timed Parity Games
Sophie Pinchinat and Rylo Ashmore
Cat Herding Played on Infinite Trees
Amrita Suresh and Nobuko Yoshida
Unreliability in Practical Subclasses of Communicating Systems
Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay and Amit Sinhababu
IPS Lower Bounds for Formulas and Sum of ROABPs
Donghyun Lim and Martin Ziegler
Degrees of Second and Higher-Order Polynomials
Laurent Bienvenu, Hugo Gimbert and Subin Pulari
The Agafonov and Schnorr-Stimm theorems for probabilistic automata
Étienne André, Swen Jacobs, Shyam Karra and Ocan Sankur
Parameterized Verification of Timed Networks with Clock Invariants
Antonio Blanca and Zhezheng Song
Cutoff for the Swendsen–Wang dynamics on the complete graph
Alejandro Díaz-Caro and Octavio Malherbe
Beyond Monads and Biproducts: A Uniform Interpretation of Parallelism in Intuitionistic Logic
Haricharan Balasundaram, J B Krishnashree, Girija Limaye and Meghana Nasre
Stability Notions for Hospital Residents with Sizes
Archit Chauhan, Samir Datta and M. Praveen
Parallel Complexity of Depth-First-Search and Maximal path
Ramya C. and Pratik Shastri
On the Hardness of Order Finding and Equivalence Testing for ROABPs
Umang Bhaskar and Yeshwant Pandit
Extending EFX Allocations to Further Multi-Graph Classes
Mathew Francis and Veena Prabhakaran
Token sliding independent set reconfiguration on block graphs
Erika Andersson, Akshay Bansal, James Peat, Jamie Sikora and Jiawei Wu
Quantum protocols for Rabin oblivious transfer
Pallavi Jain, Palash Jha and Shubham Solanki
Fairness and Efficiency in Two-Sided Matching Markets
Ayaan Bedi and Karoliina Lehtinen
Explorability in Pushdown Automata
Elena Grigorescu, Vatsal Jha and Eric Samperton
On the hardness of approximating distances of quantum codes
Yashaswini Mathur and Prafullkumar Tale
A Finer View of the Parameterized Landscape of Labeled Graph Contractions
Rosemary Adejoh, Andreas Jakoby, Sneha Mohanty and Christian Schindelhauer
How Pinball Wizards Simulate a Turing Machine
Ariel Sapir and Liam Roditty
Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
Ali Asadi, Léonard Brice, Krishnendu Chatterjee and K. S. Thejaswini
ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
Neeldhara Misra and Saraswati Nanoti
A Characterization of Spartan Graphs and New Lower Bounds for Eternal Vertex Cover
Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior and Ilya Volkovich
Communication Complexity of Equality and Error-Correcting Codes
Marius Bozga, Radu Iosif and Florian Zuleger
Iterating Non-Aggregative Structure Compositions
Arif Ali Ap, Jasine Babu and Deepa Sara John
A Correct by Construction Fault Tolerant Voter for Input Selection of a Control System
Anuj Dawar and Aidan Evans
Characterizing NC1 with Typed Monoids
Deeparnab Chakrabarty, Jonathan Conroy and Ankita Sarkar
Clustering in Varying Metrics
Thomas Erlebach, Naveen Garg, Sukriti Gupta and Amitabh Trehan
Approximating Optimal Broadcast of Files in a Hose-Model Network
Dipan Dey and Telikepalli Kavitha
Fault-Tolerant Approximate Distance Oracles with a Source Set
Sina Kalantarzadeh and Nikhil Kumar
Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs
Marek Chalupa, Thomas Henzinger and Ana Oliveira da Costa
Flavors of Quantifiers in Hyperlogics
Satyabrata Jana, Soumen Mandal, Ashutosh Rai and Saket Saurabh
Improved Approximation for Pathwidth One Vertex Deletion and Parameterized Complexity of its Variants
Ashwin Bhaskar and M. Praveen
Regulating Synchronous Data Exchange to Meet Control Flow and Data Specifications
Ajaykrishnan E S and Daniel Lokshtanov
Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division
Shibashis Guha, Anirban Majumdar, Prince Mathew and A V Sreejith
Scalable Learning of One-Counter Automata via State-Merging Algorithms
Om Prakash and Vikram Sharma
On The Roots of Independence Polynomial: Quantifying The Gap
Aniket Mishra and Abhishek Bichhawat
Fall-through Semantics for Mitigating Timing-based Side Channel Leaks
Abhimanyu Choudhury and Meena Mahajan
On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems