Skip to main content


37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Indian Institute of Technology, Kanpur. December 11–15, 2017.

Click here for the preliminary proceedings of FSTTCS'17.

Session venues:

Tuesday, December 12, 2017
0800 – 0850 Registration
0850 – 0900 Opening Remarks
Invited Talk 1
CHAIR: Paritosh Pandya
0900 – 1000 Thomas Wilke (Christian-Albrechts-Universität zu Kiel)
Backward Deterministic Finite-State Automata on Infinite Words

In this talk we describe why backward deterministic Büchi automata are interesting, how they are defined, what their main features are, and how they can be applied to solve problems in temporal logic.

Session 1A
CHAIR: Nitin Saxena
Session 1B
CHAIR: Madhavan Mukund
1010 – 1040 A Ene, V Nagarajan & R Saket
Approximation Algorithms for Stochastic k-TSP
M F Atig, A Bouajjani, K Narayan Kumar & P Saivasan
Verification of Asynchronous Programs with Nested Locks
1040 – 1110 V Guruswami & R Saket
Hardness of Rainbow Coloring Hypergraphs
B Finkbeiner & P Gölz
Synthesis in Distributed Environments
1110 – 1140 Coffee break
Session 2A
CHAIR: Rajat Mittal
Session 2B
CHAIR: Kamal Lodaya
1140 – 1210 A Chattopadhyay & N Mande
A Lifting Theorem with Applications to Symmetric Functions
L Aceto, A Achilleos, A Francalanza & A. Ingólfsdóttir
Monitoring for Silent Actions
1210 – 1240 A Anshu, D Gavinsky, R Jain, S Kundu, T Lee, P Mukhopadhyay, M Santha & S Sanyal
Composition Theorem for Randomized Query Complexity
S Demri, E Lozes & D Lugiez
On Symbolic Heaps Modulo Permission Theories
1240 – 1400 Lunch
Session 3
CHAIR: Anil Seth
1400 – 1430 V Lagerkvist & B Roy
A Dichotomy Theorem for the Inverse Satisfiability Problem
1430 – 1500 J Michaliszyn, J Otop & P Wieczorek
Querying Best Paths in Graph Databases
1500 – 1530 O Beyersdorff, L Hinde & J Pich
Reasons for Hardness in QBF Proof Systems
1530 – 1600 Coffee Break
Session 4A
CHAIR: Raghunath Tewari
Session 4B
CHAIR: B Srivathsan
1600 – 1630 G Guruganesh & E Lee
Understanding the Correlation Gap for Matchings
D Kini & M Viswanathan
Complexity of Model Checking MDPs against LTL Specifications
1630 – 1700 A Kumar, A Louis & M Tulsiani
Finding Pseudorandom Colorings of Pseudorandom Graphs
A Weinert
VLDL Satisfiability and Model Checking via Tree Automata
1700 – 1730 J Brody, J Boninger & O Kephart
Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search
H Gimbert
On the Control of Asynchronous Automata
Wednesday, December 13, 2017
Invited Talk 2
CHAIR: Sunil Simon
0900 – 1000 Edith Elkind (University of Oxford, UK)
Justified representation in multiwinner voting: axioms and algorithms

Suppose that we want to select a set of k>1 alternatives, and each voter indicates which of the alternatives are acceptable to her: the alternatives could be conference submissions, applicants for a scholarship or locations for a fast food chain. In this setting it is natural to require that the winning set represents the voters fairly, in the sense that large groups of voters with similar preferences have at least some of their approved alternatives in the winning set. In this talk, we show how to formalize this idea and how to use it to classify voting rules; surprisingly, two little-known rules proposed in the 19th century turn out to play an important role in our analysis.

Session 5A
CHAIR: Arkadev Chattopadhyay
Session 5B
CHAIR: S Akshay
1010 – 1040 F Brandl & T Kavitha
Popular Matchings with Multiple Partners
U Boker
Rabin vs. Streett Automata
1040 – 1110 M Nasre & P Nimbhorkar
Popular Matchings with Lower Quotas
M Blondin, A Finkel & J Goubault-Larrecq
Forward Analysis for WSTS, Part III: Karp-Miller Trees
1110 – 1140 Coffee break
Session 6A
CHAIR: Abhiram Ranade
Session 6B
CHAIR: Supratik Chakraborty
1140 – 1210 P K Agarwal, K Fox & A Nath
Maintaining Reeb graphs of triangulated 2-manifolds
J Day, P Fleischmann, F Manea & D Nowotka
Local Patterns
1210 – 1240 O Cagirici, P Hlineny & B Roy
On Colourability of Polygon Visibility Graphs
R Ehlers & B Finkbeiner
Symmetric Synthesis
1240 – 1400 Lunch
Invited Talk 3
CHAIR: Satya Lokam
1400 – 1500 Sham Kakade (University of Washington, USA)
Accelerating Stochastic Gradient

