FSTTCS 2020
40th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 14–18, 2020
Bits Pilani, K K Birla Goa Campus, Goa, India40th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 14–18, 2020
Bits Pilani, K K Birla Goa Campus, Goa, IndiaAll times are in Indian Standard Time (UTC + 5:30).
Tuesday, December 15, 2020  
1350 – 1400  Opening Remarks  
1400 – 1500  Invited Talk 1  
Joël Ouaknine Holonomic Techniques, Periods, and Decision Problems Holonomic techniques have deep roots going back to Wallis, Euler, and Gauss, and have evolved in modern times as an important subfield of computer algebra, thanks in large part to the work of Zeilberger and others over the past three decades. In this talk, I will give an overview of the area, and in particular will present a select survey of known and original results on decision problems for holonomic sequences and functions. (Holonomic sequences satisfy linear recurrence relations with polynomial coefficients, and holonomic functions satisfy linear differential equations with polynomial coefficients.) I will also discuss some surprising connections to the theory of periods and exponential periods, which are classical objects of study in algebraic geometry and number theory; in particular, I will relate the decidability of certain decision problems for holonomic sequences to deep conjectures about periods and exponential periods, notably those due to Kontsevich and Zagier. 

1500 – 1530  Break  
1530 – 1630  Session A1  Session B1 
Telikepalli Kavitha Mincost Popular Matchings 
Udi Boker, Denis Kuperberg, Karoliina Lehtinen and Michał Skrzypczak On the Succinctness of Alternating Parity GoodforGames Automata 

Lidiya Binti Khalil and Christian Konrad Constructing Large Matchings via Query Access to a Maximal Matching Oracle 
Sven Schewe Minimising GoodforGames Automata is NPComplete 

Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh and Meirav Zehav On the (Parameterized) Complexity of Almost Stable Marriage 
Orna Kupferman and Noam Shenwald Perspective Games with Notifications 

Aaron Bernstein and Aditi Dudeja Online Matching With Recourse: Random Edge Arrivals 
Nathalie Bertrand, Patricia Bouyer and Anirban Majumdar Synthesizing safe coalition strategies 

1630 – 1645  Break  
1645 – 1800  Session A2  Session B2 
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar and Sahil Singla Online Carpooling using Expander Decompositions 
Rishi Tulsyan, R Rekha and Deepak D'Souza Static Race Detection for RTOS Applications 

Erin Taylor, Pankaj K Agarwal, Kamesh Munagala, Emo Welzl and HsienChih Chang Clustering under Perturbation Stability in NearLinear Time 
Peter Chini and Prakash Saivasan A Framework for Consistency Algorithms 

Karthik Gajulapalli, James Liu, Tung Mai and Vijay Vazirani StabilityPreserving, TimeEfficient Mechanisms for School Choice in Two Rounds 
Michal Konecny, Florian Steinberg and Holger Thies Computable analysis for verified exact real computation 

Joshua Cook Size Bounds on Low Depth Circuits for Promise Majority 
Rebecca Bernemann, Benjamin Cabrera, Reiko Heckel and Barbara König Uncertainty Reasoning for Probabilistic Petri Nets via Bayesian Networks 

Shreyas Pai and Sriram Pemmaraju Connectivity Lower Bounds in Broadcast Congested Clique 
Paul Gastin, Sayan Mukherjee and B Srivathsan Reachability for updatable timed automata made faster and more effective 

1800 – 2030  Discussion session  
2030 – 2130  Invited Talk 2  
Yin Tat Lee Convex Optimization and Dynamic Data Structure In the last three years, there are many breakthroughs in optimization such as nearly quadratic time algorithms for bipartite matching, linear programming algorithms that are as fast as Ax = b. All of these algorithms are based on a careful combination of optimization techniques and dynamic data structures. In this talk, we will explain the framework underlying all the recent breakthroughs. Joint work with Jan van den Brand, Michael B. Cohen, Sally Dong, Haotian Jiang, Tarun Kathuria, Danupon Nanongkai, Swati Padmanabhan, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang, Sam Chiuwai Wong, Guanghao Ye, Qiuyi Zhang. 

