5 papers
Streaming Max-Cut in General Metrics
Shaofeng H. -C. Jiang, Pan Peng, Haoze Wang
Max-Cut is a fundamental combinatorial optimization problem that has been studied in various computational settings. We initiate the study of its streaming complexity in \emph{gene…
Near-Optimal Four-Cycle Counting in Graph Streams
Sebastian Lüderssen, Stefan Neumann, Pan Peng
We study four-cycle counting in arbitrary order graph streams. We present a 3-pass algorithm for -approximating the number of four-cycles using $\widetilde{O}(m/\s…
Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
Pan Peng, Yuyang Wang
We study \emph{local computation algorithms (LCAs)} for constructing spanning trees. In this setting, the goal is to locally determine, for each edge , whether it belong…
Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
Pan Peng, Christian Sohler, Yi Xu
Single-linkage clustering is a fundamental method for data analysis. Algorithmically, one can compute a single-linkage -clustering (a partition into clusters) by computing a…
Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
Weiming Feng, Zelin Li, Pan Peng
We study sublinear-time algorithms for solving linear systems , where is a diagonally dominant matrix, i.e., for all $i \in…