ACM India Announces 2020 Doctoral Dissertation Award Winner
January 7, 2020
Jatin Batra of Indian Institute of Technology Delhi has received the ACM India Council's 2020 Doctoral Dissertation Award for "Dynamic Programming for Scheduling Problems."
Advisors: Prof. Naveen Garg and Prof. Amit Kumar
Abstract: In this thesis, we obtain new results for the classical problems of scheduling jobs on a single machine with release dates to minimize weighted flowtime and the weighted version of unsplittable flow on a line. For weighted flowtime, we obtain the first constant approximation in pseudo-polynomial time in a major breakthrough. For unsplittable flow on a line, we obtain the first PTAS for the important uniform density case and the first true QPTAS for the general case, making progress towards the central question of finding a PTAS. For these results, we crucially rely on discovering connections to covering problems, this also provides novel motivation for these covering problems.
Honorable Mention went to K. Venkatesh Emani of Indian Institute of Technology Bombay, for "Optimization of Data Access from Imperative Programs using Static Analysis."
Advisor: Prof. S. Sudarshan
Abstract: Database applications are typically written using a mixture of imperative languages and embedded queries (expressed using SQL/other frameworks) for data access. Traditionally, the imperative and declarative parts of these applications have been optimized separately. Techniques for optimization that span across the declarative and imperative parts in database applications are called holistic optimization techniques. In this thesis, we present novel holistic optimization techniques for optimizing data access in applications that access data using database abstractions. In such applications, data processing logic often gets distributed across the declarative and imperative parts of a program. Consequently, data access from the application is often inefficient due to iterative queries, transfer of unused data, over-specification of queries, and other reasons. We propose techniques based on static program analysis and program transformations to automatically rewrite database applications for efficient data access. When more than one transformations are applicable on a particular program, our techniques can systematically generate all equivalent alternatives using the given set of program transformations, represent these alternatives efficiently, and choose the best rewrite based on a cost model. Similar to database applications, user defined functions in databases contain a mix of imperative code and declarative SQL queries. We build on existing techniques for optimizing the evaluation of user defined functions, with a focus on the implementation of these techniques as part of a commercial database optimizer. We demonstrate that the static analysis techniques we develop can be applied to other optimizations as well as test data generation for queries in database applications. Our experiments on real world and benchmark applications show that our techniques have wide applicability and provide significant performance benefits.
The awards will be distributed on 15 February 2020 during ACM India Annual Event.
The ACM India Doctoral Dissertation Award was established in 2011. This award recognizes the best doctoral dissertation from a degree-awarding institution based in India for each academic year, running from August 1 of one year to July 31 of the following year. The ACM India Doctoral Dissertation Award is accompanied by a prize of ₹2,00,000. An Honorable Mention award, if any, is accompanied by a prize of ₹1,00,000. The dissertation(s) will be published in the ACM Digital Library. Tata Consultancy Services Limited (TCS) is the founding sponsor of the ACM India Doctoral Dissertation Award. Please see the ACM India Doctoral Dissertation Award page for additional information on current and past winners.
