Sublinear algorithms for (Δ+ 1) vertex coloring S Assadi, Y Chen, S Khanna
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019
134 2019 Near-linear size hypergraph cut sparsifiers Y Chen, S Khanna, A Nagda
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 61-72, 2020
36 2020 Polynomial pass lower bounds for graph streaming algorithms S Assadi, Y Chen, S Khanna
Proceedings of the 51st Annual ACM SIGACT Symposium on theory of computing …, 2019
35 2019 Sublinear algorithms and lower bounds for metric tsp cost estimation Y Chen, S Kannan, S Khanna
arXiv preprint arXiv:2006.05490, 2020
17 2020 On weighted graph sparsification by linear sketching Y Chen, S Khanna, H Li
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS …, 2022
13 2022 A polynomial lower bound on the number of rounds for parallel submodular function minimization and matroid intersection D Chakrabarty, Y Chen, S Khanna
SIAM Journal on Computing, FOCS21-1-FOCS21-29, 2023
11 2023 Sublinear algorithms and lower bounds for estimating MST and TSP cost in general metrics Y Chen, S Khanna, Z Tan
arXiv preprint arXiv:2203.14798, 2022
8 2022 Network formation under random attack and probabilistic spread Y Chen, S Jabbari, M Kearns, S Khanna, J Morgenstern
arXiv preprint arXiv:1906.00241, 2019
8 2019 On (1+ ɛ)-Approximate Flow Sparsifiers Y Chen, Z Tan
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2024
6 * 2024 Sublinear time hypergraph sparsification via cut and edge sampling queries Y Chen, S Khanna, A Nagda
arXiv preprint arXiv:2106.10386, 2021
3 2021 Near-perfect recovery in the one-dimensional latent space model Y Chen, S Kannan, S Khanna
Proceedings of The Web Conference 2020, 1932-1942, 2020
3 2020 Lower Bounds on Y Chen, Z Tan
arXiv preprint arXiv:2401.09585, 2024
1 2024 Towards the characterization of terminal cut functions: a condition for laminar families Y Chen, Z Tan
arXiv preprint arXiv:2310.11367, 2023
1 2023 Query complexity of the metric steiner tree problem Y Chen, S Khanna, Z Tan
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023
1 2023 Space-efficient query evaluation over probabilistic event streams R Alur, Y Chen, K Jothimurugan, S Khanna
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer …, 2020
1 2020 The beachcombers’ problem: Walking and searching from an inner point of a line Y Chen, X Deng, Z Ji, C Liao
Language and Automata Theory and Applications: 10th International Conference …, 2016
1 2016 Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances Y Chen, Z Tan
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2025
2025 Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs Y Chen, Z Tan
arXiv preprint arXiv:2407.10852, 2024
2024 On the Streaming Complexity of Expander Decomposition Y Chen, M Kapralov, M Makarov, D Mazzali
arXiv preprint arXiv:2404.16701, 2024
2024 An Y Chen, Z Tan
arXiv preprint arXiv:2310.07862, 2023
2023 
Sanjeev KhannaHenry Salvatori Professor of Computer Science, University of PennsylvaniaZweryfikowany adres z cis.upenn.edu
