FSTTCS 2017
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Indian Institute of Technology, Kanpur. December 11–15, 2017.
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Indian Institute of Technology, Kanpur. December 11–15, 2017.
Session venues:
Tuesday, December 12, 2017  
0800 – 0850  Registration  
0850 – 0900  Opening Remarks  
Invited Talk 1 CHAIR: Paritosh Pandya 

0900 – 1000 
Thomas Wilke (ChristianAlbrechtsUniversität zu Kiel) Backward Deterministic FiniteState 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 kTSP 
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 NonAdaptive 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 littleknown rules proposed in the 19^{th} 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 GoubaultLarrecq Forward Analysis for WSTS, Part III: KarpMiller 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 2manifolds 
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 nonparametric 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 GoodForGames 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 InformationTheoretic Cryptography Informationtheoretic cryptography is chockfull of open problems with a communicationcomplexity flavor. We will describe several such problems that arise in the study of private information retrieval, multiparty secure computation, secretsharing, 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 HashingBased Approaches to Approximate DNFCounting 

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 stateoftheart and some challenges raised by the distributed setting. 

1700 – 1710  Closing Remarks 