Skip to main content


41st IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science

December 15–17, 2021

Virtual Conference due to the Covid situation

All times are in Indian Standard Time (IST). Use this site to convert from IST to your local time. Here is a table with the conference start time converted to Beijing/Chicago/Paris time.

Wednesday, December 15, 2021
1400 – 1500 Invited Talk 1
CHAIR: Chandra Chekuri
Rachel Lin
Indistinguishability Obfuscation from Well-Founded Assumptions
1500 – 1530 Break
1530 – 1620 Session A1
CHAIR: Swagato Sanyal
Session B1
CHAIR: S Akshay
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala and Ilya Volkovich
One-way Functions and a Conditional Variant of MKTP
Raveendra Holla, Nabarun Deka and Deepak D'Souza
On the Expressive Equivalence of TPTL in the Pointwise and Continuous Semantics
Yang Du and Ilya Volkovich
Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function
Benedikt Bollig, Arnaud Sangnier and Olivier Stietel
Local First-Order Logic with Two Data Values
Akhil Jalan and Dana Moshkovitz
Near-Optimal Cayley Expanders for Abelian Groups
Bartosz Bednarczyk, Maja Orłowska, Anna Pacanowska and Tony Tan
On Classical Decidable Logics extended with Percentage Quantifiers and Arithmetics
Jaikumar Radhakrishnan and Aravind Srinivasan
Property B: Two-coloring non-uniform hypergraphs
Jonni Virtema, Jana Hofmann, Bernd Finkbeiner, Juha Kontinen and Fan Yang
Linear-time Temporal Logic with Team Semantics: Expressivity and Complexity
1620 – 1645 Break
1645 – 1745 Session A2
CHAIR: Sudeshna Kolay
Session B2
CHAIR: Andrzej Murawski
Xin Li and Yu Zheng
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
Raúl Gutiérrez, Salvador Lucas and Miguel Vítores
Confluence of Conditional Rewriting in Logic Form
Chetan Gupta, Rahul Jain and Raghunath Tewari
Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
Kentaro Kikuchi and Takahito Aoto
Simple Derivation Systems for Proving Sufficient Completeness of Non-terminating Term Rewriting Systems
Fedor Fomin, Petr Golovach, Tanmay Inamdar and Saket Saurabh
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
Dongho Lee, Valentin Perrelle and Benoît Valiron
Concrete Categorical Model of a Quantum Circuit Description Language with Measurement
Diptarka Chakraborty, Kshitij Gajjar and Agastya Vibhuti Jha
Approximating the Center Ranking under Ulam
Filippo Bonchi, Alessandro Di Giorgio and Pawel Sobocinski
Diagrammatic Polyhedral Algebra
Diptarka Chakraborty, Debarati Das and Robert Krauthgamer
Approximate Trace Reconstruction via Median String (in Average-Case)
1930 – 2030 Invited Talk 2
CHAIR: Anuj Dawar
Leslie Goldberg
Approximately Counting Graph Homomorphisms and Retractions
Thursday, December 16, 2021
1400 – 1500 Invited Talk 3
CHAIR: Rupak Majumdar
Javier Esparza
State Complexity of Population Protocols
1500 – 1530 Break
1530 – 1620 Session A3
CHAIR: Rahul Saladi
Session B3
CHAIR: M Praveen
Georgiy Klimenko and Benjamin Raichel
Fast and Exact Convex Hull Simplification
A R Balasubramanian
Complexity of Coverability in Bounded Path Broadcast Networks
Taekang Eom, Seungjun Lee and Hee-Kap Ahn
Largest similar copies of convex polygons in polygonal domains
Sławomir Lasota and Mohnish Pattathurajan
Parikh images of register automata
Floyd Zweydinger, Andre Esser and Robert Kübler
A Faster Algorithm for Finding Closest Pairs in Hamming Metric
S Akshay, Blaise Genest, Loic Helouet, Krishna S and Sparsa Roychowdhury
Resilience of Timed Systems
Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal and Sandeep Sen
Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings
Nicolas Bedon
Branching Automata and Poset Automata
1620 – 1645 Break
1645 – 1745 Session A4
CHAIR: Sushmita Gupta
Session B4
CHAIR: Georg Zetzsche
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma and Raghunath Tewari
Reachability and Matching in Single Crossing Minor Free Graphs
Liam Jordon and Philippe Moser
Normal Sequences with Non-Maximal Automatic 2 Complexity
Suryajith Chillara
Functional lower bounds for restricted arithmetic circuits of depth four
Christopher Hugenroth
Separating Regular Languages over Infinite Words with respect to the Wagner hierarchy
Arkadev Chattopadhyay, Ankit Garg and Suhail Sherif
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismael Jecker, Mateus De Oliveira Oliveira and Petra Wolf
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
Yogesh Dahiya and Meena Mahajan
On (Simple) Decision Tree Rank
Karoliina Lehtinen and Udi Boker
Good for Gameness vs. History Determinism in Quantitative Automata
Sourav Chakraborty, Nikhil S Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar and Swagato Sanyal
Tight Chang's-lemma-type bounds for Boolean functions
1800 – 1900 IARCS business meeting
1930 – 2030 Invited Talk 4
CHAIR: Meena Mahajan
Scott Aaronson
BQP After 28 Years
Friday, December 17, 2021
1400 – 1500 Session A5
CHAIR: Ravishankar Krishnaswamy
Eklavya Sharma
Harmonic Algorithms for Packing d-dimensional Cuboids Into Bins
Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon and Andreas Wiese
Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
Susanne Albers and Maximilian Janke
Scheduling under random-order arrival
Daniel Lokshtanov, Saket Saurabh, Subhash Suri and Jie Xue
An ETH-tight Algorithm for Multi-Team Formation
Sylvia Boyd, Joe Cheriyan, Arash Haddadan and Sharat Ibrahimpur
Approximation Algorithms for Flexible Graph Connectivity
1500 – 1525 Break
1525 – 1615 Session A6
CHAIR: Keerti Choudhary
Session B5
CHAIR: Mikołaj Bojańczyk
Daniel Lokshtanov and Vaishali Surianarayanan
Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable
Stefan Kiefer and Qiyi Tang
Approximate Bisimulation Minimisation
Telikepalli Kavitha
Matchings, Critical Nodes, and Popular Solutions
Krishnendu Chatterjee, Rasmus Ibsen-Jensen and Andreas Pavlogiannis
Quantitative Verification on Product Graphs of Small Treewidth
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan and Ankita Sarkar
Popular Matchings in the Hospital-Residents Problem with Two-sided Lower Quotas
Benjamin Bordais, Patricia Bouyer and Stéphane Le Roux
From Local to Global Determinacy in Concurrent Graph Games
Jugal Garg, Pooja Kulkarni and Aniket Murhekar
On Fair and Efficient Allocations of Indivisible Public Goods
Emmanuel Filiot and Sarah Winter
Synthesizing computable functions from rational specifications over infinite words
1615 – 1640 Break
1640 – 1740 Invited Talk 5
CHAIR: Sunil Simon
Rahul Savani
The Complexity of Gradient Descent