FSTTCS 2019
39th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 11–13, 2019
Indian Institute of Technology Bombay39th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 11–13, 2019
Indian Institute of Technology BombaySession venues:
Wednesday, December 11, 2019 | ||
0820 – 0850 | Registration | |
0850 – 0900 | Opening | |
Invited Talk 1 CHAIR: Arkadev Chattopadhyay |
||
0900 – 1000 |
Tim Roughgarden How Computer Science Informs Modern Auction Design |
|
1000 – 1015 | Small break | |
Session A1 CHAIR: Nutan Limaye |
Session B1 CHAIR: S Krishna |
|
1015 – 1045 |
Diptarka Chakraborty, Debarati Das and Michal Koucky Approximate Online Pattern Matching in Sublinear Time |
Nathalie Bertrand, Patricia Bouyer and Anirban Majumdar Concurrent parameterized games |
1045 – 1115 |
Kanthi Sarpatwar, Baruch Schieber and Hadas Shachnai The Preemptive Resource Allocation Problem |
Thomas Brihaye, Gilles Geeraerts, Marion Hallet, Benjamin Monmege and Bruno Quoitin Dynamics on Games: Simulation-Based Techniques and Applications to Routing |
1115 – 1145 | Coffee break | |
Session A2 CHAIR: Rohit Gurjar |
Session B2 CHAIR: Alain Finkel |
|
1145 – 1215 |
Prerona Chatterjee and Ramprasad Saptharishi Constructing Faithful Homomorphisms over Fields of Finite Characteritic |
Ramanathan Thinniyam Srinivasan and Georg Zetzsche Regular Separability and Intersection Emptiness are Independent Problems |
1215 – 1245 |
V. Arvind, Abhranil Chatterjee, Rajit Dutta and Partha Mukhopadhyay Fast Exact Algorithms Using Hadamard Product of Polynomials |
David Mestel Widths of regular and context-free languages |
1245 – 1400 | Lunch break | |
Invited Talk 2 CHAIR: Paul Gastin |
||
1400 – 1500 |
Ranko Lazić Finkel was right: Counter-examples to several conjectures on variants of vector addition systems |
|
1500 – 1515 | Small break | |
Session A3 CHAIR: Kavitha Telikepalli |
Session B3 CHAIR: Benjamin Monmege |
|
1515 – 1545 |
Giorgio Lucarelli, Benjamin Moseley, Nguyen Thang, Abhinav Srivastav and Denis Trystram Online Non-preemptive Scheduling to Minimize Maximum Weighted Flow-time on Related Machines |
S Akshay, Hugo Bazille, Eric Fabre and Blaise Genest Classification among Hidden Markov Models |
1545 – 1615 |
Roy Schwartz, Mohit Singh and Sina Yazdanbod Online and Offline Algorithms for Circuit Switch Scheduling |
Benjamin Bordais, Shibashis Guha and Jean-Francois Raskin Expected Window Mean-Payoff |
1615 – 1645 | Coffee break | |
Session A4 CHAIR: Piyush Srivastava |
Session B4 CHAIR: B Srivathsan |
|
1645 – 1715 |
Jan Dreier and Peter Rossmanith Motif Counting in Preferential Attachment Graphs |
Laura Bozzelli, Angelo Montanari and Adriano Peron Taming complexity of timeline-based planning over dense temporal domains |
1715 – 1745 |
Anand Louis and Rakesh Venkat Planted Models for k-way Edge and Vertex Expansion |
Jeffrey M. Dudek and Dror Fried Transformations of Boolean Functions |
Thursday, December 12, 2019 | ||
Invited Talk 3 CHAIR: Sanjiva Prasad |
||
0900 – 1000 |
Alexandra Silva An algebraic framework to reason about concurrency |
|
1000 – 1015 | Small break | |
Session A5 CHAIR: Ramprasad Saptharishi |
Session B5 CHAIR: C Aiswarya |
|
1015 – 1045 |
Sebastian Tavenas, Maud Szusterman, Guillaume Malod and Herve Fournier Nonnegative Rank Measures and Monotone Algebraic Branching Programs |
Salvatore La Torre and P. Madhusudan Reachability in Concurrent Uninterpreted Programs |
1045 – 1115 |
Srikanth Srinivasan, Utkarsh Tripathi and S Venkitesh On the Probabilistic Degrees of Symmetric Boolean Functions |
Peter Chini, Prakash Saivasan and Roland Meyer Complexity of Liveness in Parameterized Systems |
1115 – 1145 | Coffee break | |
Session A6 CHAIR: Ruta Mehta |
Session B6 CHAIR: Benedikt Bollig |
|
1145 – 1215 |
Gordon Hoi, Sanjay Jain and Frank Stephan A Fast Algorithm for Max Hamming Distance X3SAT |
Emmanuel Filiot, Shibashis Guha and Nicolas Mazzocchi Two-way Parikh Automata |
1215 – 1245 |
Telikepalli Kavitha Popular Roommates in Simply Exponential Time |
M Praveen and Agnishom Chattopadhyay Query Preserving Watermarking Schemes for Locally Treelike Databases |
1245 – 1400 | Lunch break | |
Invited Talk 4 CHAIR: Jaikumar Radhakrishnan |
||
1400 – 1500 |
Robert Krauthgamer Sketching Graphs and Combinatorial Optimization |
|
1500 – 1515 | Small break | |
Session A7 CHAIR: Srikanth Srinivasan |
Session B7 CHAIR: Sunil Simon |
|
1515 – 1545 |
Rahul Jain and Raghunath Tewari An O(n¼ + ε) Space and Polynomial Algorithm for Grid Graph Reachability |
Laura Bozzelli, Angelo Montanari and Adriano Peron Interval temporal logic for visibly pushdown systems |
1545 – 1615 |
Sanjana Kolisetty, Linh Le, Ilya Volkovich and Mihalis Yannakakis The Complexity of Finding S-factors in Regular Graphs |
Manfred Droste, Sven Dziadek and Werner Kuich Greibach Normal Form for ω-Algebraic Systems and Weighted Simple ω-Pushdown Automata |
1615 – 1645 | Coffee break | |
Session A8 |
Session B8 CHAIR: Madhavan Mukund |
|
1645 – 1715 |
Fabio Gadducci, Hernan Melgratti, Matteo Sammartino and Christian Roldan A Categorical Account for the Specification of Replicated Data Type |
|
1715 – 1830 | IARCS Business Meeting | |
1930 – 2230 | Conference Banquet | |
Friday, December 13, 2019 | ||
Invited Talk 5 CHAIR: Arkadev Chattopadhyay |
||
0900 – 1000 |
Toniann Pitassi Progress in Lower Bounds and Applications in Lifting |
|
1000 – 1015 | Small break | |
Session A9 CHAIR: Meena Mahajan |
Session B9 CHAIR: Dietrich Kuske |
|
1015 – 1045 |
Aditya Potukuchi On the AC0[⊕] complexity of Andreev's Problem |
Marco Kuhlmann, Andreas Maletti and Lena Katharina Schiffer The Tree-Generative Capacity of Combinatory Categorial Grammars |
1045 – 1115 |
Nutan Limaye, Srikanth Srinivasan and Utkarsh Tripathi More on AC0[⊕] and Variants of the Majority Function |
Alexander Rabinovich and Doron Tiferet Degrees of Ambiguity of Büchi Tree Automata |
1115 – 1145 | Coffee break | |
Session A10 CHAIR: Michal Koucky |
Session B10 CHAIR: M Praveen |
|
1145 – 1215 |
Chetan Gupta, Rahul Jain, Vimal Raj Sharma and Raghunath Tewari Unambiguous Catalytic Computation |
Jérôme Leroux Distance Between Mutually Reachable Petri Net Configurations |
1215 – 1245 |
Yujin Choi, Seungjun Lee and Hee-Kap Ahn Maximum-Area Rectangles in a Simple Polygon |
Alain Finkel and Ekanshdeep Gupta The well structured problem for Presburger counter machines |
1245 – 1400 | Lunch break | |
Invited Talk 6 CHAIR: Anca Muscholl |
||
1400 – 1500 |
Karthikeyan Bhargavan Practical Formal Methods for Real World Cryptography |
|
1500 – 1515 | Small break | |
Session A11 CHAIR: Jaikumar Radhakrishnan |
Session B11 CHAIR: Paolo Baldan |
|
1515 – 1545 |
Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh and Roohani Sharma Exact and Approximate Digraph Bandwidth |
Denis Kuperberg, Laureline Pinault and Damien Pous Cyclic Proofs and Jumping Automata |
1545 – 1615 |
Isolde Adler, Christophe Paul and Dimitrios Thilikos Connected Search for a Lazy Robber |
Hans Kleine Büning, Piotr Wojciechowski and K Subramani New results on cutting plane proofs for Horn constraint systems |
1615 – 1645 | Coffee break | |
Session A12 CHAIR: Kavitha Telikepalli |
Session B12 CHAIR: Bharat Adsul |
|
1645 – 1715 |
Fedor Fomin, Peter Golovach and Kirill Simonov Parameterized k-Clustering: Tractability Island |
Alexandre Mansard Boolean algebras from trace automata |
1715 – 1745 |
Akansha Agrawal, Arindam Biswas, Edouard Bonnet, Nick Brettell, Radu Curticapean, Daniel Marx, Tillman Miltzow, Venkatesh Raman and Saket Saurabh Parameterized Streaming Algorithms for Min-Ones d-SAT |
Paolo Baldan and Alessandra Raffaeta Minimisation of Event Structures |