Clustering
Can we measure the impact of a database?
with P. Buneman, D. Dosso, M. Lissandrini, and G. Silvello. To appear in the Communications of the ACM.
arXiv version
Dynamic spectral clustering with provable approximation guarantee.
with S. Laenen (ICML'24).
Conference version | arXiv version | Code
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
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.
arXiv version
The support of open versus closed random walks.
with T. Sauerwald, and D. Vagnozzi (ICALP'23).
Conference 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
STAG: Spectral Toolkit of Algorithms for Graphs
Spectral toolkit of algorithms for graphs: technical report (1).
with P. Macgregor
arXiv version
Spectral toolkit of algorithms for graphs: technical report (2).
with P. Macgregor
Link
Distributed algorithms
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
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).
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