7 citations · 15 across the 11 of their papers we have counts for
15 papers
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…
Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, Tianle Xie +1
In this paper, we show that the time complexity of monotone min-plus product of two matrices is , where is the f…
Cost Sharing for Connectivity with Budget
Tianyi Zhang, Dengji Zhao, Junyu Zhang +1
We consider a cost sharing problem to connect all nodes in a weighted undirected graph, where the weight of each edge represents the cost to use the edge for the connectivity and t…
Gomory-Hu Trees in Quadratic Time
Tianyi Zhang
Gomory-Hu tree [Gomory and Hu, 1961] is a succinct representation of pairwise minimum cuts in an undirected graph. When the input graph has general edge weights, classic algorithms…
Fusion rules for pastures and tracts
Matthew Baker, Tianyi Zhang
Baker and Bowler defined a category of algebraic objects called tracts which generalize both partial fields and hyperfields. They also defined a notion of weak and strong matroids…
From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers
Krzysztof Choromanski, Han Lin, Haoxian Chen +7
In this paper we provide, to the best of our knowledge, the first comprehensive approach for incorporating various masking mechanisms into Transformers architectures in a scalable…
Faster Cut-Equivalent Trees in Simple Graphs
Tianyi Zhang
Let be an undirected connected simple graph on vertices. A cut-equivalent tree of is an edge-weighted tree on the same vertex set , such that for any pair o…
A Scaling Algorithm for Weighted -Factors in General Graphs
Ran Duan, Haoqing He, Tianyi Zhang
We study the maximum weight perfect -factor problem on any general simple graph with positive integral edge weights , and , . When we have a functio…
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Shiri Chechik, Tianyi Zhang
In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph while edges are inserted and deleted from the graph. The first non-tr…
Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
Ran Duan, Haoqing He, Tianyi Zhang
Given a graph , we wish to compute a spanning tree whose maximum vertex degree, i.e. tree degree, is as small as possible. Computing the exact optimal solution is known…
Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees
Ran Duan, Tianyi Zhang
Given a directed graph on vertices with a special vertex , the directed minimum degree spanning tree problem requires computing a incoming spanning tree rooted at wh…
Improved distance sensitivity oracles via tree partitioning
Ran Duan, Tianyi Zhang
We introduce an improved structure of distance sensitivity oracle (DSO). The task is to pre-process a non-negatively weighted graph so that a data structure can quickly answer repl…