Research Interests

Theoretical computer science; more specifically, algorithms on large data sets, sublinear algorithms, approximation algorithms, graph algorithms, and data structures.

Brief Bio: I did my PhD from Indian Institute of Technology, Kanpur under the supervision of Prof. Manindra Agrawal and Prof. Satyadev Nandakumar. After that I spent two years at Charles University, Prague, Czech Republic as a post-doctoral fellow hosted by Prof. Michal Koucky, and then almost a year at Weizmann Institute of Science, Israel as a post-doctoral fellow hosted by Prof. Robert Krauthgamer.

Teaching

• Algorithms at Scale (CS5234) Fall '22, Fall '23, Fall '24 NUS

• Advanced Algorithms  (CS6234)                       Fall '20, Fall '21            NUS

• Design and Analysis of Algorithms (CS3230) Spring '20 (co-taught with Ken Sung), Spring '21    NUS

Spring '23 (co-taught with Steven Halim)

Spring '24 (co-taught with Steven Halim and Sanjay Jain)

• Data Structure Lower Bounds             Spring '18      Charles University, Prague

• Boolean Function Complexity           Fall '16            Charles University, Prague

Students and Postdocs

• Kushagra Chatterjee (Ph.D., Aug 2021 - present)

• Yan Hong Yao Alvin (Ph.D., Jan 2021 - present)

• Kanchana Ruwanpathirana (Research Fellow, July 2024 - present)

• Nidhi Purohit (Research Fellow, June 2024 - present)

• Sanjana Dey (Research Fellow,  Oct 2022 - Nov 2024)

• Kshitij Gajjar (Research Fellow, Apr 2021 - Apr 2022)

• Gunjan Kumar (Research Fellow, jointly with Kuldeep S. Meel,  Feb 2021 - Aug 2024)

• Lawqueen Kanesh (Research Fellow, jointly with Kuldeep S. Meel,  Jan-Dec 2021)

Selected Talks

• Tight Bound on Equivalence Testing in Conditional Sampling Model

  • • UMD College Park, USA, May 2024

    • UC San Diego, USA, December 2023

• Matrix Completion: Approximating the Minimum Diameter

  • • EPAC Workshop: Algorithms and Complexity, May 2023

• Clustering Permutations: Offline to Streaming

  • • UC Santa Barbara, USA, December 2023

    • UC Riverside, USA, December 2023

    • ISI Kolkata, India, December 2022

• Support Size Estimation: The Power of Conditioning

  • • Complexity Theory with a Human Face, June 2022

• Aggregating a Data Set: Rankings to Strings

  • • CFCS TCS Day, Peking University, China, June 2022

    • Recent Trends in Algorithms 2022, March 2022

• Approximate Trace Reconstruction via Median String (in Average-Case)

  • • Conference talk at FSTTCS 2021, December 2021

• Hardness of Approximation of (Multi-)LCS over Small Alphabet

  • • Workshop on Sensitivity, Query Complexity, Communication Complexity and Fourier Analysis of Boolean Function at ISI Kolkata, India, February 2020

• Edit Distance: Constant-factor approximation, Embedding and Streaming

  • • Aalto University, Finland, March 2019

    • NUS, Singapore, March 2019

    • Royal Holloway, University of London, UK, March 2019

•   Truly Sub-quadratic Time Constant Factor Approximation of Edit Distance

  • • Invited Highlight Talk at CPM 2019, Italy, June 2019

    • Bar-Ilan University, Israel, May 2019

    • University of Warwick, UK, February 2019

    • University of Bristol, UK, February 2019

• Tight Cell Probe Bound for Succinct Boolean Matrix-Vector Multiplication

  • • Interactive Complexity workshop at Simons Institute, Berkeley, USA, October 2018

    • Summer School on Algorithms and Lower Bounds, Satellite workshop of ICALP 2018, July 2018

• Sparse Weight Tolerant Subgraph for Single Source Shortest Path

  • • Conference talk at SWAT 2018, June 2018

• Optimal Quasi-Gray Codes: Efficient Generation using Simplicity of Even Permutations

  • • Dartmouth College, USA, February 2018 (over Skype)

    • KTH, Sweden, February 2018

    • IIT Kanpur, January 2018

• Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime

  • • Conference talk at STOC 2016, June 2016

    • IIT Delhi, January 2016

    • Theory Days 2015, IIT Kanpur, November 2015

• Dimension, Pseudorandomness and Extraction of Pseudorandomness

  • • Conference talk at FSTTCS 2015, December 2015

• An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

  • • Charles University in Prague, March 2016

    • Conference talk at ISAAC 2015, December 2015

    • Theory lunch, The Chinese University of Hong Kong, January 2015

• Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs

  • • Conference talk at WALCOM 2015, February 2015