Sayan Bhattacharya

activity

20092026

most citedOn Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

16 citations · 64 across the 32 of their papers we have counts for

collaborators

Showing 2023Show all

4 papers · 1 filter

cs.DS2023

Density-Sensitive Algorithms for $(Δ + 1)$ -Edge Coloring

Sayan Bhattacharya, Martín Costa, Nadav Panski +1

Vizing's theorem asserts the existence of a $(Δ + 1)$ -edge coloring for any graph $G$ , where $Δ = Δ (G)$ denotes the maximum degree of $G$ . Several polynomial time $(Δ + 1)$ -edge colorin…

cs.DS2023

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs

Sayan Bhattacharya, Peter Kiss, Aaron Sidford +1

We study dynamic $(1 - ε)$ -approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contributi…

cs.DS2023

Chasing Positive Bodies

Sayan Bhattacharya, Niv Buchbinder, Roie Levin +1

We study the problem of chasing positive bodies in $ℓ_{1}$ : given a sequence of bodies $K_{t} = {x^{t} \in R_{+}^{n} ∣ C^{t} x^{t} \geq 1, P^{t} x^{t} \leq 1}$ revealed online…

cs.DS2023

Dynamic $(1 + ε)$ -Approximate Matching Size in Truly Sublinear Update Time

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak

We show a fully dynamic algorithm for maintaining $(1 + ε)$ -approximate \emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges using $m^{0.5 - Ω_{ε} (1)}$ update tim…

Density-Sensitive Algorithms for (Δ+1)-Edge Coloring

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs

Chasing Positive Bodies

Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time

Density-Sensitive Algorithms for $(Δ + 1)$ -Edge Coloring

Dynamic $(1 + ε)$ -Approximate Matching Size in Truly Sublinear Update Time