Assistant Professor
National University of Singapore
Email: <firstname> at nus dot edu dot sg
Embedded Files
Research Interests
Research Interests
Theoretical computer science; more specifically, algorithms on large data sets, sublinear algorithms, approximation algorithms, algorithmic fairness, 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.
Publications
Publications
Maximizing Diversity in (near-)Median String Selection
with Rudrayan Kundu, Nidhi Purohit, and Aravinda Kanchana Ruwanpathirana
CPM 2026
A Generic Framework for Fair Consensus Clustering in Streams
with Kushagra Chatterjee, Debarati Das, and Tien Long Nguyen
AAMAS 2026 (oral presentation)
Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications
with Kushagra Chatterjee, Debarati Das, and Tien Long Nguyen
AAAI 2026 (oral presentation)
Towards Fair Representation: Clustering and Consensus
with Kushagra Chatterjee, Debarati Das, Tien Long Nguyen, and Romina Nobahari
COLT 2025
Improved Rank Aggregation under Fairness Constraint
with Yan Hong Yao Alvin, Himika Das, and Sanjana Dey
IJCAI 2025
Equivalence Testing: The Power of Bounded Adaptivity
with Sourav Chakraborty, Gunjan Kumar, and Kuldeep S. Meel
AISTATS 2024
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
with Sourav Chakraborty and Gunjan Kumar
SODA 2024
Approximate Maximum Rank Aggregation: Beyond the Worst-Case
with Yan Hong Yao Alvin
FSTTCS 2023
Matrix Completion: Approximating the Minimum Diameter
with Sanjana Dey
ISAAC 2023
Support Size Estimation: The Power of Conditioning
with Gunjan Kumar and Kuldeep S. Meel
MFCS 2023
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
with Sourav Chakraborty, Gunjan Kumar, and Kuldeep S. Meel
ICALP 2023 (Track B)
Clustering Permutations: New Techniques with Streaming Applications
with Debarati Das and Robert Krauthgamer
ITCS 2023
with Syamantak Das, Arindam Khan, and Aditya Subramanian
NeurIPS 2022
Pairwise Reachability Oracles and Preservers under Failures
with Kushagra Chatterjee and Keerti Choudhary
ICALP 2022 (Track A)
Approximating the Center Ranking under Ulam
with Kshitij Gajjar and Agastya Vibhuti Jha
FSTTCS 2021
Approximate Trace Reconstruction via Median String (in Average-Case)
with Debarati Das and Robert Krauthgamer
FSTTCS 2021
Approximating the Median under the Ulam Metric
with Debarati Das and Robert Krauthgamer
SODA 2021
Hardness of Approximation of (Multi-)LCS over Small Alphabet
with Amey Bhangale and Rajendra Kumar
APPROX 2020
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
with Keerti Choudhary
ICALP 2020 (Track A)
Also to appear in ACM Transactions on Algorithms (TALG) (2025)
Approximate Online Pattern Matching in Sub-linear Time
with Debarati Das and Michal Koucky
FSTTCS 2019
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
with Debarati Das, Elazar Goldenberg, Michal Koucky, and Michael Saks
FOCS 2018 (co-winner of best paper award)
Also appeared in Journal of the ACM (JACM) 67(6), 36:1--36:22 (2020) (invited)
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity
with Debarati Das, Michal Koucky, and Nitin Saurabh
ESA 2018 (Track A)
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
with Lior Kamma and Kasper Green Larsen
STOC 2018
Sparse Weight Tolerant Subgraph for Single Source Shortest Path
with Debarati Das
SWAT 2018
On Resource-bounded versions of the van Lambalgen theorem
with Satyadev Nandakumar and Himanshu Shukla
TAMC 2017
Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime
with Elazar Goldenberg and Michal Koucky
STOC 2016 and HALG 2016
Dimension, Pseudorandomness and Extraction of Pseudorandomness
with Manindra Agrawal, Debarati Das, and Satyadev Nandakumar
FSTTCS 2015
Also appeared in Computability - The Journal of the Association Computability in Europe 6(3): 277-305 (2017)
An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
with Raghunath Tewari
ISAAC 2015
Also appeared in ACM Transactions on Computation Theory (TOCT) 9(4), 19:1--19:11 (2018)
Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs
with Raghunath Tewari
WALCOM 2015
An extended version can be found here
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs
with A. Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin Forrest Yang
FSTTCS 2014
Other Technical Reports:
Clustering with Label Consistency
with Hendrik Fichtenberger, Bernhard Haeupler, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson
with Kiarash Banihashem, Shayan Chashm Jahan, Iman Gholami, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, and Max Springer
On Approximability of Propositional Model Counting
with Lawqueen Kanesh and Kuldeep S. Meel
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
with Elazar Goldenberg and Michal Koucky
Derandomization & Time-Space Trade-off in Efficient Computation
PhD Thesis (2016)
Open Positions
Open Positions
Multiple Ph.D. Openings: Currently, I am looking for highly motivated Ph.D. students. If you are interested, please write to me to schedule a meeting and discuss. Note candidates need to get admission to the School of Computing. For detailed information regarding the admission procedure, see here. International students can also apply for the SINGA award.
Internship Opportunity: I am happy to invite graduate students for short-term internship positions. If you are interested, please email me along with your cv.
Contact Address
Contact Address
COM3-02-55,
School of Computing,
National University of Singapore,
11 Research Link, Singapore 119391.
Email: <firstname> at comp dot nus dot edu dot sg
Teaching
Teaching
Optimization Algorithms (CS4234) Fall '25 NUS
Data Structures and Algorithms (CS2040S) Spring '25, '26 NUS
Algorithms at Scale (CS5234) Fall '22, '23, '24 NUS
Advanced Algorithms (CS6234) Fall '20, '21 NUS
Design and Analysis of Algorithms (CS3230) Spring '20, '21, '23, '24 NUS
Data Structure Lower Bounds Spring '18 Charles University, Prague
Boolean Function Complexity Fall '16 Charles University, Prague
Students and Postdocs
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 - Dec 2025)
Nidhi Purohit (Research Fellow, June 2024 - June 2025)
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
Selected Talks
Fair Rank Aggregation
ISI Kolkata, December 2025
IIIT Delhi, IIT Delhi, IIT Kanpur, August 2025
IIT Bombay, July 2025
Freie Universität Berlin, Germany, July 2025
STCS Seminar, TIFR, May 2025
Workshop on Voting, Matching, and Preference Aggregation, Singapore, December 2024
Consistent Clustering
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, Czechia, 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
Page updated
Google Sites
Report abuse