Sayan Bhattacharya

Research Interests

• Design and analysis of algorithms in general, and specifically, dynamic algorithms and data structures.
• Google Scholar profile and DBLP page.

Funding

• ERC Consolidator Grant (2025 - 2030).
  
• EPSRC New Investigator Award (2020 - 2023).
  

Program Committees

• WADS 2017, STOC 2018, ICALP 2019 (Track A), ESA 2019, STACS 2020, SWAT 2020, SODA 2021, HALG 2021, SOSA 2023, STOC 2023, SODA 2024, ESA 2024, SODA 2025, ICALP 2025 (Track A).
  
• I am also a member of the LMS Computer Science Committee (2024 - 2026).
  

Workshop Organizing

• Dagstuhl Seminar on "New Trends in Clustering" (March, 2026).
  Co-organizers: Silvio Lattanzi, Shaofeng Jiang and Melanie Schmidt.
  
• Workshop on Algorithms and Complexity@Warwick (September, 2024).
  Co-organizers: Artur Czumaj and Igor C. Oliveira.
  
• Weizmann-Warwick Workshop (February, 2023).
  Co-organizers: Artur Czumaj, Robert Krauthgamer and Merav Parter.
  
• STOC Workshop on "Dynamic Algorithms: Recent Advances and Applications" (June, 2022).
  Co-organizer: Thatchaphol Saranurak.
  
• DIMAP Workshop on "Advances in Modern Graph Algorithms" (April, 2019) .
  Co-organizers: Artur Czumaj, Matthias Englert and Ramanujan Sridharan.
  

Current and Past Positions

• February, 2024 - January, 2025
  Visiting Faculty Researcher at Google Research.
• Since May, 2020
  Associate Professor at Department of Computer Science, University of Warwick, UK.
  
• March, 2017 - April, 2020
  Assistant Professor at Department of Computer Science, University of Warwick, UK.
  
• October, 2014 - February, 2017
  Assistant Professor (Fellow E) at Institute of Mathematical Sciences, Chennai, India.
  
• July, 2014 - September, 2014
  Postdoc at Theory and Applications of Algorithms research group, Faculty of Computer Science, University of Vienna, Austria.
  
• January, 2013 - June, 2014
  Postdoc at Algorithms and Compleixty department, Max-Planck Institute for Informatics, Saarbrucken, Germany.
  

Education

• August, 2008 - December, 2012
  PhD in Computer Science, Duke University, Durham, USA.
  Advisor: Kamesh Munagala.
  
• June, 2004 - May, 2008
  B. E. in Computer Science and Engineering, Jadavpur University, Kolkata, India.
  

Recent Teaching (at Warwick)

• 2024/25: (1) Discrete Mathematics and Its Applications II. (2) Approximation and Randomised Algorithms.
• 2022/23: (1) Discrete Mathematics and Its Applications II. (2) Approximation and Randomised Algorithms.
• 2021/22: (1) Discrete Mathematics and Its Applications II. (2) Approximation and Randomised Algorithms.

Current and Past PhD Students and Postdocs

• Ermiya Farokhnejad: PhD Student (since July, 2024).
• Martin Costa: PhD Student (since October, 2022).
• Peter Kiss: PhD Student (June, 2020 - October, 2024).
  Now an FWF Postdoctoral Fellow at the University of Vienna.
• Jayesh Choudhari: Postdoc (March, 2020 - November, 2021).
  Now a Senior Machine Learning Scientist at Tripadvisor.

Publications

• Vizing's Theorem in Near-Linear Time.
  S. Assadi, S. Behnezhad, S. Bhattacharya, M. Costa, S. Solomon and T. Zhang.
  STOC 2025.
  
• Fully Dynamic k-Median with Near-Optimal Update Time and Recourse.
  S. Bhattacharya, M. Costa and E. Farokhnejad.
  STOC 2025.
  
• Deterministic Dynamic Maximal Matching in Sublinear Update Time.
  A. Bernstein, S. Bhattacharya, P. Kiss and T. Saranurak.
  STOC 2025.
  
