Yu Chen

According to our database, Yu Chen authored at least 22 papers between 2016 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs.

Yu Chen, Zihan Tan

CoRR, 2024

On (1 + ɛ)-Approximate Flow Sparsifiers.

Yu Chen, Zihan Tan

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

An <i>Ω~(√log|T|)</i> Lower Bound for Steiner Point Removal.

Yu Chen, Zihan Tan

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Lower Bounds on 0-Extension with Steiner Nodes.

Yu Chen, Zihan Tan

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

On the Streaming Complexity of Expander Decomposition.

Yu Chen, Michael Kapralov, Mikhail Makarov, Davide Mazzali

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families.

Yu Chen, Zihan Tan

CoRR, 2023

An Ω̃(√(log |T|) Lower Bound for Steiner Point Removal.

Yu Chen, Zihan Tan

CoRR, 2023

On (1+ε)-Approximate Flow Sparsifiers.

Yu Chen, Zihan Tan

CoRR, 2023

Query Complexity of the Metric Steiner Tree Problem.

Yu Chen, Sanjeev Khanna, Zihan Tan

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics.

Yu Chen, Sanjeev Khanna, Zihan Tan

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

On Weighted Graph Sparsification by Linear Sketching.

Yu Chen, Sanjeev Khanna, Huan Li

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection.

Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna

CoRR, 2021

Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries.

Yu Chen, Sanjeev Khanna, Ansh Nagda

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization.

Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Near-Perfect Recovery in the One-Dimensional Latent Space Model.

Yu Chen, Sampath Kannan, Sanjeev Khanna

Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Space-efficient Query Evaluation over Probabilistic Event Streams.

Rajeev Alur, Yu Chen, Kishor Jothimurugan, Sanjeev Khanna

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation.

Yu Chen, Sampath Kannan, Sanjeev Khanna

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Near-linear Size Hypergraph Cut Sparsifiers.

Yu Chen, Sanjeev Khanna, Ansh Nagda

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Polynomial pass lower bounds for graph streaming algorithms.

Sepehr Assadi, Yu Chen, Sanjeev Khanna

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Sublinear Algorithms for (Δ + 1) Vertex Coloring.

Sepehr Assadi, Yu Chen, Sanjeev Khanna

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Network Formation under Random Attack and Probabilistic Spread.

Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019

2016

The Beachcombers' Problem: Walking and Searching from an Inner Point of a Line.

Yu Chen, Xiaotie Deng, Ziwei Ji, Chao Liao

Proceedings of the Language and Automata Theory and Applications, 2016