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 CHAIR: Sunil Simon |
|
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 CHAIR: Zeyu Guo |
Session B1 CHAIR: Dietmar Berwanger |
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 CHAIR: Venkatesh Raman |
Session B2 CHAIR: Rohit Chadha |
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 CHAIR: Telikepalli Kavitha |
|
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 CHAIR: Mrinal Kumar |
|
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 CHAIR: Ravishankar Krishnaswamy |
Session B3 CHAIR: Prakash Saivasan |
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 CHAIR: Saket Saurabh |
Session B4 CHAIR: S P Suresh |
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 – 1900 | Discussion session | |
1900 – 2000 | IARCS business meeting | |
2030 – 2130 |
Invited Talk 4 CHAIR: Meena Mahajan |
|
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 CHAIR: Telikepalli Kavitha |
Session B5 CHAIR: S Akshay |
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 CHAIR: Jaikumar Radhakrishnan |
Session B6 CHAIR: Anca Muscholl |
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 CHAIR: Madhavan Mukund |
|
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 CHAIR: Aditya Thakur |
|
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. |