Shunhua Jiang

Shunhua Jiang

Auto-generated profile, based on publicly available information

Shunhua Jiang

Columbia University, New York, USA

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
11 April 2023 in Algorithmica
Verified
Journal Article
Closed access
PDF file
SJShunhua Jiang
Shunhua Jiang
BNBento Natura
Bento Natura
OWOmri Weinstein
Omri Weinstein

26 September 2023 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
YCYi-Jun Chang
Yi-Jun Chang
RDRan Duan
Ran Duan
SJShunhua Jiang
Shunhua Jiang
We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device v has a unique identifier ID ( v ) ∈{ 1, 2, ⋖ , N } . Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens. Much progress has been made in understanding the energy complexity of leader election in radio networks, but very little is known about the tradeoff between time and energy. Chang et al. [STOC 2017] showed that the optimal deterministic energy complexity of leader election is Θ (log log N ) if each device can simultaneously transmit and listen but still leaving the problem of determining the optimal time complexity under any given energy constraint. Time–energy tradeoff: For any k ≥ log log N , we show that a leader among at most n devices can be elected deterministically in O ( k ċ n 1+ε ) + O ( k ċ N 1/k ) time and O ( k ) energy if each device can simultaneously transmit and listen, where ε > 0 is any small constant. This improves upon the previous O ( N )-time O (log log N )-energy algorithm by Chang et al. [STOC 2017]. We provide lower bounds to show that the time–energy tradeoff of our algorithm is near-optimal. Dense instances: For the dense instances where the number of devices is n = Θ ( N ), we design a deterministic leader election algorithm using only O (1) energy. This improves upon the O (log* N )-energy algorithm by Jurdziński, Kutyłowski, and Zatopiański [PODC 2002] and the O (α ( N ))-energy algorithm by Chang et al. [STOC 2017]. More specifically, we show that the optimal deterministic energy complexity of leader election is \(\Theta (\max \lbrace 1, \log \tfrac{N}{n}\rbrace)\) if each device cannot simultaneously transmit and listen, and it is \(Θ (\max \lbrace 1, \log \log \tfrac{N}{n}\rbrace)\) if each device can simultaneously transmit and listen.

6 February 2023 in arXiv
Verified
Preprint
Open access
PDF file
BHBaihe Huang
Baihe Huang
SJShunhua Jiang
Shunhua Jiang
ZSZhao Song
Zhao Song
RTRunzhou Tao
Runzhou Tao
RZRuizhe Zhang
Ruizhe Zhang
This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from the existing robust SDP-based interior point method analysis due to [Huang, Jiang, Song, Tao and Zhang, FOCS 2022]. While, the previous work only provides an efficient implementation in the classical setting. This work provides a novel quantum implementation. We give a quantum second-order algorithm with high-accuracy in both the optimality and the feasibility of its output, and its running time depending on $\log(1/\epsilon)$ on well-conditioned instances. Due to the limitation of quantum itself or first-order method, all the existing quantum SDP solvers either have polynomial error dependence or low-accuracy in the feasibility.

6 April 2023 in arXiv
Verified
Preprint
Open access
PDF file
SJShunhua Jiang
Shunhua Jiang
BPBinghui Peng
Binghui Peng
OWOmri Weinstein
Omri Weinstein
We settle the complexity of dynamic least-squares regression (LSR), where rows and labels $(\mathbf{A}^{(t)}, \mathbf{b}^{(t)})$ can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an $\epsilon$-approximate solution to $\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)} \mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$. We prove sharp separations ($d^{2-o(1)}$ vs. $\sim d$) between the amortized update time of: (i) Fully vs. Partially dynamic $0.01$-LSR; (ii) High vs. low-accuracy LSR in the partially-dynamic (insertion-only) setting. Our lower bounds follow from a gap-amplification reduction -- reminiscent of iterative refinement -- rom the exact version of the Online Matrix Vector Conjecture (OMv) [HKNS15], to constant approximate OMv over the reals, where the $i$-th online product $\mathbf{H}\mathbf{v}^{(i)}$ only needs to be computed to $0.1$-relative error. All previous fine-grained reductions from OMv to its approximate versions only show hardness for inverse polynomial approximation $\epsilon = n^{-\omega(1)}$ (additive or multiplicative) . This result is of independent interest in fine-grained complexity and for the investigation of the OMv Conjecture, which is still widely open.

20 October 2025 in arXiv
Verified
Preprint
Open access
PDF file
SJShunhua Jiang
Shunhua Jiang
MKMichael Kapralov
Michael Kapralov
LLLawrence Li
Lawrence Li
ASAaron Sidford
Aaron Sidford
In this paper we consider generalized flow problems where there is an $m$-edge $n$-node directed graph $G = (V,E)$ and each edge $e \in E$ has a loss factor $γ_e >0$ governing whether the flow is increased or decreased as it crosses edge $e$. We provide a randomized $\tilde{O}( (m + n^{1.5}) \cdot \mathrm{polylog}(\frac{W}δ))$ time algorithm for solving the generalized maximum flow and generalized minimum cost flow problems in this setting where $δ$ is the target accuracy and $W$ is the maximum of all costs, capacities, and loss factors and their inverses. This improves upon the previous state-of-the-art $\tilde{O}(m \sqrt{n} \cdot \log^2(\frac{W}δ) )$ time algorithm, obtained by combining the algorithm of [Daitch-Spielman, 2008] with techniques from [Lee-Sidford, 2014]. To obtain this result we provide new dynamic data structures and spectral results regarding the matrices associated to generalized flows and apply them through the interior point method framework of [Brand-Lee-Liu-Saranurak-Sidford-Song-Wang, 2021].

17 February 2022 in arXiv
Verified
Preprint
Open access
PDF file
SJShunhua Jiang
Shunhua Jiang
BNBento Natura
Bento Natura
OWOmri Weinstein
Omri Weinstein
We present a faster interior-point method for optimizing sum-of-squares (SOS) polynomials, which are a central tool in polynomial optimization and capture convex programming in the Lasserre hierarchy. Let $p = \sum_i q^2_i$ be an $n$-variate SOS polynomial of degree $2d$. Denoting by $L := \binom{n+d}{d}$ and $U := \binom{n+2d}{2d}$ the dimensions of the vector spaces in which $q_i$'s and $p$ live respectively, our algorithm runs in time $\tilde{O}(LU^{1.87})$. This is polynomially faster than state-of-art SOS and semidefinite programming solvers, which achieve runtime $\tilde{O}(L^{0.5}\min\{U^{2.37}, L^{4.24}\})$. The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis, which efficiently extends to multivariate SOS optimization, and requires maintaining spectral approximations to low-rank perturbations of elementwise (Hadamard) products. This is the main challenge and departure from recent IPM breakthroughs using inverse-maintenance, where low-rank updates to the slack matrix readily imply the same for the Hessian matrix.