Spectral graph theory
Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem, with H. Li, and L. Zanetti. 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, 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
Clustering
Communication-Optimal Distributed Clustering, with J. Chen, D. Woodruff, and Q. Zhang (NIPS'16).
Conference version | Full version |
Spotlight video
Distributed Graph Clustering and Sparsification. with L. Zanetti. arXiv version
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
Load balancing
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
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
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
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