7 citations · 15 across the 11 of their papers we have counts for
4 papers · 1 filter
Testing Spreading Behavior in Networks with Arbitrary Topologies
Augusto Modanese, Yuichi Yoshida
Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologi…
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in- Time Barrier
Anton Bukov, Shay Solomon, Tianyi Zhang
The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U…
Streaming Edge Coloring with Subquadratic Palette Size
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an -node graph arrive in an arbitrary order…
Almost-Optimal Sublinear Additive Spanners
Zihan Tan, Tianyi Zhang
Given an undirected unweighted graph on vertices and edges, a subgraph is a spanner of with stretch function $f: \mathbb{R}_+ \rightarrow \m…