Sayan Bhattacharya

106 papers A* 36A 5B 1Journal 56Unranked 8
YearRankTypeTitle / Venue / Authors
2026 J jnl
Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier.
CoRR
Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang
2026 A* conf
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems.
SODA
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
2026 A* conf
Vizing's Theorem in Deterministic Almost-Linear Time.
SODA
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2025 A* conf
Almost Optimal Fully Dynamic k-Center Clustering with Recourse.
ICML
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Silvio Lattanzi, Nikos Parotsidis
2025 A* conf
Deterministic Dynamic Maximal Matching in Sublinear Update Time.
STOC
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2025 J jnl
Deterministic Dynamic Maximal Matching in Sublinear Update Time.
CoRR
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2025 A* conf
Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains.
SODA
Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2025 J jnl
Fully Dynamic Euclidean k-Means.
CoRR
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou
2025 J jnl
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time.
CoRR
Sayan Bhattacharya, Ruoxu Cen, Debmalya Panigrahi
2025 A* conf
Fully Dynamic k-Median with Near-Optimal Update Time and Recourse.
STOC
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad
2025 J jnl
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems.
CoRR
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
2025 J jnl
Vizing's Theorem in Deterministic Almost-Linear Time.
CoRR
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2025 A* conf
Vizing's Theorem in Near-Linear Time.
STOC
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2024 — conf
Arboricity-Dependent Algorithms for Edge Coloring.
SWAT
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
2024 A conf
Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring.
ESA
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
2024 A* conf
Dynamic Facility Location in High Dimensional Euclidean Spaces.
ICML
Sayan Bhattacharya, Gramoz Goranci, Shaofeng H.-C. Jiang, Yi Qian, Yubo Zhang
2024 J jnl
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.
J. ACM
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
2024 J jnl
Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains.
CoRR
Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2024 J jnl
Faster (Δ + 1)-Edge Coloring: Breaking the m √n Time Barrier.
CoRR
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
2024 A* conf
Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier.
FOCS
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
2024 J jnl
Fully Dynamic
CoRR
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis
2024 J jnl
Fully Dynamic
CoRR
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis
2024 J jnl
Fully Dynamic
CoRR
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad
2024 A* conf
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse.
FOCS
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis
2024 A* conf
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
STOC
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
2024 A* conf
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time.
SODA
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
2024 J jnl
Vizing's Theorem in Near-Linear Time.
CoRR
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
2023 J jnl
Arboricity-Dependent Algorithms for Edge Coloring.
CoRR
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
2023 A* conf
Chasing Positive Bodies.
FOCS
Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak
2023 J jnl
Chasing Positive Bodies.
CoRR
Sayan Bhattacharya, Niv Buchbinder, Roie Levin, Thatchaphol Saranurak
2023 J jnl
Density-Sensitive Algorithms for (Δ+1)-Edge Coloring.
CoRR
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
2023 J jnl
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.
SIAM J. Comput.
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
2023 J jnl
Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time.
CoRR
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2023 A* conf
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time.
FOCS
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2023 A* conf
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates.
SODA
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2023 A* conf
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.
SODA
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
2023 J jnl
Fully Dynamic k-Clustering in Õ(k) Update Time.
CoRR
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis
2023 A* conf
Fully Dynamic k-Clustering in Õ(k) Update Time.
NeurIPS
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis
2023 J jnl
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
CoRR
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
2023 J jnl
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time.
CoRR
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
2023 A* conf
Sublinear Algorithms for (1.5+ε)-Approximate Matching.
STOC
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2022 A* conf
A New Dynamic Algorithm for Densest Subhypergraphs.
WWW
Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, Prantar Ghosh
2022 J jnl
A New Dynamic Algorithm for Densest Subhypergraphs.
CoRR
Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, Prantar Ghosh
2022 J jnl
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates.
CoRR
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2022 J jnl
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.
CoRR
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
2022 A* conf
Efficient and Stable Fully Dynamic Facility Location.
NeurIPS
Sayan Bhattacharya, Silvio Lattanzi, Nikos Parotsidis
2022 J jnl
Efficient and Stable Fully Dynamic Facility Location.
CoRR
Sayan Bhattacharya, Silvio Lattanzi, Nikos Parotsidis
2022 J jnl
Fully Dynamic (Δ +1)-Coloring in
ACM Trans. Algorithms
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, Shay Solomon
2022 A conf
Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary.
ESA
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert
2022 J jnl
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary.
CoRR
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert
2022 J jnl
Sublinear Algorithms for (1.5+ε)-Approximate Matching.
CoRR
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2021 A* conf
Deterministic Rounding of Dynamic Fractional Matchings.
ICALP
Sayan Bhattacharya, Peter Kiss
2021 J jnl
Deterministic Rounding of Dynamic Fractional Matchings.
CoRR
Sayan Bhattacharya, Peter Kiss
2021 A* conf
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.
SODA
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
2021 A* conf
Online Edge Coloring Algorithms via the Nibble Method.
SODA
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
2020 J jnl
An Improved Algorithm for Dynamic Set Cover.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
2020 A* conf
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs.
SODA
Sayan Bhattacharya, Janardhan Kulkarni
2020 A* conf
Coarse-Grained Complexity for Dynamic Algorithms.
SODA
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
2020 J jnl
Coarse-Grained Complexity for Dynamic Algorithms.
CoRR
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
2020 J jnl
Deterministic Dynamic Matching in O(1) Update Time.
Algorithmica
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
2020 J jnl
Online Edge Coloring Algorithms via the Nibble Method.
CoRR
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
2020 J jnl
Prior-free multi-unit auctions with ordered bidders.
Theor. Comput. Sci.
Sayan Bhattacharya, Elias Koutsoupias, Janardhan Kulkarni, Stefano Leonardi, Tim Roughgarden, Xiaoming Xu
2019 A* conf
A New Deterministic Algorithm for Dynamic Set Cover.
FOCS
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2019 J jnl
A New Deterministic Algorithm for Dynamic Set Cover.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2019 A* conf
Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time.
SODA
Sayan Bhattacharya, Janardhan Kulkarni
2019 J jnl
Fully Dynamic (Δ+1)-Coloring in Constant Update Time.
CoRR
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, Shay Solomon
2019 J jnl
New Amortized Cell-Probe Lower Bounds for Dynamic Problems.
CoRR
Sayan Bhattacharya, Monika Henzinger, Stefan Neumann
2019 J jnl
New amortized cell-probe lower bounds for dynamic problems.
Theor. Comput. Sci.
Sayan Bhattacharya, Monika Henzinger, Stefan Neumann
2018 J jnl
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs.
CoRR
Sayan Bhattacharya, Janardhan Kulkarni
2018 J jnl
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
SIAM J. Comput.
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
2018 J jnl
Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε
CoRR
Sayan Bhattacharya, Janardhan Kulkarni
2018 A* conf
Dynamic Algorithms for Graph Coloring.
SODA
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai
2018 J jnl
Dynamic algorithms via the primal-dual method.
Inf. Comput.
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
2017 B conf
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.
IPCO
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
2017 J jnl
Dynamic Algorithms for Graph Coloring.
CoRR
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai
2017 A* conf
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in
SODA
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2017 J jnl
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2017 A conf
Improved Algorithm for Dynamic b-Matching.
ESA
Sayan Bhattacharya, Manoj Gupta, Divyarthi Mohan
2017 J jnl
Welfare Maximization with Friends-of-Friends Network Externalities.
Theory Comput. Syst.
Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, Martin Starnberger
2016 J jnl
Design of Dynamic Algorithms via Primal-Dual Method.
CoRR
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
2016 J jnl
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time.
CoRR
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
2016 J jnl
New Deterministic Approximation Algorithms for Fully Dynamic Matching.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2016 A* conf
New deterministic approximation algorithms for fully dynamic matching.
STOC
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2015 — conf
Design of Dynamic Algorithms via Primal-Dual Method.
ICALP (1)
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
2015 A* conf
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
SODA
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
2015 — conf
Maintaining Near-Popular Matchings.
ICALP (2)
Sayan Bhattacharya, Martin Hoefer, Chien-Chung Huang, Telikepalli Kavitha, Lisa Wagner
2015 A* conf
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
STOC
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
2015 J jnl
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
2015 A conf
Welfare Maximization with Friends-of-Friends Network Externalities.
STACS
Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, Martin Starnberger
2014 — conf
Coordination Mechanisms for Selfish Routing over Time on a Tree.
ICALP (1)
Sayan Bhattacharya, Janardhan Kulkarni, Vahab S. Mirrokni
2014 A conf
Coordination mechanisms from (almost) all scheduling policies.
ITCS
Sayan Bhattacharya, Sungjin Im, Janardhan Kulkarni, Kamesh Munagala
2014 J jnl
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
CoRR
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
2014 — conf
New Approximability Results for the Robust k-Median Problem.
SWAT
Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, Adrian Neumann
2013 A* conf
Near-optimal multi-unit auctions with ordered bidders.
EC
Sayan Bhattacharya, Elias Koutsoupias, Janardhan Kulkarni, Stefano Leonardi, Tim Roughgarden, Xiaoming Xu
2013 J jnl
New Approximability Results for the Robust k-Median Problem.
CoRR
Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, Adrian Neumann
2012 J jnl
Budget-Constrained Auctions with Heterogeneous Items.
Theory Comput.
Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala
2012 — conf
Computing a Profit-Maximizing Sequence of Offers to Agents in a Social Network.
WINE
Sayan Bhattacharya, Dmytro Korzhyk, Vincent Conitzer
2012 J jnl
Constant-Competitive Prior-Free Auction with Ordered Bidders
CoRR
Sayan Bhattacharya, Janardhan Kulkarni, Xiaoming Xu
2011 — conf
Approximation Algorithm for Security Games with Costly Resources.
WINE
Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala
2011 A* conf
Consideration set generation in commerce search.
WWW
Sayan Bhattacharya, Sreenivas Gollapudi, Kamesh Munagala
2011 — conf
On Allocations with Negative Externalities.
WINE
Sayan Bhattacharya, Janardhan Kulkarni, Kamesh Munagala, Xiaoming Xu
2010 J jnl
A cops and robber game in multidimensional grids.
Discret. Appl. Math.
Sayan Bhattacharya, Goutam Paul, Swagato Sanyal
2010 A* conf
Budget constrained auctions with heterogeneous items.
STOC
Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala
2010 A* conf
Incentive Compatible Budget Elicitation in Multi-unit Auctions.
SODA
Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, Lirong Xia
2009 J jnl
Incentive Compatible Budget Elicitation in Multi-unit Auctions
CoRR
Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, Lirong Xia
2009 J jnl
On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids
CoRR
Sayan Bhattacharya, Goutam Paul, Swagato Sanyal