Sayan Bhattacharya

Orcid: 0000-0003-1612-0296

According to our database1, Sayan Bhattacharya authored at least 59 papers between 2009 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.
J. ACM, October, 2024

Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains.
CoRR, 2024

Fully Dynamic <i>k</i>-Center Clustering Made Simple.
CoRR, 2024

Vizing's Theorem in Near-Linear Time.
CoRR, 2024

Fully Dynamic <i>k</i>-Clustering with Fast Update Time and Small Recourse.
CoRR, 2024

Faster (Δ + 1)-Edge Coloring: Breaking the m √n Time Barrier.
CoRR, 2024

Arboricity-Dependent Algorithms for Edge Coloring.
Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic Facility Location in High Dimensional Euclidean Spaces.
Proceedings of the Forty-first International Conference on Machine Learning, 2024

Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring.
Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.
SIAM J. Comput., October, 2023

Sublinear Algorithms for (1.5+ε)-Approximate Matching.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fully Dynamic k-Clustering in Õ(k) Update Time.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Chasing Positive Bodies.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
Fully Dynamic (Δ +1)-Coloring in <i>O</i>(1) Update Time.
ACM Trans. Algorithms, 2022

A New Dynamic Algorithm for Densest Subhypergraphs.
Proceedings of the WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25, 2022

Efficient and Stable Fully Dynamic Facility Location.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Edge Coloring Algorithms via the Nibble Method.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Deterministic Rounding of Dynamic Fractional Matchings.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020
Prior-free multi-unit auctions with ordered bidders.
Theor. Comput. Sci., 2020

An Improved Algorithm for Dynamic Set Cover.
CoRR, 2020

Deterministic Dynamic Matching in O(1) Update Time.
Algorithmica, 2020

Coarse-Grained Complexity for Dynamic Algorithms.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
New amortized cell-probe lower bounds for dynamic problems.
Theor. Comput. Sci., 2019

Fully Dynamic (Δ+1)-Coloring in Constant Update Time.
CoRR, 2019

Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A New Deterministic Algorithm for Dynamic Set Cover.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
SIAM J. Comput., 2018

Dynamic algorithms via the primal-dual method.
Inf. Comput., 2018

Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε<sup>2</sup>) Amortized Update Time.
CoRR, 2018

Dynamic Algorithms for Graph Coloring.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
Welfare Maximization with Friends-of-Friends Network Externalities.
Theory Comput. Syst., 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log<sup>3</sup>n) Worst Case Update Time.
CoRR, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in <i>O</i>(log<sup>3</sup> <i>n</i>) Worst Case Update Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Improved Algorithm for Dynamic b-Matching.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
New deterministic approximation algorithms for fully dynamic matching.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Design of Dynamic Algorithms via Primal-Dual Method.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Maintaining Near-Popular Matchings.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
New Approximability Results for the Robust k-Median Problem.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Coordination mechanisms from (almost) all scheduling policies.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Coordination Mechanisms for Selfish Routing over Time on a Tree.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Near-optimal multi-unit auctions with ordered bidders.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2012
Budget-Constrained Auctions with Heterogeneous Items.
Theory Comput., 2012

Constant-Competitive Prior-Free Auction with Ordered Bidders
CoRR, 2012

Computing a Profit-Maximizing Sequence of Offers to Agents in a Social Network.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

2011
Consideration set generation in commerce search.
Proceedings of the 20th International Conference on World Wide Web, 2011

On Allocations with Negative Externalities.
Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Approximation Algorithm for Security Games with Costly Resources.
Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

2010
A cops and robber game in multidimensional grids.
Discret. Appl. Math., 2010

Incentive Compatible Budget Elicitation in Multi-unit Auctions.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids
CoRR, 2009


  Loading...