FSTTCS 2020 December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference)

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)



Nitin Saxena and Sunil Simon (Eds.)
ISBN 978-3-95977-174-0, LIPICS Vol. 182 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 29 MB)
Search Publication Server

Authors
  • Adler, Isolde
  • Agarwal, Pankaj K.
  • Aiswarya, C.
  • Almagor, Shaull
  • Arora, Sanjeev
  • Arrighi, Emmanuel
  • Atserias, Albert
  • Baier, Christel
  • Balasubramanian, A. R.
  • Banerjee, Niranka
  • Bernemann, Rebecca
  • Bernstein, Aaron
  • Bertrand, Nathalie
  • Beyersdorff, Olaf
  • Bhattacharya, Anup
  • Bille, Philip
  • Bilò, Davide
  • Blinkhorn, Joshua
  • Block, Alexander R.
  • Blocki, Jeremiah
  • Boker, Udi
  • Bonnet, Édouard
  • Bouyer, Patricia
  • Cabrera, Benjamin
  • Chang, Hsien-Chih
  • Chini, Peter
  • Choudhary, Pratibha
  • Cook, Joshua
  • Darwin, Oscar
  • de Oliveira Oliveira, Mateus
  • Droste, Manfred
  • D'Souza, Deepak
  • Dudeja, Aditi
  • Dvořák, Pavel
  • Dziadek, Sven
  • Fahey, Polly
  • Fernau, Henning
  • Filiot, Emmanuel
  • Friedrich, Tobias
  • Funke, Florian
  • Gajulapalli, Karthik
  • Gastin, Paul
  • Ghosh, Prantar
  • Gørtz, Inge Li
  • Goyal, Dishant
  • Grelier, Nicolas
  • Grigorescu, Elena
  • Grüttemeier, Niels
  • Gupta, Anupam
  • Gupta, Sushmita
  • Haar, Stefan
  • Haddad, Serge
  • Heckel, Reiko
  • Jain, Pallavi
  • Jaiswal, Ragesh
  • Jantsch, Simon
  • Kanesh, Lawqueen
  • Karimov, Toghrul
  • Kavitha, Telikepalli
  • Khalil, Lidiya Khalidah binti
  • Khanna, Yash
  • Kiefer, Stefan
  • King, Valerie
  • Komusiewicz, Christian
  • Konečný, Michal
  • König, Barbara
  • Konrad, Christian
  • Kothapalli, Kishore
  • Krishnaswamy, Ravishankar
  • Kuich, Werner
  • Kulkarni, Shubhang
  • Kumar, Amit
  • Kuperberg, Denis
  • Kupferman, Orna
  • Lee, Yin Tat
  • Lefaucheux, Engel
  • Lehtinen, Karoliina
  • Lenzner, Pascal
  • Liu, James A.
  • Löding, Christof
  • Loff, Bruno
  • Lokshtanov, Daniel
  • Louis, Anand
  • Mahajan, Meena
  • Mai, Tung
  • Majumdar, Anirban
  • Mande, Nikhil S.
  • Markey, Nicolas
  • Melnichenko, Anna
  • Meyer, Roland
  • Miltzow, Tillmann
  • Molitor, Louise
  • Morawietz, Nils
  • Moshkovitz, Dana
  • Mukherjee, Sayan
  • Munagala, Kamesh
  • Oh, Justin
  • Ouaknine, Joël
  • Pai, Rekha
  • Pai, Shreyas
  • Panolan, Fahad
  • Parys, Paweł
  • Pedersen, Max Rishøj
  • Peitl, Tomáš
  • Pemmaraju, Sriram V.
  • Perrin, Dominique
  • Pouly, Amaury
  • Praveen, M.
  • Purser, David
  • Raman, Venkatesh
  • Rotenberg, Eva
  • Roy, Sanjukta
  • Ryzhikov, Andrew
  • Sadhukhan, Suman
  • Saivasan, Prakash
  • Sankur, Ocan
  • Sanyal, Swagato
  • Saurabh, Saket
  • Saxena, Nitin
  • Schewe, Sven
  • Schwoon, Stefan
  • Seshia, Sanjit A.
  • Shenwald, Noam
  • Shpilka, Amir
  • Simon, Sunil
  • Singla, Sahil
  • Skrzypczak, Michał
  • Sommer, Frank
  • Sood, Gaurav
  • Srivathsan, B
  • Steinberg, Florian
  • Steiner, Teresa Anna
  • Tang, Qiyi
  • Taylor, Erin
  • Thies, Holger
  • Tulsyan, Rishi
  • van der Wall, Sören
  • Vazirani, Vijay V.
  • Wasim, Omer
  • Welzl, Emo
  • Whiteland, Markus A.
  • Winter, Sarah
  • Wolf, Petra
  • Ye, Lina
  • Zehavi, Meirav
  • Zhu, Minshen
  • Zuckerman, David
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Saxena, Nitin ; Simon, Sunil

    Abstract | Document (344 KB) | BibTeX

    The Quest for Mathematical Understanding of Deep Learning (Invited Talk)
    Authors: Arora, Sanjeev

    Abstract | Document (176 KB) | BibTeX

    Proofs of Soundness and Proof Search (Invited Talk)
    Authors: Atserias, Albert

    Abstract | Document (164 KB) | BibTeX

    Convex Optimization and Dynamic Data Structure (Invited Talk)
    Authors: Lee, Yin Tat

    Abstract | Document (180 KB) | BibTeX

    Holonomic Techniques, Periods, and Decision Problems (Invited Talk)
    Authors: Ouaknine, Joël

    Abstract | Document (309 KB) | BibTeX

    Algorithmic Improvisation for Dependable Intelligent Autonomy (Invited Talk)
    Authors: Seshia, Sanjit A.

    Abstract | Document (272 KB) | BibTeX

    On Some Recent Advances in Algebraic Complexity (Invited Talk)
    Authors: Shpilka, Amir

    Abstract | Document (204 KB) | BibTeX

    Faster Property Testers in a Variation of the Bounded Degree Model
    Authors: Adler, Isolde ; Fahey, Polly

    Abstract | Document (509 KB) | BibTeX

    Clustering Under Perturbation Stability in Near-Linear Time
    Authors: Agarwal, Pankaj K. ; Chang, Hsien-Chih ; Munagala, Kamesh ; Taylor, Erin ; Welzl, Emo

    Abstract | Document (555 KB) | BibTeX

    Width Notions for Ordering-Related Problems
    Authors: Arrighi, Emmanuel ; Fernau, Henning ; de Oliveira Oliveira, Mateus ; Wolf, Petra

    Abstract | Document (630 KB) | BibTeX

    Optimal Output Sensitive Fault Tolerant Cuts
    Authors: Banerjee, Niranka ; Raman, Venkatesh ; Saurabh, Saket

    Abstract | Document (685 KB) | BibTeX

    Online Matching with Recourse: Random Edge Arrivals
    Authors: Bernstein, Aaron ; Dudeja, Aditi

    Abstract | Document (830 KB) | BibTeX

    Hard QBFs for Merge Resolution
    Authors: Beyersdorff, Olaf ; Blinkhorn, Joshua ; Mahajan, Meena ; Peitl, Tomáš ; Sood, Gaurav

    Abstract | Document (569 KB) | BibTeX

    On Sampling Based Algorithms for k-Means
    Authors: Bhattacharya, Anup ; Goyal, Dishant ; Jaiswal, Ragesh ; Kumar, Amit

    Abstract | Document (655 KB) | BibTeX

    String Indexing for Top-k Close Consecutive Occurrences
    Authors: Bille, Philip ; Gørtz, Inge Li ; Pedersen, Max Rishøj ; Rotenberg, Eva ; Steiner, Teresa Anna

    Abstract | Document (533 KB) | BibTeX

    Fair Tree Connection Games with Topology-Dependent Edge Cost
    Authors: Bilò, Davide ; Friedrich, Tobias ; Lenzner, Pascal ; Melnichenko, Anna ; Molitor, Louise

    Abstract | Document (705 KB) | BibTeX

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

    Abstract | Document (592 KB) | BibTeX

    Maximum Clique in Disk-Like Intersection Graphs
    Authors: Bonnet, Édouard ; Grelier, Nicolas ; Miltzow, Tillmann

    Abstract | Document (710 KB) | BibTeX

    Parameterized Complexity of Feedback Vertex Sets on Hypergraphs
    Authors: Choudhary, Pratibha ; Kanesh, Lawqueen ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket

    Abstract | Document (706 KB) | BibTeX

    Size Bounds on Low Depth Circuits for Promise Majority
    Authors: Cook, Joshua

    Abstract | Document (461 KB) | BibTeX

    Lower Bounds for Semi-adaptive Data Structures via Corruption
    Authors: Dvořák, Pavel ; Loff, Bruno

    Abstract | Document (534 KB) | BibTeX

    Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds
    Authors: Gajulapalli, Karthik ; Liu, James A. ; Mai, Tung ; Vazirani, Vijay V.

    Abstract | Document (505 KB) | BibTeX

    New Verification Schemes for Frequency-Based Functions on Data Streams
    Authors: Ghosh, Prantar

    Abstract | Document (485 KB) | BibTeX

    Online Carpooling Using Expander Decompositions
    Authors: Gupta, Anupam ; Krishnaswamy, Ravishankar ; Kumar, Amit ; Singla, Sahil

    Abstract | Document (580 KB) | BibTeX

    On the (Parameterized) Complexity of Almost Stable Marriage
    Authors: Gupta, Sushmita ; Jain, Pallavi ; Roy, Sanjukta ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (931 KB) | BibTeX

    Min-Cost Popular Matchings
    Authors: Kavitha, Telikepalli

    Abstract | Document (503 KB) | BibTeX

    Constructing Large Matchings via Query Access to a Maximal Matching Oracle
    Authors: Khalil, Lidiya Khalidah binti ; Konrad, Christian

    Abstract | Document (605 KB) | BibTeX

    Planted Models for the Densest k-Subgraph Problem
    Authors: Khanna, Yash ; Louis, Anand

    Abstract | Document (653 KB) | BibTeX

    Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model
    Authors: Kothapalli, Kishore ; Pai, Shreyas ; Pemmaraju, Sriram V.

    Abstract | Document (655 KB) | BibTeX

    On Parity Decision Trees for Fourier-Sparse Boolean Functions
    Authors: Mande, Nikhil S. ; Sanyal, Swagato

    Abstract | Document (640 KB) | BibTeX

    Colored Cut Games
    Authors: Morawietz, Nils ; Grüttemeier, Niels ; Komusiewicz, Christian ; Sommer, Frank

    Abstract | Document (558 KB) | BibTeX

    Randomness Efficient Noise Stability and Generalized Small Bias Sets
    Authors: Moshkovitz, Dana ; Oh, Justin ; Zuckerman, David

    Abstract | Document (530 KB) | BibTeX

    Connectivity Lower Bounds in Broadcast Congested Clique
    Authors: Pai, Shreyas ; Pemmaraju, Sriram V.

    Abstract | Document (639 KB) | BibTeX

    Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT
    Authors: Wasim, Omer ; King, Valerie

    Abstract | Document (546 KB) | BibTeX

    Weighted Tiling Systems for Graphs: Evaluation Complexity
    Authors: Aiswarya, C. ; Gastin, Paul

    Abstract | Document (787 KB) | BibTeX

    Process Symmetry in Probabilistic Transducers
    Authors: Almagor, Shaull

    Abstract | Document (577 KB) | BibTeX

    Reachability in Dynamical Systems with Rounding
    Authors: Baier, Christel ; Funke, Florian ; Jantsch, Simon ; Karimov, Toghrul ; Lefaucheux, Engel ; Ouaknine, Joël ; Pouly, Amaury ; Purser, David ; Whiteland, Markus A.

    Abstract | Document (1,646 KB) | BibTeX

    Parameterized Complexity of Safety of Threshold Automata
    Authors: Balasubramanian, A. R.

    Abstract | Document (657 KB) | BibTeX

    Uncertainty Reasoning for Probabilistic Petri Nets via Bayesian Networks
    Authors: Bernemann, Rebecca ; Cabrera, Benjamin ; Heckel, Reiko ; König, Barbara

    Abstract | Document (587 KB) | BibTeX

    Synthesizing Safe Coalition Strategies
    Authors: Bertrand, Nathalie ; Bouyer, Patricia ; Majumdar, Anirban

    Abstract | Document (618 KB) | BibTeX

    Dynamic Network Congestion Games
    Authors: Bertrand, Nathalie ; Markey, Nicolas ; Sadhukhan, Suman ; Sankur, Ocan

    Abstract | Document (595 KB) | BibTeX

    On the Succinctness of Alternating Parity Good-For-Games Automata
    Authors: Boker, Udi ; Kuperberg, Denis ; Lehtinen, Karoliina ; Skrzypczak, Michał

    Abstract | Document (529 KB) | BibTeX

    A Framework for Consistency Algorithms
    Authors: Chini, Peter ; Saivasan, Prakash

    Abstract | Document (487 KB) | BibTeX

    Equivalence of Hidden Markov Models with Continuous Observations
    Authors: Darwin, Oscar ; Kiefer, Stefan

    Abstract | Document (457 KB) | BibTeX

    Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words
    Authors: Droste, Manfred ; Dziadek, Sven ; Kuich, Werner

    Abstract | Document (546 KB) | BibTeX

    Synchronization of Deterministic Visibly Push-Down Automata
    Authors: Fernau, Henning ; Wolf, Petra

    Abstract | Document (595 KB) | BibTeX

    Synthesis from Weighted Specifications with Partial Domains over Finite Words
    Authors: Filiot, Emmanuel ; Löding, Christof ; Winter, Sarah

    Abstract | Document (533 KB) | BibTeX

    Reachability for Updatable Timed Automata Made Faster and More Effective
    Authors: Gastin, Paul ; Mukherjee, Sayan ; Srivathsan, B

    Abstract | Document (554 KB) | BibTeX

    Active Prediction for Discrete Event Systems
    Authors: Haar, Stefan ; Haddad, Serge ; Schwoon, Stefan ; Ye, Lina

    Abstract | Document (526 KB) | BibTeX

    Comparing Labelled Markov Decision Processes
    Authors: Kiefer, Stefan ; Tang, Qiyi

    Abstract | Document (602 KB) | BibTeX

    Computable Analysis for Verified Exact Real Computation
    Authors: Konečný, Michal ; Steinberg, Florian ; Thies, Holger

    Abstract | Document (574 KB) | BibTeX

    Perspective Games with Notifications
    Authors: Kupferman, Orna ; Shenwald, Noam

    Abstract | Document (581 KB) | BibTeX

    On the Complexity of Multi-Pushdown Games
    Authors: Meyer, Roland ; van der Wall, Sören

    Abstract | Document (710 KB) | BibTeX

    Higher-Order Nonemptiness Step by Step
    Authors: Parys, Paweł

    Abstract | Document (485 KB) | BibTeX

    The Degree of a Finite Set of Words
    Authors: Perrin, Dominique ; Ryzhikov, Andrew

    Abstract | Document (551 KB) | BibTeX

    What You Must Remember When Transforming Datawords
    Authors: Praveen, M.

    Abstract | Document (463 KB) | BibTeX

    Minimising Good-For-Games Automata Is NP-Complete
    Authors: Schewe, Sven

    Abstract | Document (536 KB) | BibTeX

    Static Race Detection for RTOS Applications
    Authors: Tulsyan, Rishi ; Pai, Rekha ; D'Souza, Deepak

    Abstract | Document (647 KB) | BibTeX

    Synchronization Under Dynamic Constraints
    Authors: Wolf, Petra

    Abstract | Document (617 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI