Research

Bounded Relativization

Advisor: Marco Carmosino

Collaborator: Rene Reyes

Institution: Boston University, USA

Duration: November 2023 – Present

• Studying the paradigm of Bounded Relativisation introduced by Hirahara, Liu, and Ren in 2023.

• Examining the Bounded Relativisation of Algorithmic Method implications.

• Revisiting axiomatic definitions of oracle-access frameworks and investigating their limitations.

Lipschitz Testing

Advisor: Sofya Raskhodnikova

Collaborator: Ephraim Linder

Institution: Boston University, USA

Duration: November 2023 – Present

• Working on query lower bounds for Lipschitz testing in different property testing paradigms (e.g. tolerant testing, erasure-resilient testing).

• Investigating the power of adaptivity for Lipschitz testing algorithms.

Multi-Agent Contratcs

Advisor: Kira Goldner

Collaborator: Thodoris Tsilivis

Institution: Boston University, USA

Duration: November 2023 – Present

• Studying the seminal work on multi-agent contracts by Duetting, Ezra, Feldman, and Kesselheim in 2023.

• Working on improved approximation algorithms in this setting, and extensions to related contract problems.

Matching Algorithms in Sublinear Time

Advisors: Claire Mathieu, Frederic Magniez

Institution: Institut de recherche en informatique fondamentale (IRIF; English: Fundamental Computing Research Institute), France

Duration: May 2023 – Present

• Studied sublinear time algorithms for approximating the maximum matching of a graph.

• Currently working on designing algorithms with improved parameters and extending these algorithmic techniques to related graph problems.

• This collaboration was set up as part of an exchange program hosted by CNRS for top-ranking senior students at Chennai Mathematical Institute, India.

Ulam Metric Median

Advisor: Diptarka Chakraborty

Institution: National University of Singapore, Singapore

Duration: December 2022 - January 2023

• Investigated computational properties of the Ulam metric.

• Studied complexity-theoretic properties and reductions for problems on computing medians under various metrics like k-distance and edit distance.

• Constructed reductions to prove the NP-hardness of computing a variant of the LCS (longest common subsequence) problem over permutations.

Local Computation Algorithms

Advisor: Nithin Varma

Institution: Chennai Mathematical Institute, India

Duration: May 2022 – December 2022

• Studied the model of Local Computation Algorithms (LCAs) introduced by Rubinfeld, Tamir, Vardi, and Xie in 2011.

• Presented LCAs for Maximal Independent Set, Hypergraph Two Colouring and other structures like Random Query Trees. The slides from my presentations are available here.

• Writing a survey on the key techniques used in LCAs.

• Designed LCAs for problems on numerical sequences.