He Sun


Clustering


Urku Portfolio

Fast Approximation of Similarity Graphs with Kernel Density Estimation. with P. Macgregor (NeurIPS'23, Spotlight).
Conference version | arXiv version | Code

Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs. with B. Manghiuc and S. Laenen (ICML'23).
Conference version | arXiv version | Talk | Code

A Tighter Analysis of Spectral Clustering, and Beyond. with P. Macgregor (ICML'22).
Conference version | arXiv version | Talk | Code

Finding bipartite components in hypergraphs. with P. Macgregor (NeurIPS'21).
Conference version | arXiv version | Talk | Code

Hierarchical clustering: O(1)-approximation for well-clustered graphs. with B. Manghiuc (NeurIPS'21).
Conference version | arXiv version | Talk | Code

Local algorithms for finding densely connected clusters. with P. Macgregor (ICML'21 for a long talk).
Conference version | arXiv version | Talk | Code

Higher-order spectral clustering of directed graphs. with S. Laenen (NeurIPS'20).
Conference version | arXiv version | Talk

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

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

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

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

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


Algorithmic spectral graph theory


Urku Portfolio

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime. with B. Jourdan, and P. Macgregor.
arXiv version

Three Hardness Results for Graph Similarity Problems. with D. Vagnozzi. submitted
arXiv version

The Support of Open versus Closed Random Walks. with T. Sauerwald, and D. Vagnozzi (ICALP'23).
Conference version

Spectral Toolkit of Algorithms for Graphs: Technical Report (1). with P. Macgregor
arXiv version

Is the Algorithmic Kadison-Singer Problem Hard? with B. Jourdan, and P. Macgregor (ISAAC'23).
arXiv version

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

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

Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem. with H. Li, and L. Zanetti (ESA'19)
Conference version | 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


Database algorithms


Urku Portfolio

Measuring the Impact of a Database, with P. Buneman, D. Dosso, M. Lissandrini, and G. Silvello, 2022.
submitted


Distributed algorithms


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

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

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

Balls into Bins via Local Search. with P.Bogdan, T.Sauerwald, and A.Stauffer (SODA'13).
Conference version | arXiv 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).
Journal version | Conference version

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

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