Skip to main content


42nd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science

All times are in Indian Standard Time (UTC + 5:30).

Session venues:

Sunday, December 18, 2022
Invited Talk 1
CHAIR: Venkatesan Guruswami
9:15 – 10:15 Anupam Gupta
Algorithms for Uncertain Environments: Going Beyond the Worst Case
10:15 – 10:30 SHORT BREAK
Session 1 (A11)   Matchings
CHAIR: Rohit Gurjar
Session 1 (B11)   Infinite Words
CHAIR: Amaldev Manuel
10:30 – 10:55 Rohith Reddy Gangam, Tung Mai, Nitya Raju, Vijay V. Vazirani
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications
Rüdiger Ehlers, Sven Schewe
Natural Colors of Infinite Words
10:55 – 11:20 Telikepalli Kavitha
Stable Matchings with One-Sided Ties and Approximate Popularity
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, Martin Zimmermann
Parikh Automata over Infinite Words
11:20 – 11:50 COFFEE BREAK
Session 2 (A12)  Games
CHAIR: Rishi Saket
Session 2 (B12)   Ambiguity
CHAIR: Aiswarya Cyriac
11:50 – 12:15 Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, Chao Xu
Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
Olivier Carton
Ambiguity through the lens of measure theory
12:15 – 12:40 Vijay V. Vazirani
New Characterizations of Core Imputations of Matching and b-Matching Games (Extended Abstract)
Florent Koechlin
New analytic techniques for proving the inherent ambiguity of context-free languages
12:40 – 14:00 LUNCH BREAK
Invited Talk 2
CHAIR: Prahladh Harsha
14:00 – 15:00 Irit Dinur
Expanders in Higher Dimensions
15:00 – 15:15 SHORT BREAK
Session 3 (A13)   Complexity
CHAIR: Raghavendra Rao B.V.
Session 3 (B13)   Game Theory
CHAIR: B Srivathsan
15:15 – 15:40 Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, Vladimir Lysikov
Degree-restricted strength decompositions and algebraic branching programs
Guy Avni, Suman Sadhukhan
Computing Threshold Budgets in Discrete Bidding Games
15:40 – 16:05 Pascal Koiran, Subhayan Saha
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms
Dylan Bellier, Sophie Pinchinat, François Schwarzentruber
Dependency Matrices for Multiplayer Strategic Dependencies
16:05 – 16:35 COFFEE BREAK
Session 4 (A14)  Complexity
CHAIR: Nithin Varma
Session 4 (B14)  TBA
CHAIR: Nikhil Balaji
16:35 – 17:00 Joshua Cook
More Verifier Efficient Interactive Protocols For Bounded Space
Ali Ahmadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi, Đorđe Žikelić
Algorithms and Hardness Results for Computing Cores of Markov Chains
17:00 – 17:25 Gianfranco Bilardi, Lorenzo De Stefani
The DAG Visit approach for Pebbling and I/O Lower Bounds
Mohit Garg, Suneel Sarswat
The Design and Regulation of Exchanges: A Formal Approach
18:00 – 19:30 Cultural Progam
Monday, December 19, 2022
Invited Talk 3
CHAIR: Anuj Dawar
09:15 – 10:15 Patricia Bouyer
The True Colors of Memory: A Tour of Chromatic Memory Strategies in Zero-Sum Games on Graphs
10:15 – 10:30 SHORT BREAK
Session 5 (A21)  Graph Algorithms
CHAIR: Saket Saurabh
Session 5 (B21)  Formal Languages
CHAIR: Deepak D'Souza
10:30 – 10:55 Jasine Babu, R. Krithika, Deepak Rajendraprasad
Packing Arc-Disjoint 4-Cycles in Oriented Graphs
Bernd Finkbeiner, Noemi Passing
Synthesizing Dominant Strategies for Liveness
10:55 – 11:20 Utkarsh Joshi, Saladi Rahul, Josson Joe Thoppil
A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs
Moses Ganardi, Louis Jachiet, Markus Lohrey, Thomas Schwentick
Low-Latency Sliding Window Algorithms for Formal Languages
11:20 – 11:50 COFFEE BREAK
Session 6 (A22)  Polynomial Factorization
CHAIR: Arkadev Chattopadhyay
Session 6 (B22)  Geometry
CHAIR: Minati De
11:50 – 12:15 Pranav Bisht, Nitin Saxena
Derandomization via symmetric polytopes: Poly-time factorization of certain sparse polynomials
Hee-Kap Ahn, Sang Won Bae, Chung Jaehoon, Chan-Su Shin and Sang Duk Yoon
Inscribing or Circumscribing a Histogon to a Convex Polygon
12:15 – 12:40 Pranav Bisht, Ilya Volkovich
On Solving Sparse Polynomial Factorization Related Problems
Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas C. Nandy, Alex Pahlow
Half-Guarding Weakly-Visible Polygons and Terrains
12:40 – 14:00 LUNCH BREAK
Invited Talk 4
CHAIR: Madhavan Mukund
14:00 – 15:00 Akash Lal
Industrial-Strength Controlled Concurrency Testing
15:00 – 15:30 COFFEE BREAK
Session 7 (A23)   Approximation Algorithms
CHAIR: Rakesh Venkat
Session 7 (B23)   Logic and Synthesis
CHAIR: Pascal Weil
15:30 – 15:55 Oded Lachish, Felix Reidl, Chhaya Trehan
When you come at the king you best not miss
Abhishek De, Farzad Jafarrahmani, Alexis Saurin
Phase semantics for linear logic with least and greatest fixed points
15:55 – 16:20 Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker, Jakub Svoboda
Complexity of Spatial Games
Orna Kupferman, Ofer Leshkowitz
Synthesis of Privacy-Preserving Systems
16:20 – 16:45 Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale, Gaurav Viramgami
Romeo and Juliet Meeting in Forest Like Regions
Thomas Place, Marc Zeitoun
A generic polynomial time approach to separation by first-order logic without quantifier alternation
16:45 – 17:15 COFFEE BREAK
17:15 – 18:30 Business Meeting @ TTJ Auditorium, ICSR Building, IITM
19:30 – 22:00 Banquet @ Le Meridian, Alandur, Chennai.
Tuesday, December 20, 2022
Invited Talk 5
CHAIR: Venkatesan Guruswami
09:15 – 10:15 Rahul Santhanam
Why MCSP is a More Important Problem than SAT
10:15 – 10:30 SHORT BREAK
Session 8 (A31)   Arithmetic Circuit Complexity
CHAIR: Meena Mahajan
Session 8 (B31) Geometry
CHAIR: Venkatesan Guruswami
10:30 – 10:55 Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay
Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product
Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
10:55 – 11:20 Radu Curticapean, Nutan Limaye, Srikanth Srinivasan
On the VNP-hardness of Some Monomial Symmetric Polynomials
Minati De, Saksham Jain, Sarat Varma Kallepalli, Satyam Singh
Online Piercing of Geometric Objects
11:20 – 11:50 COFFEE BREAK
Session 9 (A32)  Query Complexity
CHAIR: Olaf Beyersdorff
Session 9 (B32)  Game Theory
CHAIR: Shibashis Guha
11:50 – 12:15 Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Counting and Sampling from Substructures using Linear Algebraic Queries
Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan, Ocan Sankur
Semilinear Representations for Series-Parallel Atomic Congestion Games
12:15 – 12:40 Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Benjamin Bordais, Patricia Bouyer, Stéphane Le Roux
Playing (Almost-)Optimally in Concurrent Büchi and co-Büchi Games
12:40 – 13:05 Ramita Maharjan, Thomas Watson
Complexity of Fault Tolerant Query Complexity
K. S. Thejaswini, Pierre Ohlmann, Marcin Jurdziński
A technique to speed up symmetric attractor-based algorithms for parity games
13:05 – 14:30 Lunch break