Sayan Bhattacharya

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 60

Top Topics

Approximation Algorithms

Coordination Mechanism

Top Venues

Publications

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