FSTTCS 2021 December 15-17, 2021, Virtual Conference

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)



Mikołaj Bojańczyk and Chandra Chekuri (Eds.)
ISBN 978-3-95977-215-0, LIPICS Vol. 213 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 17 MB)
Search Publication Server

Authors
  • Aaronson, Scott
  • Ahn, Hee-Kap
  • Akshay, S.
  • Albers, Susanne
  • Allender, Eric
  • Aoto, Takahito
  • Arrighi, Emmanuel
  • Balasubramanian, A. R.
  • Banchhor, Shashwat
  • Bednarczyk, Bartosz
  • Bedon, Nicolas
  • Bojańczyk, Mikołaj
  • Boker, Udi
  • Bollig, Benedikt
  • Bonchi, Filippo
  • Bordais, Benjamin
  • Bouyer, Patricia
  • Boyd, Sylvia
  • Chakraborty, Diptarka
  • Chakraborty, Sourav
  • Chatterjee, Krishnendu
  • Chattopadhyay, Arkadev
  • Chekuri, Chandra
  • Cheraghchi, Mahdi
  • Cheriyan, Joseph
  • Chillara, Suryajith
  • Dahiya, Yogesh
  • Das, Debarati
  • Datta, Samir
  • Deka, Nabarun
  • de Oliveira Oliveira, Mateus
  • Di Giorgio, Alessandro
  • D'Souza, Deepak
  • Du, Yang
  • Eberle, Franziska
  • Eom, Taekang
  • Esparza, Javier
  • Esser, Andre
  • Fernau, Henning
  • Filiot, Emmanuel
  • Finkbeiner, Bernd
  • Fomin, Fedor V.
  • Gajjala, Rishikesh
  • Gajjar, Kshitij
  • Garg, Ankit
  • Garg, Jugal
  • Genest, Blaise
  • Goldberg, Leslie Ann
  • Golovach, Petr A.
  • Gupta, Chetan
  • Gutiérrez, Raúl
  • Haddadan, Arash
  • Hélouët, Loïc
  • Hoffmann, Stefan
  • Hofmann, Jana
  • Holla, Raveendra
  • Holzer, Markus
  • Hugenroth, Christopher
  • Ibrahimpur, Sharat
  • Ibsen-Jensen, Rasmus
  • Inamdar, Tanmay
  • Jain, Rahul
  • Jalan, Akhil
  • Janke, Maximilian
  • Jecker, Ismaël
  • Jha, Agastya Vibhuti
  • Jordon, Liam
  • Kavitha, Telikepalli
  • Kiefer, Stefan
  • Kikuchi, Kentaro
  • Klimenko, Georgiy
  • Kontinen, Juha
  • Krauthgamer, Robert
  • Krishna, S.
  • Kübler, Robert
  • Kulkarni, Pooja
  • Lasota, Sławomir
  • Lee, Dongho
  • Lee, Seungjun
  • Lehtinen, Karoliina
  • Le Roux, Stéphane
  • Lin, Huijia (Rachel)
  • Li, Xin
  • Lokshtanov, Daniel
  • Lucas, Salvador
  • Mahajan, Meena
  • Mande, Nikhil S.
  • Megow, Nicole
  • Mittal, Rajat
  • Molli, Tulasimohan
  • Moser, Philippe
  • Moshkovitz, Dana
  • Mukherjee, Anish
  • Murhekar, Aniket
  • Myrisiotis, Dimitrios
  • Nasre, Meghana
  • Nimbhorkar, Prajakta
  • Nölke, Lukas
  • Orłowska, Maja
  • Pacanowska, Anna
  • Paraashar, Manaswi
  • Pattathurajan, Mohnish
  • Pavlogiannis, Andreas
  • Perrelle, Valentin
  • Radhakrishnan, Jaikumar
  • Raichel, Benjamin
  • Ranjan, Keshav
  • Roychowdhury, Sparsa
  • Sabharwal, Yogish
  • Sangnier, Arnaud
  • Sanyal, Swagato
  • Sarkar, Ankita
  • Saurabh, Saket
  • Savani, Rahul
  • Sen, Sandeep
  • Sharma, Eklavya
  • Sharma, Vimal Raj
  • Sherif, Suhail
  • Simon, Bertrand
  • Sobociński, Paweł
  • Srinivasan, Aravind
  • Stietel, Olivier
  • Surianarayanan, Vaishali
  • Suri, Subhash
  • Tang, Qiyi
  • Tan, Tony
  • Tewari, Raghunath
  • Tirumala, Harsha
  • Valiron, Benoît
  • Virtema, Jonni
  • Vítores, Miguel
  • Volkovich, Ilya
  • Wiese, Andreas
  • Winter, Sarah
  • Wolf, Petra
  • Xue, Jie
  • Xu, Zhaowei
  • Yang, Fan
  • Zheng, Yu
  • Zweydinger, Floyd
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Bojańczyk, Mikołaj ; Chekuri, Chandra

    Abstract | Document (433 KB) | BibTeX

    BQP After 28 Years (Invited Talk)
    Authors: Aaronson, Scott

    Abstract | Document (300 KB) | BibTeX

    State Complexity of Population Protocols (Invited Talk)
    Authors: Esparza, Javier

    Abstract | Document (371 KB) | BibTeX

    Approximately Counting Graph Homomorphisms and Retractions (Invited Talk)
    Authors: Goldberg, Leslie Ann

    Abstract | Document (341 KB) | BibTeX

    Indistinguishability Obfuscation from Well-Founded Assumptions (Invited Talk)
    Authors: Lin, Huijia (Rachel)

    Abstract | Document (345 KB) | BibTeX

    The Complexity of Gradient Descent (Invited Talk)
    Authors: Savani, Rahul

    Abstract | Document (442 KB) | BibTeX

    Scheduling in the Secretary Model
    Authors: Albers, Susanne ; Janke, Maximilian

    Abstract | Document (905 KB) | BibTeX

    One-Way Functions and a Conditional Variant of MKTP
    Authors: Allender, Eric ; Cheraghchi, Mahdi ; Myrisiotis, Dimitrios ; Tirumala, Harsha ; Volkovich, Ilya

    Abstract | Document (815 KB) | BibTeX

    Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings
    Authors: Banchhor, Shashwat ; Gajjala, Rishikesh ; Sabharwal, Yogish ; Sen, Sandeep

    Abstract | Document (915 KB) | BibTeX

    Approximation Algorithms for Flexible Graph Connectivity
    Authors: Boyd, Sylvia ; Cheriyan, Joseph ; Haddadan, Arash ; Ibrahimpur, Sharat

    Abstract | Document (759 KB) | BibTeX

    Tight Chang’s-Lemma-Type Bounds for Boolean Functions
    Authors: Chakraborty, Sourav ; Mande, Nikhil S. ; Mittal, Rajat ; Molli, Tulasimohan ; Paraashar, Manaswi ; Sanyal, Swagato

    Abstract | Document (876 KB) | BibTeX

    Approximate Trace Reconstruction via Median String (In Average-Case)
    Authors: Chakraborty, Diptarka ; Das, Debarati ; Krauthgamer, Robert

    Abstract | Document (1,085 KB) | BibTeX

    Approximating the Center Ranking Under Ulam
    Authors: Chakraborty, Diptarka ; Gajjar, Kshitij ; Jha, Agastya Vibhuti

    Abstract | Document (971 KB) | BibTeX

    Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
    Authors: Chattopadhyay, Arkadev ; Garg, Ankit ; Sherif, Suhail

    Abstract | Document (729 KB) | BibTeX

    Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four
    Authors: Chillara, Suryajith

    Abstract | Document (814 KB) | BibTeX

    On (Simple) Decision Tree Rank
    Authors: Dahiya, Yogesh ; Mahajan, Meena

    Abstract | Document (719 KB) | BibTeX

    Reachability and Matching in Single Crossing Minor Free Graphs
    Authors: Datta, Samir ; Gupta, Chetan ; Jain, Rahul ; Mukherjee, Anish ; Sharma, Vimal Raj ; Tewari, Raghunath

    Abstract | Document (811 KB) | BibTeX

    Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function
    Authors: Du, Yang ; Volkovich, Ilya

    Abstract | Document (742 KB) | BibTeX

    Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
    Authors: Eberle, Franziska ; Megow, Nicole ; Nölke, Lukas ; Simon, Bertrand ; Wiese, Andreas

    Abstract | Document (799 KB) | BibTeX

    Largest Similar Copies of Convex Polygons in Polygonal Domains
    Authors: Eom, Taekang ; Lee, Seungjun ; Ahn, Hee-Kap

    Abstract | Document (993 KB) | BibTeX

    A Faster Algorithm for Finding Closest Pairs in Hamming Metric
    Authors: Esser, Andre ; Kübler, Robert ; Zweydinger, Floyd

    Abstract | Document (896 KB) | BibTeX

    ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Inamdar, Tanmay ; Saurabh, Saket

    Abstract | Document (850 KB) | BibTeX

    On Fair and Efficient Allocations of Indivisible Public Goods
    Authors: Garg, Jugal ; Kulkarni, Pooja ; Murhekar, Aniket

    Abstract | Document (733 KB) | BibTeX

    Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
    Authors: Gupta, Chetan ; Jain, Rahul ; Tewari, Raghunath

    Abstract | Document (773 KB) | BibTeX

    Near-Optimal Cayley Expanders for Abelian Groups
    Authors: Jalan, Akhil ; Moshkovitz, Dana

    Abstract | Document (758 KB) | BibTeX

    Matchings, Critical Nodes, and Popular Solutions
    Authors: Kavitha, Telikepalli

    Abstract | Document (718 KB) | BibTeX

    Fast and Exact Convex Hull Simplification
    Authors: Klimenko, Georgiy ; Raichel, Benjamin

    Abstract | Document (727 KB) | BibTeX

    Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
    Authors: Li, Xin ; Zheng, Yu

    Abstract | Document (777 KB) | BibTeX

    An ETH-Tight Algorithm for Multi-Team Formation
    Authors: Lokshtanov, Daniel ; Saurabh, Saket ; Suri, Subhash ; Xue, Jie

    Abstract | Document (691 KB) | BibTeX

    Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable
    Authors: Lokshtanov, Daniel ; Surianarayanan, Vaishali

    Abstract | Document (844 KB) | BibTeX

    Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas
    Authors: Nasre, Meghana ; Nimbhorkar, Prajakta ; Ranjan, Keshav ; Sarkar, Ankita

    Abstract | Document (791 KB) | BibTeX

    Property B: Two-Coloring Non-Uniform Hypergraphs
    Authors: Radhakrishnan, Jaikumar ; Srinivasan, Aravind

    Abstract | Document (554 KB) | BibTeX

    Harmonic Algorithms for Packing d-Dimensional Cuboids into Bins
    Authors: Sharma, Eklavya

    Abstract | Document (871 KB) | BibTeX

    Resilience of Timed Systems
    Authors: Akshay, S. ; Genest, Blaise ; Hélouët, Loïc ; Krishna, S. ; Roychowdhury, Sparsa

    Abstract | Document (865 KB) | BibTeX

    On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
    Authors: Arrighi, Emmanuel ; Fernau, Henning ; Hoffmann, Stefan ; Holzer, Markus ; Jecker, Ismaël ; de Oliveira Oliveira, Mateus ; Wolf, Petra

    Abstract | Document (824 KB) | BibTeX

    Complexity of Coverability in Bounded Path Broadcast Networks
    Authors: Balasubramanian, A. R.

    Abstract | Document (1,024 KB) | BibTeX

    On Classical Decidable Logics Extended with Percentage Quantifiers and Arithmetics
    Authors: Bednarczyk, Bartosz ; Orłowska, Maja ; Pacanowska, Anna ; Tan, Tony

    Abstract | Document (958 KB) | BibTeX

    Branching Automata and Pomset Automata
    Authors: Bedon, Nicolas

    Abstract | Document (656 KB) | BibTeX

    History Determinism vs. Good for Gameness in Quantitative Automata
    Authors: Boker, Udi ; Lehtinen, Karoliina

    Abstract | Document (854 KB) | BibTeX

    Local First-Order Logic with Two Data Values
    Authors: Bollig, Benedikt ; Sangnier, Arnaud ; Stietel, Olivier

    Abstract | Document (802 KB) | BibTeX

    Diagrammatic Polyhedral Algebra
    Authors: Bonchi, Filippo ; Di Giorgio, Alessandro ; Sobociński, Paweł

    Abstract | Document (843 KB) | BibTeX

    From Local to Global Determinacy in Concurrent Graph Games
    Authors: Bordais, Benjamin ; Bouyer, Patricia ; Le Roux, Stéphane

    Abstract | Document (1,037 KB) | BibTeX

    Quantitative Verification on Product Graphs of Small Treewidth
    Authors: Chatterjee, Krishnendu ; Ibsen-Jensen, Rasmus ; Pavlogiannis, Andreas

    Abstract | Document (871 KB) | BibTeX

    Synthesizing Computable Functions from Rational Specifications over Infinite Words
    Authors: Filiot, Emmanuel ; Winter, Sarah

    Abstract | Document (803 KB) | BibTeX

    Confluence of Conditional Rewriting in Logic Form
    Authors: Gutiérrez, Raúl ; Lucas, Salvador ; Vítores, Miguel

    Abstract | Document (902 KB) | BibTeX

    On the Expressive Equivalence of TPTL in the Pointwise and Continuous Semantics
    Authors: Holla, Raveendra ; Deka, Nabarun ; D'Souza, Deepak

    Abstract | Document (723 KB) | BibTeX

    Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy
    Authors: Hugenroth, Christopher

    Abstract | Document (645 KB) | BibTeX

    Normal Sequences with Non-Maximal Automatic Complexity
    Authors: Jordon, Liam ; Moser, Philippe

    Abstract | Document (753 KB) | BibTeX

    Approximate Bisimulation Minimisation
    Authors: Kiefer, Stefan ; Tang, Qiyi

    Abstract | Document (791 KB) | BibTeX

    Simple Derivation Systems for Proving Sufficient Completeness of Non-Terminating Term Rewriting Systems
    Authors: Kikuchi, Kentaro ; Aoto, Takahito

    Abstract | Document (635 KB) | BibTeX

    Parikh Images of Register Automata
    Authors: Lasota, Sławomir ; Pattathurajan, Mohnish

    Abstract | Document (781 KB) | BibTeX

    Concrete Categorical Model of a Quantum Circuit Description Language with Measurement
    Authors: Lee, Dongho ; Perrelle, Valentin ; Valiron, Benoît ; Xu, Zhaowei

    Abstract | Document (2,157 KB) | BibTeX

    Linear-Time Temporal Logic with Team Semantics: Expressivity and Complexity
    Authors: Virtema, Jonni ; Hofmann, Jana ; Finkbeiner, Bernd ; Kontinen, Juha ; Yang, Fan

    Abstract | Document (806 KB) | BibTeX

    		  



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