Jingbang Chen

I am a first year PhD student in the Algorithms & Complexity Group of University of Waterloo starting in Winter 2023. I am fortunate to be advised by Richard Peng. Prior to this, I received my Master at Georgia Institute of Technology and B.Eng (Honors) at Zhejiang University under supervision of Can Wang.

I have a broad interest in theoretical computer science, with special interests in developing efficient algorithms to solve problems on graphs with certain structured, balancing between theoretical analysis and practical applications.

I am highly involved with Competitive Programming. Staring from season 2022 - 2023, I work as the coach of GT programming team. Prior to this, I competed representing Zhejiang University and Georgia Tech in 2017 - 2021, participating in ICPC World Finals 2018 (Beijing), 2022 (Egypt). I also worked as the problem setter, the judge for over 10 contests including ICPC Nanjing Regional 2020, 2021 and the coach of training camps including ByteDance Winter Trainning Camp. I am also the founder and committee member of Universal Cup, which is a non-profit organization dedicated to providing trainings for competitive programming teams. All related experience are listed in Competitive Programming.

education

Ph.D., Computer Science, University of Waterloo, Waterloo, 2023 - Current
M.S., Computer Science, Georgia Institute of Technology, Atlanta, 2020 - 2022
B.Eng. (Honors), Pursuit Science Class, Chu Kochen Honors College (Joint Program with College of Computer Science and Technology), Zhejiang University, Hangzhou, 2016 - 2020
Guangzhou No.2 High School, Guangzhou, 2010 - 2016

news

Aug 30, 2023	Our paper “Distance Queries over Dynamic Interval Graphs” is accepted by the 34th International Symposium on Algorithms and Computation (ISAAC 2023).
Apr 17, 2023	Our paper “Hardness of Graph-Structured Algebraic and Symbolic Problems” is accepted by The 18th Algorithms and Data Structures Symposium (WADS 2023).
Mar 9, 2023	Our paper “Exponential Convergence of Sinkhorn Under Regularization Scheduling” is accepted by SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23).

selected publications

Sandpile Prediction on Structured Undirected Graphs

Chang, Ruinian, Chen, Jingbang, and Shi, Qingyu

2023
Learning-Augmented B-Trees

Cao, Xinyuan, Chen, Jingbang, Chen, Li, Lambert, Chris, Peng, Richard, and Sleator, Daniel

2023
Exponential Convergence of Sinkhorn Under Regularization Scheduling

Chen, Jingbang, Chen, Li, Liu, Yang P., Peng, Richard, and Ramaswami, Arvind

2023

Abs

Abstract In 2013, Cuturi [9] introduced the SINKHORN algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a better convergence rate for a high accuracy solution, we work on understanding the SINKHORN algorithm under regularization scheduling, and thus modify it with a mechanism that adaptively doubles the regularization parameter η periodically. We prove that such modified version of SINKHORN has an exponential convergence rate as iteration complexity depending on log(l/ɛ) instead of ɛ-o(1) from previous analyses [1, 9] in the optimal transport problems with integral supply and demand. Furthermore, with cost and capacity scaling procedures, the general optimal transport problem can be solved with a logarithmic dependence on 1/ɛ as well.
Hardness of Graph-Structured Algebraic and Symbolic Problems

Chen, Jingbang, Gao, Yu, Huang, Yufan, Peng, Richard, and Wang, Runze

In Algorithms and Data Structures 2023

Abs

In this paper (A full version can be found at https://arxiv.org/abs/2109.12736v3.), we study the hardness of solving graph structured linear systems with coefficients over a finite field Z_p and over a polynomial ring F[x_1,...,x_t]. We reduce solving general linear systems in Z_p to solving unit-weight low-degree graph Laplacians over Z_p with a polylogarithmic overhead on the number of non-zeros. Under the by now common assumption of hardness of solving general linear systems in Z_p, this result shows that ideas for solving graph-structured linear systems over reals are unlikely to transfer to finite-field settings. We also reduce solving general linear systems over Z_p to solving linear systems whose coefficient matrices are walk matrices (matrices with all ones on the diagonal) and normalized Laplacians (Laplacians that are also walk matrices) over Z_p. Furthermore, motivated by applications that choose entries of such systems over finite fields randomly, we provide some generalizations of our reductions to symbolic settings.