Skip to main content

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, India

All 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
Min-cost Popular Matchings
Udi Boker, Denis Kuperberg, Karoliina Lehtinen and Michał Skrzypczak
On the Succinctness of Alternating Parity Good-for-Games Automata
Lidiya Binti Khalil and Christian Konrad
Constructing Large Matchings via Query Access to a Maximal Matching Oracle
Sven Schewe
Minimising Good-for-Games Automata is NP-Complete
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 Hsien-Chih Chang
Clustering under Perturbation Stability in Near-Linear Time
Peter Chini and Prakash Saivasan
A Framework for Consistency Algorithms
Karthik Gajulapalli, James Liu, Tung Mai and Vijay Vazirani
Stability-Preserving, Time-Efficient 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 Chiu-wai 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 Top-k 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 Disk-Like Intersection Graphs
Sören van der Wall and Roland Meyer
On the Complexity of Multi-Pushdown Games
Yash Khanna and Anand Louis
Planted Models for the Densest k-Subgraph Problem
Manfred Droste, Sven Dziadek and Werner Kuich
Nivat-Theorem 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 MAX-CUT
Dominique Perrin and Andrew Ryzhikov
The Degree of a Finite Set of Words
Nikhil Mande and Swagato Sanyal
On parity decision trees for Fourier-sparse Boolean functions
Paweł Parys
Higher-Order Nonemptiness Step by Step
Davide Bilò, Tobias Friedrich, Pascal Lenzner, Anna Melnichenko and Louise Molitor
Fair Tree Connection Games with Topology-Dependent 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 Push-Down Automata
Kishore Kothapalli, Shreyas Pai and Sriram Pemmaraju
Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory 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 1-to-1 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 1-to-1 correspondence with the P-refutations 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 proof-length for Resolution is NP-hard (Atserias-Mü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 subexponential-length 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 k-Means
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 Frequency-Based 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 Semi-adaptive 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 Ordering-Related 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 large-scale 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 cyber-physical 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 domain-specific probabilistic programming language for the design and analysis of learning-based autonomous systems.