Wednesday, December 16, 2020  
1400 – 1500  Invited Talk 3  
Amir Shpilka On Some Recent Advances in Algebraic Complexity Algebraic complexity is the field studying the intrinsic difficulty of algebraic problems in an algebraic model of computation, most notably arithmetic circuits. It is a very natural model of computation that attracted a large amount of research in the last few decades, partially due to its simplicity and elegance, but mostly because of its importance. Being a more structured model than Boolean circuits, one could hope that the fundamental problems of theoretical computer science, such as separating P from NP, deciding whether P = BPP and more, will be easier to solve for arithmetic circuits. In this talk I will give the basic definitions, explain the main questions and how they relate to their Boolean counterparts, and discuss what I view as promising approaches to tackling the most fundamental problems in the field. 

1500 – 1530  Break  
1530 – 1630  Session A3  Session B3 
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen, Eva Rotenberg and Teresa Anna Steiner String Indexing for Topk Close Consecutive Occurrences 
C Aiswarya and Paul Gastin Weighted Tiling Systems for Graphs: Evaluation Complexity 

Édouard Bonnet, Nicolas Grelier and Till Miltzow Maximum Clique in DiskLike Intersection Graphs 
Sören van der Wall and Roland Meyer On the Complexity of MultiPushdown Games 

Yash Khanna and Anand Louis Planted Models for the Densest kSubgraph Problem 
Manfred Droste, Sven Dziadek and Werner Kuich NivatTheorem and Logic for Weighted Pushdown Automata on Infinite Words 

Isolde Adler and Polly Fahey Faster Property Testers in a Variation of the Bounded Degree Model 
A R Balasubramanian Parameterized Complexity of Safety of Threshold Automata 

1630 – 1645  Break  
1645 – 1800  Session A4  Session B4 
Omer Wasim and Valerie King Fully dynamic sequential and distributed algorithms for MAXCUT 
Dominique Perrin and Andrew Ryzhikov The Degree of a Finite Set of Words 

Nikhil Mande and Swagato Sanyal On parity decision trees for Fouriersparse Boolean functions 
Paweł Parys HigherOrder Nonemptiness Step by Step 

Davide Bilò, Tobias Friedrich, Pascal Lenzner, Anna Melnichenko and Louise Molitor Fair Tree Connection Games with TopologyDependent Edge Cost 
Petra Wolf Synchronization under Dynamic Constraints 

Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz and Frank Sommer Colored Cut Games 
Henning Fernau and Petra Wolf Synchronization of Deterministic Visibly PushDown Automata 

Kishore Kothapalli, Shreyas Pai and Sriram Pemmaraju SampleandGather: Fast Ruling Set Algorithms in the LowMemory MPC Model 

1800 – 2030  Discussion session  
2030 – 2130  Invited Talk 4  
Albert Atserias Proofs of Soundness and Proof Search Let P be a sound proof system for propositional logic. For each CNF formula F, let SAT(F) be a CNF formula whose satisfying assignments are in 1to1 correspondence with those of F (e.g., F itself). For each integer s, let REF(F, s) be a CNF formula whose satisfying assignments are in 1to1 correspondence with the Prefutations of F of length s. Since P is sound, it is obvious that the conjunction formula SAT(F) & REF(F,s) is unsatisfiable for any choice of F and s. It has been long known that, for many natural proof systems P and for the most natural formalizations of the formulas SAT and REF, the unsatisfiability of SAT(F) & REF(F,s) can be established by a short refutation. In addition, for most P, these short refutations live in the proof system P itself. This is the case for all Frege proof systems. In contrast it was known since the early 2000’s that Resolution proofs of Resolution’s soundness statements must have superpolynomial length. In this talk I will explain how the soundness formulas for a proof system P relate to the computational complexity of the proof search problem for P. In particular, I will explain how such formulas are used in the recent proof that the problem of approximating the minimum prooflength for Resolution is NPhard (AtseriasMüller 2019). Besides playing a key role in this hardness of approximation result, the renewed interest in the soundness formulas led to a complete answer to the question whether Resolution has subexponentiallength proofs of its own soundness statements (Garlík 2019). 