There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, and Nesterov 2014. This work considers the use of “fast gradient” methods for the special case of stochastic approximation for the least squares regression problem. Our main result refutes the conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process.

Session 7
CHAIR: Satya Lokam
1500 – 1530 O Kupferman, G Vardi & M Vardi
Flow Games
1530 – 1600 Coffee Break
Session 8A
CHAIR: Kavitha Telikepalli
Session 8B
CHAIR: K Narayan Kumar
1600 – 1630 A Garg & A Ranade
Train Scheduling on a Unidirectional Path
P Parys
Complexity of the Diagonal Problem for Recursion Schemes
1630 – 1700 Y Huang, M V Janardhanan & L Reyzin
Network Construction with Ordered Constraints
B Bednarczyk & W Charatonik
Modulo Counting on Words and Trees
1700 – 1730 E Grigorescu, E S Azer & S Zhou
Streaming for Aibohphobes: Longest Palindrome with Mis- matches
B Bérard, S Haddad & E Lefaucheux
Probabilistic Disclosure: Maximisation vs. Minimisation
1740 – 1830 IARCS Business Meeting
1900 – 2200 Conference Banquet
Thursday, December 14, 2017
Invited Talk 4
CHAIR: Somenath Biswas
0900 – 1000 Devavrat Shah (MIT, USA)
Matrix Estimation and Collaborative Filtering

Estimating a matrix based on partial, noisy observations is prevalent in variety of modern applications with recommendation system being a prototypical example. The non-parametric latent variable model provides canonical representation for such matrix data when the underlying distribution satisfies ``exchangeability'' with graphons and stochastic block model being recent examples of interest. Collaborative filtering has been a successfully utilized heuristic in practice since the dawn of e- commerce. In this extended abstract, we will argue that collaborative filtering (and its variants) solve matrix estimation for a generic latent variable model with near optimal sample complexity.

This talk is based on joint works with Lee, Li, Shah and Song (2016) and Borgs, Chayes, Lee and Shah (2017).

Session 9A
CHAIR: Vikram Sharma
Session 9B
CHAIR: Deepak D'Souza
1010 – 1040 A Krebs, N Limaye & M Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth
U Boker, O Kupferman & M Skrzypczak
How Deterministic are Good-For-Games Automata?
1040 – 1110 Y Cao, Y Ke, Y Otachi & J You
Vertex Deletion Problems on Chordal Graphs
J Michaliszyn & J Otop
Average Stack Cost of Büchi Pushdown Automata
1110 – 1140 Coffee break
Session 10A
CHAIR: Meghana Nasre
Session 10B
CHAIR: S P Suresh
1140 – 1210 D Lokshtanov, S Saurabh, R Sharma & M Zehavi
Balanced Judicious Partition is FPT
B Rangarajan
A combinatorial proof of Bass’s determinant formula for the zeta function of regular graphs
1210 – 1240 A Agrawal, R Krithika, D Lokshtanov, A Mouawad & Ramanujan M S
On the Parameterized Complexity of Simultaneous Deletion Problems
A Bhangale, S Khot & D Thiruvenkatachari
An Improved Dictatorship Test with Perfect Completeness
1240 – 1400 Lunch
Invited Talk 5
CHAIR: Meena Mahajan
1400 – 1500 Vinod Vaikuntanathan (MIT CSAIL, USA)
The Many Problems in Information-Theoretic Cryptography

Information-theoretic cryptography is chock-full of open problems with a communication-complexity flavor. We will describe several such problems that arise in the study of private information retrieval, multi-party secure computation, secret-sharing, private simultaneous messages (PSM) and conditional disclosure of secrets (CDS). In all these cases, there is a huge (exponential) gap between the best known upper and lower bounds. Our focus will be on describing the (sometimes surprising) connections between these problems, some old and some new.

Session 11
CHAIR: Meena Mahajan
1500 – 1530 K S Meel, A A Shrotri & M Y Vardi
On Hashing-Based Approaches to Approximate DNF-Counting
1530 – 1600 Coffee Break
Invited Talk 6
CHAIR: R Ramanujam
1600 – 1700 Anca Muscholl (LaBRI & Université Bordeaux, France)
Automated synthesis: a distributed viewpoint

Formal methods rely on a clear mathematical understanding of programs and their interactions. The goal of synthesis is to design a program that complies with a given logical specification, and reactive synthesis addresses the question in the setting where programs interact with their environment.

In recent years, synthesis of reactive, distributed programs has gained momentum. The goal is to construct automatically programs and controllers consisting of local entities that can interact in various ways, in order to guarantee a correct behavior. The talk will present that state-of-the-art and some challenges raised by the distributed setting.

1700 – 1710 Closing Remarks