# Sayan Bhattacharya

According to our database

Collaborative distances:

^{1}, Sayan Bhattacharya authored at least 24 papers between 2010 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

New amortized cell-probe lower bounds for dynamic problems.

Theor. Comput. Sci., 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

2018

Dynamic algorithms via the primal-dual method.

Inf. Comput., 2018

Dynamic Algorithms for Graph Coloring.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

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

Welfare Maximization with Friends-of-Friends Network Externalities.

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

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.

Discrete Applied Mathematics, 2010

Budget constrained auctions with heterogeneous items.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Incentive Compatible Budget Elicitation in Multi-unit Auctions.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010