Manoj Gupta

Conference Publications

1. Õptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost
   Manoj Gupta and Mrigankashekhar Shandilya
   FOCS 2026
2. Approximate Single Source Dual Fault Tolerant Distance Oracle
   Koustav Das and Manoj Gupta
   ESA 2026
3. Dynamic MIS Revisited: Incremental, Fault Tolerant and Fully Dynamic
   Manoj Gupta, Shahbaz Khan and Madhu Surendra
   SWAT 2026
4. Improved 2-Approximate Shortest Paths for close vertex pairs
   Manoj Gupta
   FOCS 2025
5. Near Optimal Dual Fault Tolerant Distance Oracle
   Dipan Dey and Manoj Gupta
   ESA 2024
6. The Group Access Bounds for Binary Search Trees
   Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek and Sorrachai Yingchareonthawornchai
   ICALP 2024
7. Nearly Optimal Fault Tolerant Distance Oracle
   Dipan Dey and Manoj Gupta
   STOC 2024
   There was an error in this paper and we have retracted this result. Please see the comments in the arXiv version for details.
8. Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
   Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek and Sorrachai Yingchareonthawornchai
   SODA 2023
9. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem
   Dipan Dey and Manoj Gupta
   ESA 2022
10. Output Sensitive Fault Tolerant Maximum Matching
    Niranka Banerjee, Manoj Gupta, Venkatesh Raman and Saket Saurabh
    CSR 2022
11. Simple dynamic algorithms for Maximal Independent Set, Maximum Flow and Maximum Matching
    Manoj Gupta and Shahbaz Khan
    SOSA 2021
12. Multiple Source Replacement Path Problem
    Manoj Gupta, Rahul Jain and Nitiksha Modi
    PODC 2020
13. On the Complexity of Optimal Matching Reconfiguration
    Manoj Gupta, Hitesh Kumar and Neeldhara Misra
    SOFSEM 2019
14. Generic Single Edge Fault Tolerant Exact Distance Oracle
    Manoj Gupta and Aditi Singh
    ICALP 2018
15. Improved Algorithm for Dynamic b-Matching
    Sayan Bhattacharya, Manoj Gupta and Divyarthi Mohan
    ESA 2017
16. Multiple Source Dual Fault Tolerant BFS Trees
    Manoj Gupta and Shahbaz Khan
    ICALP 2017
17. CAPReS: Context Aware Persona Based Recommendation for Shoppers
    Joydeep Banerjee, Gurulingesh Raravi, Manoj Gupta, Sindhu K. Ernala, Shruti Kunde, Koustuv Dasgupta
    AAAI 2016
18. Cell Design and Routing of Jobs in a Multisite Make-to-Order Enterprise
    Manoj Gupta, J.C. Bose, Partha Dutta
    ICAPS 2016
19. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time
    Manoj Gupta
    FSTTCS 2014
20. Fully Dynamic (1+ε) Approximate Matchings
    Manoj Gupta and Richard Peng
    FOCS 2013
21. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
    Abhash Anand, Surender Baswana, Manoj Gupta, Sandeep Sen
    FSTTCS 2012
22. Fully dynamic maximal matching in O(log n) update time
    Surender Baswana, Manoj Gupta, Sandeep Sen
    FOCS 2011
23. The update complexity of selection and related problems
    Manoj Gupta, Yogish Sabharwal, Sandeep Sen
    FSTTCS 2011

Journal Publications

1. Better Analysis of GREEDY Binary Search Tree on Decomposable Sequences
   Navin Goyal, Manoj Gupta
   Theoretical Computer Science, 2019
2. Fully dynamic maximal matching in O(log n) update time
   Surender Baswana, Manoj Gupta, Sandeep Sen
   SIAM J. Comput., 2018
3. The update complexity of selection and related problems
   Manoj Gupta, Yogish Sabharwal, Sandeep Sen
   Theory Comput. Syst., 2016, 59, 112-132
4. The robust knapsack problem with queries
   Marc Goerigk, Manoj Gupta, Jonas Ide, Anita Schobel, Sandeep Sen
   Computers & OR, 2015, 55, 12-22

Book Chapters and Manuscripts

1. Matching in Dynamic Graphs
   Surender Baswana, Manoj Gupta, Sandeep Sen
   Encyclopedia of Algorithms, 2016, 1195-1199
2. On Dynamic Optimality for Binary Search Trees
   Navin Goyal, Manoj Gupta
3. An O(log n) Fully Dynamic Algorithm for Maximum matching in a tree
   Manoj Gupta, Ankit Sharma