2025
Can We Measure the Impact of a Database?
Commun. ACM, May, 2025
Coreset Spectral Clustering.
Proceedings of the Thirteenth International Conference on Learning Representations, 2025
2024
Spectral Toolkit of Algorithms for Graphs: Technical Report (2).
CoRR, 2024
Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime.
CoRR, 2024
Dynamic Spectral Clustering with Provable Approximation Guarantee.
Proceedings of the Forty-first International Conference on Machine Learning, 2024
2023
Three Hardness Results for Graph Similarity Problems.
CoRR, 2023
Spectral Toolkit of Algorithms for Graphs: Technical Report (1).
CoRR, 2023
Fast Approximation of Similarity Graphs with Kernel Density Estimation.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023
Is the Algorithmic Kadison-Singer Problem Hard?
Proceedings of the 34th International Symposium on Algorithms and Computation, 2023
Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs.
Proceedings of the International Conference on Machine Learning, 2023
The Support of Open Versus Closed Random Walks.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023
2022
A Tighter Analysis of Spectral Clustering, and Beyond.
Proceedings of the International Conference on Machine Learning, 2022
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
2021
Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Finding Bipartite Components in Hypergraphs.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Local Algorithms for Finding Densely Connected Clusters.
Proceedings of the 38th International Conference on Machine Learning, 2021
2020
Higher-Order Spectral Clustering of Directed Graphs.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020
Augmenting the Algebraic Connectivity of Graphs.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020
Hermitian matrices for clustering directed graphs: insights and applications.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020
2019
Distributed Graph Clustering and Sparsification.
ACM Trans. Parallel Comput., 2019
Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019
2018
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time.
SIAM J. Comput., 2018
2017
Partitioning Well-Clustered Graphs: Spectral Clustering Works!
SIAM J. Comput., 2017
An SDP-based algorithm for linear-sized spectral sparsification.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Distributed Graph Clustering by Load Balancing.
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017
2016
Balls into bins via local search: Cover time and maximum load.
Random Struct. Algorithms, 2016
Communication-Optimal Distributed Clustering.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016
2015
Randomized Rumour Spreading: The Effect of the Network Topology.
Comb. Probab. Comput., 2015
Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
2014
Partitioning Well-Clustered Graphs with k-Means and Heat Kernel.
CoRR, 2014
Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014
2013
Deterministic polynomial-time algorithms for designing short DNA words.
Theor. Comput. Sci., 2013
Counting Hypergraphs in Data Streams
CoRR, 2013
Balls into Bins via Local Search.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013
2012
Multi-Attribute Profit-Maximizing Pricing (Extended Abstract)
CoRR, 2012
Low Randomness Rumor Spreading via Hashing.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012
Counting Arbitrary Subgraphs in Data Streams.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Greedy Construction of 2-Approximate Minimum Manhattan Networks.
Int. J. Comput. Geom. Appl., 2011
Minimum Manhattan Network is NP-Complete.
Discret. Comput. Geom., 2011
Approximate Counting of Cycles in Streams.
Proceedings of the Algorithms - ESA 2011, 2011
2009
Two improved range-efficient algorithms for F<sub>0</sub> estimation.
Theor. Comput. Sci., 2009
On Construction of Almost-Ramanujan Graphs.
Discret. Math. Algorithms Appl., 2009
2008
Greedy Construction of 2-Approximation Minimum Manhattan Network.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008
A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem.
Proceedings of the Algorithmic Aspects in Information and Management, 2008
2007
Two Improved Range-Efficient Algorithms for <i>F</i> <sub>0</sub> Estimation.
Proceedings of the Theory and Applications of Models of Computation, 2007