About ACM India Doctoral Dissertation Award

The ACM India 2023 Doctoral Dissertation Award goes to Pranjal Dutta for his dissertation titled “A Tale of Hardness, De-randomization and De-bordering in Complexity Theory.” Pranjal’s dissertation makes breakthrough contributions in the study of hardness, approximation and derandomization of algebraic circuits, and develops new mathematical tools, laying the foundation for future developments in algebraic complexity theory. Pranjal’s dissertation work was done at Chennai Mathematical Institute under the supervision of Prof. Nitin Saxena.

Pranjal Dutta’s dissertation makes multiple contributions to algebraic complexity theory. In an early result, he shows that the existence of a polynomial with a slightly largish special representation would resolve the long-standing VP vs VNP problem, and also provide non-trivial algorithms for polynomial identity testing (PIT) – effectively attacking two flagship problems in algebraic complexity theory. In the context of PIT, his dissertation provides a nearly polynomial time algorithm for derandomization of a special class of depth 4 algebraic circuits, where the top fanin is bounded and the bottom gates compute low degree polynomials. This is among the strongest results in PIT known so far. Pranjal also provides a deep understanding of the power of closure of algebraic circuits -- an important problem in the Geometric Complexity Theory approach to the P vs NP problem. Specifically, he shows that the closure (or border) of (bounded fanin) depth 3 circuits can be captured by algebraic branching programs, making it one of the first such "de-bordering" results in this area. Additionally, his work also establishes an efficient algorithm for PIT for this class, and shows a surprising exponential-gap hierarchy-theorem for depth-3 constant-top-fanin circuits.

The Honorable Mention for 2023 goes to Jogendra Nath Kundu for his dissertation titled “Self-supervised Domain Adaptation Framework for Computer Vision Tasks.” Jogendra’s dissertation makes significant and timely contributions to unsupervised domain adaptation and self-supervised learning techniques for structured prediction based vision tasks, advancing the practical deployment of intelligent machines in real-world scenarios. His dissertation work was done at Indian Institute of Science, Bangalore under the supervision of Prof. Venkatesh Babu Radhakrishnan.

Jogendra Nath Kundu’s doctoral dissertation makes three important contributions. First, he considers image-like dense-prediction tasks, where he addresses shortcomings in existing classification-based domain adaptation algorithms. The content-preserving mechanisms introduced by him via cyclic consistency objectives have been shown to yield state-of-the-art performance. Next, he introduces source-side procurement stage learning, a novel approach to source-free adaptation, which significantly enhances adaptability in scenarios with restricted data-sharing. Finally, Jogendra’s thesis applies domain adaptation concepts to the complex task of 3D human pose estimation. He shows how this can be achieved by incorporation of effective prior-enforcing mechanisms alongside development of novel self-supervised techniques leveraging inter-entity relations. The insights in Jogendra’s dissertation have the potential to revolutionize the deployment of intelligent vision systems across diverse industries, from healthcare to virtual and augmented reality.

The ACM India Doctoral Dissertation Award was established in 2011. This award recognizes the best doctoral dissertation in Computer Science and related disciplines from a degree-awarding institution based in India for each academic year, running from July 1 of one year to June 30 of the following year. The ACM India Doctoral Dissertation Award is accompanied by a prize of ₹2,00,000. An Honorable Mention award, given to nomination(s), if any, that missed the award by a narrow margin, is accompanied by a prize of ₹1,00,000, that is shared among the recipient(s). The winning dissertation(s) will be published in the ACM Digital Library. Tata Consultancy Services Limited (TCS)  is the founding sponsor of these awards. Please see the ACM India Doctoral Dissertation Award page for additional information on current and past winners.

Siddharth Sandipkumar Bhandari is the recipient of the ACM India 2022 Doctoral Dissertation Award for his dissertation titled “Exact Sampling and List Decoding” that develops new techniques and tools in sampling graph colourings and contributes to improved analyses for understanding list-decodability of codes. Siddharth’s doctoral dissertation work was done at Tata Institute of Fundamental Research, Mumbai under the supervision of Prahladh Harsha.

Siddharth’s dissertation makes fundamental contributions to two different areas of theoretical computer science: (a) sampling colourings of graphs and (b) list-decoding error-correcting codes. Sampling a random k-colouring of a given graph is a classic problem in theoretical computer science and statistical physics. The problem of perfect sampling is to construct a polynomial time randomised algorithm that generates a perfect sample from the uniform distribution of k-colourings. Siddharth’s work improves on a two-decade old algorithm for solving this problem using novel techniques that are likely to have wider applicability. In the area of list-decoding, Siddharth’s dissertation focuses on three problems. The first problem is the zero-error capacity of the q/(q 1) channel. Prior work on perfect hashing shows that as the list-size is reduced, the channel capacity decreases from an inverse-polynomial form to an inverse-exponential form, and it has been an open problem to understand where this transition occurs. By showing that the channel follows a coupon-collector like behaviour, Siddharth’s work demonstrates that there is an almost sharp transition near O(q log q). The other two results in this part are related to list-decodability of algebraic codes and lead to a better understanding of the list-decoding of these codes all the way up to capacity.

