FSTTCS 2018
38th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 10–14, 2018
School of Engineering and Applied Science
Ahmedabad University
38th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 10–14, 2018
School of Engineering and Applied Science
Ahmedabad University
Click here for the FSTTCS'18 proceedings.
Ramprasad Saptharishi and Anamay Tengse
Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees
Amy Babay, Michael Dinitz and Zeyu Zhang
Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network
Emmanuel Filiot, Olivier Gauwin , Nathan Lhote and Anca Muscholl
On Canonical Models for Rational Functions over Infinite Words
Damien Busatto-Gaston, Benjamin Monmege and Pierre-Alain Reynier
Symbolic Approximation of Weighted Timed Games
Deepanjan Kesh
Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements
Alessio Mansutti
Extending propositional separation logic for robustness properties
Ágnes Cseh and Telikepalli Kavitha
Popular Matchings in Complete Graphs
Sougata Bose, Anca Muscholl , Vincent Penelle and Gabriele Puppis
Origin-equivalence of two-way word transducers is in PSPACE
Marc Bagno and Denis Kuperberg
Büchi Good-for-Games automata are efficiently recognizable
Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg , Naveen Garg , Martin Hoefer and Kurt Mehlhorn
On Fair Division for Indivisible Items
Beatrice Berard, Stefan Haar and Loic Helouet
Hyper Partial Order Logic
Kazuyuki Asada and Naoki Kobayashi
Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
Alexandre Debant, Stephanie Delaune and Cyrille Wiedling
Proving physical proximity using symbolic models
Janusz Schmude, Adrien Boiret and Radosław Piórkowski
The “Hilbert Method” for Solving Transducer Equivalence Problems
Udi Boker and Karoliina Lehtinen
On The Way to Alternating Weak Automata
Gilles Geeraerts, Shibashis Guha and Jean-Francois Raskin
Safe and Optimal Scheduling for Hard and Soft Tasks
Markus Bläser, Balagopal Komarath and Karteek Sreenivasaiah
Graph Pattern Polynomials
Mohsen Alambardar Meybodi, Fedor V. Fomin, Amer E. Mouawad and Fahad Panolan
On the parameterized complexity of [1,j]-domination problems
Faried Abu Zaid and Chris Köcher
The Cayley-Graph of the Queue Monoid: Logic and Decidability
Sumedh Tirodkar
Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model
Anantha Padmanabha, R. Ramanujam and Yanjing Wang
Bundled fragments of first order modal logic: (un)decidability
Faried Abu Zaid
Uniformly Automatic Classes of Finite Structures
V. Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
Swaroop N P and Vikram Sharma
Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
Alain Finkel, Jérôme Leroux and Grégoire Sutre
Reachability for Two-Counter Machines with One Test and One Reset
Karl Bringmann and Bhaskar Ray Chaudhury
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
Stephane Le Roux, Arno Pauly and Mickael Randour
Extending finite-memory determinacy to Boolean combinations of winning conditions
Samir Datta, Siddharth Iyer, Raghav Kulkarni and Anish Mukherjee
Shortest k-Disjoint Paths via Determinants
Bhaskar Ray Chaudhury and Kurt Mehlhorn
Combinatorial Algorithms for General Linear Arrow-Debreu Markets
Sapna Grover, Neelima Gupta , Samir Khuller and Aditya Pancholi
Constant factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem
Furio Honsell, Luigi Liquori , Claude Stolze and Ivan Scagnetto
The ∆-framework
Vincent Penelle, Sylvain Salvati and Grégoire Sutre
On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems
Siddharth Bhandar, Prahladh Harsha , Tulasimohan Molli and Srikanth Srinivasan
On the Probabilistic Degree of OR over the Reals
Junjie Luo, Hendrik Molter, André Nichterlein and Rolf Niedermeier.
Parameterized Dynamic Cluster Editing
Elazar Goldenberg and Karthik C. S.
Towards a General Direct Product Testing Theorem
Balthazar Bauer, Jevgēnijs Vihrovs and Hoeteck Wee
On the Inner Product Predicate and a Generalization of Matching Vector Families
Thomas Place and Marc Zeitoun
The complexity of separation for levels in concatenation hierarchies
Siddhesh Chaubal and Anna Gal
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
Umang Bhaskar and Abheek Ghosh
On the Welfare of Cardinal Voting Mechanisms
Pierre Ganty and Elena Gutiérrez
The Parikh Property for Weighted Context-Free Grammars
Pranabendu Misra, Roohani Sharma, Saket Saurabh and Meirav Zehavi
Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
Manisha Bansal, Naveen Garg and Neelima Gupta
A 5-approximation for Universal Facility Location
David Baelde, Anthony Lick and Sylvain Schmitz
A Hypersequent Calculus with Clusters for Tense Logic over Ordinals
Parosh Abdulla, Mohamed Faouzi Atig, Krishna S and Shaan Vaidya
Verification of Timed Asynchronous Programs