FSTTCS 2022
42nd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
- Main Conference: December 18–20, 2022
- Pre-Conference Workshops: December 15–17, 2022
- Venue: IIT Madras
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 | ||
8:15 | REGISTRATION | |
9:00 – 9:15 | OPENING REMARKS | |
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 |