FSTTCS 2022
42nd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
- Main Conference: December 18–20, 2022
- Pre-Conference Workshops: December 15–17, 2022
- Venue: IIT Madras
42nd IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
Joshua Cook
More Verifier Efficient Interactive Protocols For Bounded Space
Ramita Maharjan and Thomas Watson
Complexity of Fault Tolerant Query Complexity
Olivier Carton
Ambiguity through the lens of measure theory
Jasine Babu, R. Krithika and Deepak Rajendraprasad
Packing Arc-Disjoint 4-Cycles in Oriented Graphs
Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan and Ocan Sankur
Semilinear Representations for Series-Parallel Atomic Congestion Games
Pranav Bisht and Nitin Saxena
Derandomization via symmetric polytopes: Poly-time factorization of certain sparse polynomials
Utkarsh Joshi, Saladi Rahul and Josson Thoppil
A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs
Benjamin Bordais, Patricia Bouyer and Stephane Le Roux
Playing (Almost-)Optimally in Concurrent Büchi and co-Büchi Games
Pascal Koiran and Subhayan Saha
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms
Arjan Cornelissen, Nikhil Mande and Subhasree Patro
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismael Jecker and Jakub Svoboda
Complexity of Spatial Games
Pranav Bisht and Ilya Volkovich
On Solving Sparse Polynomial Factorization Related Problems
Vijay Vazirani
New Characterizations of Core Imputations of Matching and $b$-Matching Games
Guy Avni and Suman Sadhukhan
Computing Threshold Budgets in Discrete Bidding Games
Bernd Finkbeiner and Noemi Passing
Synthesizing Dominant Strategies for Liveness
Rüdiger Ehlers and Sven Schewe
Natural Colors of Infinite Words
Florent Koechlin
New analytic techniques for proving the inherent ambiguity of context-free languages
Telikepalli Kavitha
Stable Matchings with One-Sided Ties and Approximate Popularity
Moses Ganardi, Louis Jachiet, Markus Lohrey and Thomas Schwentick
Low-Latency Sliding Window Algorithms for Formal Languages
Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri and Chao Xu
Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
Gianfranco Bilardi and Lorenzo De Stefani
The DAG Visit approach for Pebbling and I/O Lower Bounds
Oded Lachish, Felix Reidl and Chhaya Trehan
When you come at the king you best not miss
Abhishek De, Farzad Jafarrahmani and Alexis Saurin
Phase semantics for linear logic with least and greatest fixed points
Arindam Khan, Eklavya Sharma and K. V. N. Sreenivas
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer and Vladimir Lysikov
Degree-restricted strength decompositions and algebraic branching programs
Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas Nandy and Alex Pahlow
Half-Guarding Weakly-Visible Polygons and Terrains
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra and Manaswi Paraashar
Counting and Sampling from Substructures using Linear Algebraic Queries
Orna Kupferman and Ofer Leshkowitz
Synthesis of Privacy-Preserving Systems
Thomas Place and Marc Zeitoun
A generic polynomial time approach to separation by first-order logic without quantifier alternation
Rohith Reddy Gangam, Tung Mai, Nitya Raju and Vijay V. Vazirani
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications
Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale and Gaurav Viramgami
Romeo and Juliet Meeting in Forest Like Regions
K. S. Thejaswini, Pierre Ohlmann and Marcin Jurdzinski
A technique to speed up symmetric attractor-based algorithms for parity games
Radu Curticapean, Nutan Limaye and Srikanth Srinivasan
On the VNP-hardness of Some Monomial Symmetric Polynomials
Arkadev Chattopadhyay, Utsab Ghosal and Partha Mukhopadhyay
Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product
Dylan Bellier, Sophie Pinchinat and Francois Schwarzentruber
Dependency Matrices for Multiplayer Strategic Dependencies
Ali Ahmadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi and Đorđe Žikelić
Algorithms and Hardness Results for Computing Cores of Markov Chains
Mohit Garg and Suneel Sarswat
The Design and Regulation of Exchanges: A Formal Approach
Minati De, Saksham Jain, Sarat Varma Kallepalli and Satyam Singh
Online Piercing of Geometric Objects
Hee-Kap Ahn, Sang Won Bae, Chung Jaehoon, Chan-Su Shin and Sang Duk Yoon
Inscribing or Circumscribing a Histogon to a Convex Polygon
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen and Martin Zimmermann
Parikh Automata over Infinite Words