FSTTCS 2023
43rd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
- Main Conference: December 18–20, 2023
- Venue: IIIT Hyderabad
43rd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
| Monday, December 18, 2023 | ||
| 0900 – 1000 |
Invited Talk 1 CHAIR: Srikanth Srinivasan |
|
|
Nisheeth Vishnoi Algorithms in the Presence of Biased Inputs |
||
| 1000 – 1030 | Break | |
| 1030 – 1130 |
Session A1 CHAIR: Neeldhara Misra |
Session B1 CHAIR: Supratik Chakraborty |
|
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Ramanujan M. Sridharan and Saket Saurabh FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less |
Wojciech Czerwinski, Maciej Debski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michal Skrzypczak, Frank Stephan and Christopher Tan Languages given by Finite Automata over the Unary Alphabet |
|
|
R. Krithika, Kutty Malu V K, Roohani Sharma and Prafullkumar Tale Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction |
Yoav Feinstein and Orna Kupferman Monotonicity Characterizations of Regular Languages |
|
| 1130 – 1145 | Break | |
| 1145 – 1245 |
Session A2 CHAIR: Umang Bhaskar |
Session B2 CHAIR: Dietmar Berwanger |
|
Harmender Gahlawat and Meirav Zehavi Parameterized Complexity of Incomplete Connected Fair Division |
Dietrich Kuske A class of rational trace relations closed under composition |
|
|
Aniket Murhekar and Eklavya Sharma Nash Equilibria of Two-Player Matrix Games Repeated Until Collision |
Debajyoti Bera and Tharrmashastha Sapv A Generalized Quantum Branching Program |
|
| 1245 – 1400 | Lunch | |
| 1400 – 1500 |
Invited Talk 2 CHAIR: Patricia Bouyer |
|
|
Thomas Brihaye Reachability Games and Friends: A Journey Through the Lens of Memory and Complexity |
||
| 1500 – 1530 | Break | |
| 1530 – 1700 |
Session A3 CHAIR: Nikhil Mande |
Session B3 CHAIR: Prakash Saivasan |
|
Pranav Bisht, Nikhil Gupta and Ilya Volkovich Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae |
Chris Köcher and Georg Zetzsche Regular Separators for VASS Coverability Languages |
|
|
Ulysse Lechine Revisiting Mulmuley: Simple proof that maxflow is not in the algebraic version of NC |
Ismaël Jecker, Wojciech Czerwiński, Jérôme Leroux, Sławomir Lasota and Łukasz Orlikowski New Lower Bounds for Reachability in Vector Addition Systems |
|
|
Prerona Chatterjee, Kshitij Gajjar and Anamay Tengse Monotone Classes Beyond VNP |
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman, Filip Mazowiecki and Henry Sinclair-Banks Acyclic Petri and Workflow Nets with Resets |
|
| Tuesday, December 19, 2023 | ||
| 0900 – 1000 |
Invited Talk 3 CHAIR: Piyush Srivastava |
|
|
Leonard Schulman Computational and Information-Theoretic Questions from Causal Inference |
||
| 1000 – 1030 | Break | |
| 1030 – 1130 |
Session A4 CHAIR: Karteek Sreenivasaiah |
Session B4 CHAIR: B Srivathsan |
|
Rahul Chugh, Supartha Podder and Swagato Sanyal Decision Tree Complexity versus Block Sensitivity and Degree |
Eugene Asarin, Aldric Degorre, Catalin Dima and Bernardo Jacobo Inclán Bandwidth of Timed Automata: 3 Classes |
|
|
Nikhil Mande, Manaswi Paraashar and Nitin Saurabh Randomized and quantum query complexities of finding a king in a tournament |
Léo Henry, Blaise Genest and Alexandre Drewery Reinforcement Planning for effective epsilon-optimal policies in dense time with discontinuities |
|
| 1130 – 1145 | Break | |
| 1145 – 1245 |
Session A5 CHAIR: Sujit Gujar |
Session B5 CHAIR: Abhisekh Sankaran |
|
Vijay Vazirani Towards a Practical, Budget-Oblivious Algorithm for the Adwords Problem under Small Bids |
Abhimanyu Choudhury and Meena Mahajan Dependency schemes in CDCL-based QBF solving: a proof-theoretic study |
|
|
Arghya Chakraborty and Rahul Vaze Online facility location with weights and congestion |
Anupam Das, Abhishek De and Alexis Saurin Comparing infinitary systems for linear logic with fixed points |
|
| 1245 – 1400 | Lunch | |
| 1400 – 1500 |
Invited Talk 4 CHAIR: Deepak D'Souza |
|
|
Sharon Shoham From Concept Learning to SAT-Based Invariant Inference |
||
| 1500 – 1530 | Break | |
| 1530 – 1630 |
Session A6 CHAIR: N R Aravind |
Session B6 CHAIR: Aiswarya C |
|
Telikepalli Kavitha and Kazuhisa Makino Popular Maximum Matchings in the Many-to-Many Setting |
Alain Finkel, Krishna S, Khushraj Madnani, Rupak Majumdar and Georg Zetzsche Counter Machines With Infrequent Reversals |
|
|
Amir Abboud, Seri Khoury, Oree Leibowitz and Ron Safier Listing 4-Cycles |
Prince Mathew, Vincent Penelle, Prakash Saivasan and A V Sreejith Weighted one-deterministic-counter automata |
|
| 1700 – 1800 | IARCS business meeting | |
| 1900 onwards | Conference Banquet, Taramati Baradari Resort | |
| Wednesday, December 20, 2023 | ||
| 0900 – 1000 |
Invited Talk 5 CHAIR: Rishi Saket |
|
|
Prasad Raghavendra On Measuring Average Case Complexity via Sum-Of-Squares Degree |
||
| 1000 – 1030 | Break | |
| 1030 – 1130 |
Session A7 CHAIR: Telikepalli Kavitha |
Session B7 CHAIR: Thomas Brihaye |
|
Diptarka Chakraborty and Yan Hong Yao Alvin Approximate Maximum Rank Aggregation: Beyond the Worst-Case |
Irmak Saglam and Anne-Kathrin Schmuck Solving Odd-Fair Parity Games |
|
|
Jacques Dark, Adithya Diddapur and Christian Konrad Interval Selection in Data Streams: Weighted Intervals and the Insertion-deletion Setting |
Mihir Vahanwala Robust Positivity Problems for Linear Recurrence Sequences |
|
| 1130 – 1145 | Break | |
| 1145 – 1245 |
Session A8 CHAIR: Nitin Saurabh |
Session B8 CHAIR: Shibashis Guha |
|
Venkatesan Guruswami and Rishi Saket Hardness of Learning Boolean Functions from Label Proportions |
Shaull Almagor, Daniel Assa and Udi Boker Synchronized CTL over One-Counter Automata |
|
|
Dieter van Melkebeek and Nicollas Mocelin Sdroievski Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols |
Ashwin Bhaskar and M. Praveen Constraint LTL with Remote Access |
|
| 1245 – 1400 | Lunch | |
| 1400 – 1500 |
Session A9 CHAIR: Meena Mahajan |
|
|
Olivier Lalonde, Nikhil Mande and Ronald de Wolf Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error |
||
|
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan and Sruthi Sekar Bounded Simultaneous Messages |
||
| 1500 – 1530 | Break | |
| 1530 – 1630 |
Session A10 CHAIR: Aniket Basu Roy |
|
|
Jishnu Roychoudhury and Jatin Yadav An optimal algorithm for sorting in trees |
||
|
Ramanujan M. S and Akanksha Agrawal Approximately Interpolating Between Uniformly and Non-uniformly Polynomial Kernels |
||