• Even Faster $(\Delta+1)$-Edge Coloring via Shorter Multi-Step Vizing Chains.
  S. Bhattacharya, M. Costa, S. Solomon and T. Zhang.
  SODA 2025.
  
• Fully Dynamic k-Clustering with Fast Update Time and Small Recourse.
  S. Bhattacharya, M. Costa, N. Garg, S. Lattanzi and N. Parotsidis.
  FOCS 2024.
  
• Faster $(\Delta+1)$-Edge Coloring: Breaking the $m\sqrt{n}$ Time Barrier.
  S. Bhattacharya, D. Carmon, M. Costa, S. Solomon and T. Zhang.
  FOCS 2024.
  
• Density-Sensitive Algorithms for $(\Delta+1)$-Edge Coloring.
  S. Bhattacharya, M. Costa, N. Panski and S. Solomon.
  ESA 2024 (Track A).
• Dynamic Facility Location in High Dimensional Euclidean Spaces.
  S. Bhattacharya, G. Goranci, S. H. C. Jiang, Y. Qian and Y. Zhang.
  ICML 2024 (Accepted as a "Spotlight").
• Arboricity-Dependent Algorithms for Edge Coloring.
  S. Bhattacharya, M. Costa, N. Panski and S. Solomon.
  SWAT 2024.
• Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
  S. Bhattacharya, P. Kiss, A. Sidford and D. Wajc.
  STOC 2024.
• Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time.
  S. Bhattacharya, M. Costa, N. Panski and S. Solomon.
  SODA 2024.
• Fully Dynamic k-Clustering in \tilde{O}(k) Update Time.
  S. Bhattacharya, M. Costa, S. Lattanzi and N. Parotsidis.
  NeurIPS 2023.
• Chasing Postive Bodies.
  S. Bhattacharya, N. Buchbinder, R. Levin and T. Saranurak.
  FOCS 2023.
• Dynamic (1+\epsilon)-Approximate Matching Size in Truly Sublinear Update Time.
  S. Bhattacharya, P. Kiss and T. Saranurak.
  FOCS 2023.
• Sublinear Algorithms for (1.5+\epsilon)-Approximate Matching.
  S. Bhattacharya, P. Kiss and T. Saranurak.
  STOC 2023.
• Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.
  S. Bhattacharya, P. Kiss, T. Saranurak and D. Wajc.
  SODA 2023 (Best paper award).
  Journal version accepted at JACM.
• Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates.
  S. Bhattacharya, P. Kiss and T. Saranurak.
  SODA 2023.
• Efficient and Stable Fully Dynamic Facility Location.
  S. Bhattacharya, S. Lattanzi and N. Parotsidis.
  NeurIPS 2022 ("Oral" presentation).
• Simple Dynamic Spanners with Near-Optimal Recourse against an Adaptive Adversary.
  S. Bhattacharya, T. Saranurak and P. Sukprasert.
  ESA 2022 (Track A).
• A New Dynamic Algorithm for Densest Subhypergraphs.
  S. K. Bera, S. Bhattacharya, J. Choudhari and P. Ghosh.
  WWW 2022.
• Fully Dynamic (\Delta+1)-Coloring in O(1) Update Time.
  S. Bhattacharya, F. Grandoni, J. Kulkarni, Q. C. Liu and S. Solomon.
  ACM Transactions on Algorithms 2022 (Volume 18, Issue 2).
• Deterministic Rounding of Dynamic Fractional Matchings.
  S. Bhattacharya and P. Kiss.
  ICALP 2021, Track A (Best paper award).
• Online Edge Coloring Algorithms via the Nibble Method.
  S. Bhattacharya, F. Grandoni and D. Wajc.
  SODA 2021.
• Dynamic Set Cover: Improved Amortized and Worst-Case Update Times.
  S. Bhattacharya, M. Henzinger, D. Nanongkai and X. Wu.
  SODA 2021.
• Coarse-Grained Complexity for Dynamic Algorithms.
  S. Bhattacharya, D. Nanongkai and T. Saranurak.
  SODA 2020.