Thursday, December 17, 2020  
1400 – 1515  Session A5  Session B5 
Dana Moshkovitz, Justin Oh and David Zuckerman Randomness Efficient Noise Stability and Generalized Small Bias Sets 
Christel Baier, Florian Funke, Simon Jantsch, Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, Amaury Pouly, David Purser and Markus A Whiteland Reachability in Dynamical Systems with Rounding 

Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal and Amit Kumar On Sampling Based Algorithms for kMeans 
Oscar Darwin and Stefan Kiefer Equivalence of Hidden Markov Models with Continuous Observations 

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl and Gaurav Sood Hard QBFs for Merge Resolution 
Stefan Kiefer and Qiyi Tang Comparing Labelled Markov Decision Processes 

Prantar Ghosh New Verification Schemes for FrequencyBased Functions on Data Streams 
Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan and Ocan Sankur Dynamic Network Congestion Games 

Alexander Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni and Minshen Zhu Locally Decodable/Correctable Codes for Insertions and Deletions 

1515 – 1530  Break  
1530 – 1630  Session A6  Session B6 
Pratibha Choudhary, Daniel Lokshtanov, Lawqueen Kanesh, Fahad Panolan and Saket Saurabh Parameterized Complexity of Feedback Vertex Sets on Hypergraphs 
Emmanuel Filiot, Christof Löding and Sarah Winter Synthesis from Weighted Specifications with Partial Domains over Finite Words 

Niranka Banerjee, Venkatesh Raman and Saket Saurabh Optimal Output Sensitive Fault Tolerant Cuts 
Stefan Haar, Serge Haddad, Stefan Schwoon and Lina Ye Active Prediction for Discrete Event Systems 

Pavel Dvořák and Bruno Loff Lower Bounds for Semiadaptive Data Structures via Corruption 
Shaull Almagor Process Symmetry in Probabilistic Transducers 

Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira and Petra Wolf Width Notions for OrderingRelated Problems 
M Praveen What You Must Remember When Transforming Datawords (Extended Abstract) 

1630 – 1900  Discussion session  
1900 – 2000  Invited Talk 5  
Sanjeev Arora The quest for mathematical understanding of deep learning Deep learning has transformed Machine Learning and Artificial Intelligence in the past decade. It raises fundamental questions for mathematics and theory of computer science, since it relies upon solving largescale nonconvex problems via gradient descent and its variants. This talk will be an introduction to mathematical questions raised by deep learning, and some partial understanding obtained in recent years. 

2000 – 2030  Break  
2030 – 2130  Invited Talk 6  
Sanjit A Seshia Algorithmic Improvisation for Dependable Intelligent Autonomy Algorithmic Improvisation, also called control improvisation or controlled improvisation, is a new framework for automatically synthesizing systems with specified random but controllable behavior. In this talk, I will present the theory of algorithmic improvisation and show how it can be used in a wide variety of applications where randomness can provide variety, robustness, or unpredictability while guaranteeing safety or other properties. Applications demonstrated to date include robotic surveillance, software fuzz testing, music improvisation, human modeling, generating test cases for simulating cyberphysical systems, and generation of synthetic data sets to train and test machine learning algorithms. In this talk, I will particularly focus on applications to the design of intelligent autonomous systems, presenting work on randomized planning for robotics and a domainspecific probabilistic programming language for the design and analysis of learningbased autonomous systems. 