Pritish Mohapatra shares the Honorable Mention for his dissertation titled “Optimization for and by Machine Learning” that makes significant contributions towards the design of efficient optimization methods for machine learning, including key results for optimizing ranking metrics used in information retrieval systems. Pritish’s doctoral dissertation work was done at International Institute of Information Technology, Hyderabad under the supervision of C. V. Jawahar.

Pritish’s dissertation addresses the problem of making optimization of complicated loss functions efficient and practical. Specifically, he designs a practically efficient optimization algorithm for a category of non-decomposable ranking metrics that greatly improve the feasibility of using such sophisticated metrics for learning in information retrieval tasks. Pritish also provides a concrete theoretical analysis that proves the superiority of the proposed algorithm for optimization, providing a fine balance between the theoretical soundness and practical utility of the algorithms. Pritish’s work also makes an interesting contribution in the use of the classical optimization technique of partial-linearization for efficient learning of large-scale classification models. This holds special significance for learning of models with structured output spaces. Finally, Pritish’s dissertation contributes to the problem of using learning for optimization. He proposes a novel framework that uses a learnable model for doing rounding for combinatorial optimization algorithms. This is based on a key insight that randomized rounding procedures can be visualized as sampling from latent variable models.

Sruthi Sekar shares the Honorable Mention for her dissertation titled “Near-Optimal Non-Malleable Codes and Leakage Resilient Secret Sharing Schemes” that makes fundamental contributions in our understanding of cryptographic primitives such as non-malleable codes, secret sharing schemes and randomness extractors. Sruthi’s doctoral dissertation work was done at Indian Institute of Science, Bangalore under the supervision of Bhavana Kanukurthi.

The goal of non-malleable codes (NMCs) is to enable encoding of messages so that an adversary cannot tamper it into the encoding of a related message. An open problem in this area is to build 1/2-rate NMCs in 2-split state model where a codeword consists of two independently tamperable states. Sruthi’s dissertation makes fundamental contributions to this area. Specifically, she builds on her earlier work to introduce new two-state non-malleable codes for random messages with rate 1/2. This work also introduces a new primitive called "Non-malleable randomness encoders". Her dissertation also shows how to build a near-optimal rate 1/3, 2-state NMC, thereby taking us a step closer to solving the main open problem in this area. In addition, Sruthi’s dissertation introduces a new pseudorandomness primitive called "Adaptive Extractors" and shows their applicability to building constant-rate leakage resilient secret sharing schemes.

Deepika Yadav shares the Honorable Mention for her dissertation titled “Supporting Ongoing Training of Community Health Workers through Mobile-based Solutions in Rural India” that combines the knowledge of Computer System research and HCI to produce systems that are deployed in fields. Her work resulted in deployment of a mobile based training platform for ASHA workers that has been used to train hundreds of ASHA workers. Deepika’s doctoral dissertation work was done at Indraprastha Institute of Information Technology Delhi under the supervision of Pushpendra Singh.

Deepika’s dissertation develops a low-cost mobile-based training platform called “Sangosthi” that allows a geographically distributed group of community health workers (CHWs) to connect over a conference call and receive training in a structured manner. The developed system uses a hybrid architecture to use Interactive Voice Response for facilitating online audio training sessions, enabling CHWs to access training from anywhere through their feature phones. Her work contributes to (i) testing the feasibility and efficacy of a low-cost technology intervention through a controlled field experiment (ii) unpacking the training needs of CHWs in the field and mapping it back to the existing reference material through a large-scale deployment on 500 CHWs, (iii) investigating the potential for peer-to-peer learning models to address the challenge of experts’ availability through a controlled field experiment, and (iv) exploring the potential for automated techniques in this domain by proposing a semi-automated natural language processing approach for curating generated learning content and exposing CHWs and women to Chatbot-based education for the first time. By using a range of mixed methods and field experiments, Deepika’s dissertation expands the focus of HCI4D and mHealth research on CHW competence development in low-resource settings.

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 is accompanied by a prize of ₹1,00,000 which is shared amongst the recipients. The dissertation(s) will be published in the ACM Digital Library. Financial support for both the award and honorable mention is provided by Tata Consultancy Services (TCS). Please see the ACM India Doctoral Dissertation Award page for additional information on current and past winners.