FSTTCS 2022 December 18-20, 2022, IIT Madras, Chennai, India

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)



Anuj Dawar and Venkatesan Guruswami (Eds.)
ISBN 978-3-95977-261-7, LIPICS Vol. 250 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 19 MB)
Search Publication Server

Authors
  • Ahmadi, Ali
  • Ahn, Hee-Kap
  • Avni, Guy
  • Babu, Jasine
  • Bae, Sang Won
  • Beideman, Calvin
  • Bellier, Dylan
  • Bertrand, Nathalie
  • Bilardi, Gianfranco
  • Bishnu, Arijit
  • Bisht, Pranav
  • Bordais, Benjamin
  • Bouyer, Patricia
  • Carton, Olivier
  • Chandrasekaran, Karthekeyan
  • Chatterjee, Krishnendu
  • Chattopadhyay, Arkadev
  • Chekuri, Chandra
  • Chung, Jaehoon
  • Cook, Joshua
  • Cornelissen, Arjan
  • Curticapean, Radu
  • Dawar, Anuj
  • De, Abhishek
  • De, Minati
  • De Stefani, Lorenzo
  • Dinur, Irit
  • Duraisamy, Nandhana
  • Ehlers, Rüdiger
  • Finkbeiner, Bernd
  • Ganardi, Moses
  • Gangam, Rohith Reddy
  • Garg, Mohit
  • Gesmundo, Fulvio
  • Ghosal, Purnata
  • Ghosal, Utsab
  • Ghosh, Arijit
  • Goharshady, Amir Kafshdar
  • Guha, Shibashis
  • Gupta, Anupam
  • Guruswami, Venkatesan
  • Hillberg, Hannah Miller
  • Ibsen-Jensen, Rasmus
  • Ikenmeyer, Christian
  • Jachiet, Louis
  • Jafarrahmani, Farzad
  • Jain, Saksham
  • Jallu, Ramesh K.
  • Jecker, Ismaël
  • Joshi, Utkarsh
  • Jurdziński, Marcin
  • Kallepalli, Sarat Varma
  • Kavitha, Telikepalli
  • Khan, Arindam
  • Koechlin, Florent
  • Koiran, Pascal
  • Krithika, R.
  • Krohn, Erik
  • Kupferman, Orna
  • Lachish, Oded
  • Lehtinen, Karoliina
  • Le Roux, Stéphane
  • Leshkowitz, Ofer
  • Limaye, Nutan
  • Lohrey, Markus
  • Lysikov, Vladimir
  • Maharjan, Ramita
  • Maheshwari, Anil
  • Mai, Tung
  • Mande, Nikhil S.
  • Markey, Nicolas
  • Meggendorfer, Tobias
  • Mishra, Gopinath
  • Misra, Neeldhara
  • Mukhopadhyay, Partha
  • Mulpuri, Manas
  • Nandy, Subhas C.
  • Ohlmann, Pierre
  • Pahlow, Alex
  • Paraashar, Manaswi
  • Passing, Noemi
  • Patro, Subhasree
  • Pinchinat, Sophie
  • Place, Thomas
  • Rahul, Saladi
  • Rajendraprasad, Deepak
  • Raju, Nitya
  • Randour, Mickael
  • Reidl, Felix
  • Sadhukhan, Suman
  • Safavi, Roodabeh
  • Saha, Subhayan
  • Sankur, Ocan
  • Santhanam, Rahul
  • Sarswat, Suneel
  • Saurin, Alexis
  • Saxena, Nitin
  • Schewe, Sven
  • Schwarzentruber, François
  • Schwentick, Thomas
  • Sharma, Eklavya
  • Shin, Chan-Su
  • Singh, Satyam
  • Sreenivas, K. V. N.
  • Srinivasan, Srikanth
  • Svoboda, Jakub
  • Tale, Prafullkumar
  • Thejaswini, K. S.
  • Thoppil, Josson Joe
  • Trehan, Chhaya
  • Vandenhove, Pierre
  • Vazirani, Vijay V.
  • Viramgami, Gaurav
  • Volkovich, Ilya
  • Watson, Thomas
  • Xu, Chao
  • Yoon, Sang Duk
  • Zeitoun, Marc
  • Žikelić, Ðorđe
  • Zimmermann, Martin
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Dawar, Anuj ; Guruswami, Venkatesan

    Abstract | Document (493 KB) | BibTeX

    Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk)
    Authors: Gupta, Anupam

    Abstract | Document (254 KB) | BibTeX

    Why MCSP Is a More Important Problem Than SAT (Invited Talk)
    Authors: Santhanam, Rahul

    Abstract | Document (343 KB) | BibTeX

    The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs (Invited Talk)
    Authors: Bouyer, Patricia ; Randour, Mickael ; Vandenhove, Pierre

    Abstract | Document (759 KB) | BibTeX

    Expanders in Higher Dimensions (Invited Talk)
    Authors: Dinur, Irit

    Abstract | Document (293 KB) | BibTeX

    Packing Arc-Disjoint 4-Cycles in Oriented Graphs
    Authors: Babu, Jasine ; Krithika, R. ; Rajendraprasad, Deepak

    Abstract | Document (903 KB) | BibTeX

    Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
    Authors: Beideman, Calvin ; Chandrasekaran, Karthekeyan ; Chekuri, Chandra ; Xu, Chao

    Abstract | Document (644 KB) | BibTeX

    The DAG Visit Approach for Pebbling and I/O Lower Bounds
    Authors: Bilardi, Gianfranco ; De Stefani, Lorenzo

    Abstract | Document (915 KB) | BibTeX

    Counting and Sampling from Substructures Using Linear Algebraic Queries
    Authors: Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath ; Paraashar, Manaswi

    Abstract | Document (861 KB) | BibTeX

    Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials
    Authors: Bisht, Pranav ; Saxena, Nitin

    Abstract | Document (822 KB) | BibTeX

    On Solving Sparse Polynomial Factorization Related Problems
    Authors: Bisht, Pranav ; Volkovich, Ilya

    Abstract | Document (849 KB) | BibTeX

    Complexity of Spatial Games
    Authors: Chatterjee, Krishnendu ; Ibsen-Jensen, Rasmus ; Jecker, Ismaël ; Svoboda, Jakub

    Abstract | Document (642 KB) | BibTeX

    Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product
    Authors: Chattopadhyay, Arkadev ; Ghosal, Utsab ; Mukhopadhyay, Partha

    Abstract | Document (787 KB) | BibTeX

    Inscribing or Circumscribing a Histogon to a Convex Polygon
    Authors: Chung, Jaehoon ; Bae, Sang Won ; Shin, Chan-Su ; Yoon, Sang Duk ; Ahn, Hee-Kap

    Abstract | Document (873 KB) | BibTeX

    More Verifier Efficient Interactive Protocols for Bounded Space
    Authors: Cook, Joshua

    Abstract | Document (804 KB) | BibTeX

    Improved Quantum Query Upper Bounds Based on Classical Decision Trees
    Authors: Cornelissen, Arjan ; Mande, Nikhil S. ; Patro, Subhasree

    Abstract | Document (779 KB) | BibTeX

    On the VNP-Hardness of Some Monomial Symmetric Polynomials
    Authors: Curticapean, Radu ; Limaye, Nutan ; Srinivasan, Srikanth

    Abstract | Document (814 KB) | BibTeX

    Online Piercing of Geometric Objects
    Authors: De, Minati ; Jain, Saksham ; Kallepalli, Sarat Varma ; Singh, Satyam

    Abstract | Document (1,167 KB) | BibTeX

    Half-Guarding Weakly-Visible Polygons and Terrains
    Authors: Duraisamy, Nandhana ; Hillberg, Hannah Miller ; Jallu, Ramesh K. ; Krohn, Erik ; Maheshwari, Anil ; Nandy, Subhas C. ; Pahlow, Alex

    Abstract | Document (1,312 KB) | BibTeX

    A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications
    Authors: Gangam, Rohith Reddy ; Mai, Tung ; Raju, Nitya ; Vazirani, Vijay V.

    Abstract | Document (776 KB) | BibTeX

    Degree-Restricted Strength Decompositions and Algebraic Branching Programs
    Authors: Gesmundo, Fulvio ; Ghosal, Purnata ; Ikenmeyer, Christian ; Lysikov, Vladimir

    Abstract | Document (702 KB) | BibTeX

    A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs
    Authors: Joshi, Utkarsh ; Rahul, Saladi ; Thoppil, Josson Joe

    Abstract | Document (857 KB) | BibTeX

    Stable Matchings with One-Sided Ties and Approximate Popularity
    Authors: Kavitha, Telikepalli

    Abstract | Document (732 KB) | BibTeX

    Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
    Authors: Khan, Arindam ; Sharma, Eklavya ; Sreenivas, K. V. N.

    Abstract | Document (938 KB) | BibTeX

    Black Box Absolute Reconstruction for Sums of Powers of Linear Forms
    Authors: Koiran, Pascal ; Saha, Subhayan

    Abstract | Document (711 KB) | BibTeX

    When You Come at the King You Best Not Miss
    Authors: Lachish, Oded ; Reidl, Felix ; Trehan, Chhaya

    Abstract | Document (654 KB) | BibTeX

    Complexity of Fault Tolerant Query Complexity
    Authors: Maharjan, Ramita ; Watson, Thomas

    Abstract | Document (563 KB) | BibTeX

    Romeo and Juliet Meeting in Forest like Regions
    Authors: Misra, Neeldhara ; Mulpuri, Manas ; Tale, Prafullkumar ; Viramgami, Gaurav

    Abstract | Document (5,742 KB) | BibTeX

    New Characterizations of Core Imputations of Matching and b-Matching Games
    Authors: Vazirani, Vijay V.

    Abstract | Document (596 KB) | BibTeX

    Algorithms and Hardness Results for Computing Cores of Markov Chains
    Authors: Ahmadi, Ali ; Chatterjee, Krishnendu ; Goharshady, Amir Kafshdar ; Meggendorfer, Tobias ; Safavi, Roodabeh ; Žikelić, Ðorđe

    Abstract | Document (852 KB) | BibTeX

    Computing Threshold Budgets in Discrete-Bidding Games
    Authors: Avni, Guy ; Sadhukhan, Suman

    Abstract | Document (746 KB) | BibTeX

    Dependency Matrices for Multiplayer Strategic Dependencies
    Authors: Bellier, Dylan ; Pinchinat, Sophie ; Schwarzentruber, François

    Abstract | Document (891 KB) | BibTeX

    Semilinear Representations for Series-Parallel Atomic Congestion Games
    Authors: Bertrand, Nathalie ; Markey, Nicolas ; Sadhukhan, Suman ; Sankur, Ocan

    Abstract | Document (814 KB) | BibTeX

    Playing (Almost-)Optimally in Concurrent Büchi and Co-Büchi Games
    Authors: Bordais, Benjamin ; Bouyer, Patricia ; Le Roux, Stéphane

    Abstract | Document (1,197 KB) | BibTeX

    Ambiguity Through the Lens of Measure Theory
    Authors: Carton, Olivier

    Abstract | Document (693 KB) | BibTeX

    Phase Semantics for Linear Logic with Least and Greatest Fixed Points
    Authors: De, Abhishek ; Jafarrahmani, Farzad ; Saurin, Alexis

    Abstract | Document (914 KB) | BibTeX

    Natural Colors of Infinite Words
    Authors: Ehlers, Rüdiger ; Schewe, Sven

    Abstract | Document (743 KB) | BibTeX

    Synthesizing Dominant Strategies for Liveness
    Authors: Finkbeiner, Bernd ; Passing, Noemi

    Abstract | Document (791 KB) | BibTeX

    Low-Latency Sliding Window Algorithms for Formal Languages
    Authors: Ganardi, Moses ; Jachiet, Louis ; Lohrey, Markus ; Schwentick, Thomas

    Abstract | Document (827 KB) | BibTeX

    The Design and Regulation of Exchanges: A Formal Approach
    Authors: Garg, Mohit ; Sarswat, Suneel

    Abstract | Document (1,086 KB) | BibTeX

    Parikh Automata over Infinite Words
    Authors: Guha, Shibashis ; Jecker, Ismaël ; Lehtinen, Karoliina ; Zimmermann, Martin

    Abstract | Document (792 KB) | BibTeX

    New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages
    Authors: Koechlin, Florent

    Abstract | Document (812 KB) | BibTeX

    Synthesis of Privacy-Preserving Systems
    Authors: Kupferman, Orna ; Leshkowitz, Ofer

    Abstract | Document (838 KB) | BibTeX

    A Generic Polynomial Time Approach to Separation by First-Order Logic Without Quantifier Alternation
    Authors: Place, Thomas ; Zeitoun, Marc

    Abstract | Document (924 KB) | BibTeX

    A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games
    Authors: Thejaswini, K. S. ; Ohlmann, Pierre ; Jurdziński, Marcin

    Abstract | Document (936 KB) | BibTeX

    		  



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