He Sun


Urku Portfolio

Higher-order spectral clustering of directed graphs. with S. Laenen. NeurIPS'20. Full version | Spotlight video

Hermitian matrices for clustering directed graphs: insights and applications. with M. Cucuringu, H. Li, and L. Zanetti (AISTATS'20). arXiv version.

Distributed Graph Clustering and Sparsification. with L. Zanetti. ACM Transactions on Parallel Computing, 6(3): 17:1-17:23,2019. arXiv version| Journal version .

Communication-Optimal Distributed Clustering, with J. Chen, D. Woodruff, and Q. Zhang (NIPS'16).
Conference version | Full version | Spotlight video

Human Motion Parsing by Hierarchical Dynamic Clustering. with Y.Zhang, S.Tang, and H.NeumanN (BMVC'18).

Temporal Human Action Segmentation via Dynamic Clustering. with Y.Zhang, S.Tang, and H.Neumann. arXiv version| code

Spectral graph theory

Urku Portfolio

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary, with A. Bernstein, J. van den Brand, M. Gutenberg, D. Nanongkai, T. Saranurak, and A. Sidford. arXiv version

Augmenting the Algebraic Connectivity of Graphs, with B. Manghiuc, and P. Peng (ESA'20) arXiv version

Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem, with H. Li, and L. Zanetti (ESA'19) arXiv version

An SDP-Based Algorithm for Linear-Sized Spectral Sparsification with Y.Lee (STOC'17)
Conference version | arXiv version

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, with Y. Lee (SIAM Journal on Computing'18, FOCS'15). Conference version | arXiv version

Partitioning Well-Clustered Graphs: Spectral Clustering Works! with R. Peng, and L. Zanetti (SIAM Journal on Computing'17, COLT'15). Journal version | Conference version | arXiv version | Poster

Load balancing

Urku Portfolio

Balls into Bins via Local Search: Cover Time and Maximum Load. with K.Bringmann, T.Sauerwald, and A.Stauffer (RSA'16, STACS'14). Journal version | Conference version | arXiv version

Balls into Bins via Local Search. with P.Bogdan, T.Sauerwald, and A.Stauffer (SODA'13).
Conference version | arXiv version

Tight Bounds For Randomized Load Balancing on Arbitrary Network Topologies. with T. Sauerwald (FOCS'12). Conference version | arXiv version

Rumor spreading

Urku Portfolio

Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading. with Z. Guo (SODA'15)
Conference version | arXiv version

Randomized Rumor Spreading: the Effect of the Network Topology. with X.Giménez, K.Panagiotou, and T.Sauerwald (CPC'15). Journal version

Low Randomness Rumor Spreading via Hashing. with G. Giakkoupis, T. Sauerwald, and P. Woelfel (STACS'12). Conference version

Streaming algorithms

Urku Portfolio

Counting Hypergraphs in Data Streams. arXiv version

Counting Arbitrary Subgraphs in Data Streams. with D.Kane, K.Mehlhorn, and T.Sauerwald (ICALP'12). Conference version

Approximate Counting of Cycles in Streams. with M.Manjunath, K.Mehlhorn, and K.Panagiotou (ESA'11) Conference version

Two improved range-efficient algorithms for F0 estimation. with Chung Keung Poon (TCS'09) Journal version | Conference version

Computational geometry

Urku Portfolio

Minimum Manhattan Network is NP-Complete. with F.Chin, and Z.Guo (DCG'11, SoCG'09).
Conference version | Journal version

Greedy Construction of 2-Approximate Minimum Manhattan Networks. with Z.Guo, and H.Zhu (IJCGA'11, ISAAC'08). Conference version | Journal version

A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem, with Z.Guo, and H.Zhu (AAIM'08). Conference version