# Sayan Bhattacharya

According to our database

Collaborative distances:

^{1}, Sayan Bhattacharya authored at least 34 papers between 2009 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

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/ε

^{2}) 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

^{3}n) Worst Case Update Time.
CoRR, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in

*O*(log^{3}*n*) 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