Pranjal Dutta Chosen as the Recipient of the ACM India 2023 Doctoral Dissertation Award

December 30, 2023

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.” Dutta’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. Dutta's dissertation work was done at Chennai Mathematical Institute under the supervision of Prof. Nitin Saxena.

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. Dutta 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.” Kundu'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.

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, Kundus 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 Kundu'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.