• An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs.
  S. Bhattacharya and J. Kulkarni.
  SODA 2020.
• A New Deterministic Algorithm for Dynamic Set Cover.
  S. Bhattacharya, M. Henzinger and D. Nanongkai.
  FOCS 2019.
• Deterministically Maintaining a (2+\epsilon)-Approximate Minimum Vertex Cover in O(1/\epsilon^2) Amortized Update Time.
  S. Bhattacharya and J. Kulkarni.
  SODA 2019.
• Dynamic Algorithms for Graph Coloring.
  S. Bhattacharya, D. Chakrabarty, M. Henzinger and D. Nanongkai.
  SODA 2018.
• Improved Algorithm for Dynamic b-Matching.
  S. Bhattacharya, M. Gupta and Divyarthi M.
  ESA 2017 (Track A).
• Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.
  S. Bhattacharya, D. Chakrabarty and M. Henzinger.
  IPCO 2017.
• Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log^3 n) Worst Case Update Time.
  S. Bhattacharya, M. Henzinger and D. Nanongkai.
  SODA 2017.
• New Deterministic Approximation Algorithms for Fully Dynamic Matching.
  S. Bhattacharya, M. Henzinger and D. Nanongkai.
  STOC 2016.
  
• Maintaining Near-Popular Matchings.
  S. Bhattacharya, M. Hoefer, C. C. Huang, T. Kavitha and L. Wagner.
  ICALP 2015 (Track C).
  
• Design of Dynamic Algorithms via Primal-Dual Method.
  S. Bhattacharya, M. Henzinger and G. F. Italiano.
  ICALP 2015 (Track A).
  
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
  S. Bhattacharya, M. Henzinger, D. Nanongkai and C. E. Tsourakakis.
  STOC 2015.
  
• Welfare Maximization with Friends-of-Friends Network Externalities.
  S. Bhattacharya, W. Dvorak, M. Henzinger and M. Starnberger.
  STACS 2015.
  
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
  S. Bhattacharya, M. Henzinger and G. F. Italiano.
  SODA 2015.
  
• New Approximability Results for the Robust k-Median Problem.
  S. Bhattacharya, P. Chalermsook, K. Mehlhorn and A. Neumann.
  SWAT 2014.
  
• Coordination Mechanisms for Selfish Routing over Time on a Tree.
  S. Bhattacharya, J. Kulkarni and V. Mirrokni.
  ICALP 2014 (Track A).
  
• Coordination Mechanisms from (almost) all Scheduling Policies.
  S. Bhattacharya, S. Im, J. Kulkarni and K. Munagala.
  ITCS 2014.
  
• Near-optimal Multi-unit Auctions with Ordered Bidders .
  S. Bhattacharya, E. Koutsoupias, J. Kulkarni, S. Leonardi, T. Roughgarden and X. Xu.
  EC 2013.
  
• Computing a Profit-Maximizing Sequence of Offers to Agents in a Social Network.
  S. Bhattacharya, D. Korzhyk and V. Conitzer.
  WINE 2012 (short paper).
  
• Approximation Algorithm for Security Games with Costly Resources.
  S. Bhattacharya, V. Conitzer and K. Munagala.
  WINE 2011.
  
• On Allocations with Negative Externalities.
  S. Bhattacharya, J. Kulkarni, K. Munagala and X. Xu.
  WINE 2011.
  
• Consideration Set Generation in Commerce Search.
  S. Bhattacharya, S. Gollapudi and K. Munagala.
  WWW 2011.
  
• Cops and Robber Game in Multidimensional Grids.
  S. Bhattacharya, G. Paul and S. Sanyal.
  Discrete Applied Mathematics 2010 (Volume 158, Issue 16).
  
• Budget Constrained Auctions with Heterogeneous Items.
  S. Bhattacharya, G. Goel, S. Gollapudi and K. Munagala.
  STOC 2010.
  
• Incentive Compatible Budget Elicitation in Multi-unit Auctions.
  S. Bhattacharya, V. Conitzer, K. Munagala and L. Xia.
  SODA 2010.