SHShang-En Huang

Shang-En Huang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Shang-En Huang has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Deterministic Expander Routing: Faster and More Versatile

    by Yi-Jun Chang, Shang-En Huang, Hsin-Hao Su

    We consider the expander routing problem formulated by Ghaffari, Kuhn, and Su (PODC 2017), where the goal is to route all the tokens to their destinations given that each vertex is the source and the destination of at most deg(υ) tokens. They developed randomized algorithms that solve this problem in poly [EQUATION] rounds in the CONGEST model, where ϕ is the conductance of the graph. In addition, as noted by Chang, Pettie, Saranurak, and Zhang (JACM 2021), it is possible to obtain a preprocessing/query tradeoff so that the routing queries can be answered faster at the cost of more preprocessing time. The efficiency and flexibility of the processing/query tradeoff of expander routing have led to many other distributed algorithms in the CONGEST model, such as subpolynomial-round minimum spanning tree algorithms in expander graphs and near-optimal algorithms for k-clique enumeration in general graphs. As the routing algorithm of Ghaffari, Kuhn, and Su and the subsequent improved algorithm by Ghaffari and Li (DISC 2018) are both randomized, all the resulting applications are also randomized. Recently, Chang and Saranurak (FOCS 2020) gave a deterministic algorithm that solves an expander routing instance in 2O(log2/3 n·log1/3 log n) rounds. The deterministic algorithm is less efficient and does not allow preprocessing/query tradeoffs, which precludes the de-randomization of algorithms that require this feature, such as the aforementioned k-clique enumeration algorithm in general graphs. The main contribution of our work is a new deterministic expander routing algorithm that not only matches the randomized bound of Ghaffari, Kuhn, and Su but also allows preprocessing/query tradeoffs. Our algorithm solves a single instance of routing query in [EQUATION] rounds. For instance, this allows us to compute an MST in an expander graph in the same round complexity deterministically, improving the previous state-of-the-art 2O(log2/3 n·log1/3 log n). Our algorithm achieves the following preprocessing and query tradeoffs: For 0 < ϵ < 1, we can answer every routing query in logO(1/ϵ) n rounds at the cost of a (nO(ϵ) + logO(1/ϵ) n)-round preprocessing procedure. Combining this with the approach of Censor-Hillel, Leitersdorf, and Vulakh (PODC 2022), we obtain a near-optimal Õ(n1--2/k)-round deterministic algorithm for k-clique enumeration in general graphs, improving the previous state-of-the-art n1--2/k+o(1). As a side result of independent interest, we demonstrate the equivalence between expander routing and sorting in the sense that they are reducible to each other up to a polylogarithmic factor in round complexities in the CONGEST model.


  • Open Access

    Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection

    by Shang-En Huang, Seth Pettie, Leqi Zhu

    Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively corrupt up to f < n/3 parties. Moreover, the problem is insoluble with f ≥ n/3 corruptions. However, Bracha’s [ 13 ] 1984 protocol (see also Ben-Or [ 8 ]) achieved f < n/3 resilience at the cost of exponential expected latency 2 Θ ( n ) , a bound that has never been improved in this model with f = ⌊ (n-1)/3 ⌋ corruptions. In this article, we prove that Byzantine Agreement in the asynchronous, full information model can be solved with probability 1 against an adaptive adversary that can corrupt f < n/3 parties, while incurring only polynomial latency with high probability . Our protocol follows an earlier polynomial latency protocol of King and Saia [ 33 , 34 ], which had suboptimal resilience, namely f ≈ n /10 9 [ 33 , 34 ]. Resilience f = (n-1)/3 is uniquely difficult, as this is the point at which the influence of the Byzantine and honest players are of roughly equal strength. The core technical problem we solve is to design a collective coin-flipping protocol that eventually lets us flip a coin with an unambiguous outcome. In the beginning, the influence of the Byzantine players is too powerful to overcome, and they can essentially fix the coin’s behavior at will. We guarantee that after just a polynomial number of executions of the coin-flipping protocol, either (a) the Byzantine players fail to fix the behavior of the coin (thereby ending the game) or (b) we can “blacklist” players such that the blacklisting rate for Byzantine players is at least as large as the blacklisting rate for good players. The blacklisting criterion is based on a simple statistical test of fraud detection .


  • Open Access

    Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence

    by Nairen Cao, Shang-En Huang, Hsin-Hao Su

    The paper presents parallel algorithms for multiplying implicit simple unit-Monge matrices (Krusche and Tiskin, PPAM 2009) of size n x n in the EREW PRAM model. We show implicit simple unit-Monge matrices multiplication of size n x n can be achieved by a deterministic EREW PRAM algorithm with O(n log n log log n) total work and O(log3 n) span. This implies that there is a deterministic EREW PRAM algorithm solving the longest increasing subsequence (LIS) problem in O(n log2 n log log n) work and O(log 4 n) span. Furthermore, with randomization and bitwise operations, implicitly multiplying two simple unit-Monge matrices can be improved to O(n log n) work and O(log3n) span, which leads to a randomized EREW PRAM algorithm obtaining LIS in O(nlog2n) work and O(log4n) span with high probability. In the regime where the LIS has length k = Ψ(log3n), our results improve the span from Õ(n2/3) (Krusche and Tiskin, SPAA 2010) and O(klog n) (Gu, Men, Shen, Sun, and Wan, SPAA 2023) to O(log4 n) while the total work remains near optimal Õ (n).


  • Open Access

    (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings

    by Shang-En Huang, Hsin-Hao Su

    The maximum weighted matching (mwm) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the recent progress of Fischer, Mitrovic, and Uitto [16] who gave a poly(1/ϵ, log n)-round algorithm for obtaining a (1 − ϵ)-approximate solution for unweighted maximum matching, it had been an open problem whether a (1 − ϵ)-approximate mwm can be obtained in poly(1/ϵ, log n) rounds in the CONGEST model. Algorithms with such running times were only known for special graph classes such as bipartite graphs [1] and minor-free graphs [8]. For general graphs, the previously known algorithms require exponential in (1/ϵ) rounds for obtaining a (1 − ϵ)-approximate solution [13] or achieve an approximation factor of at most 2/3 [1]. In this work, we settle this open problem by giving a deterministic poly(1/ϵ, log n)-round algorithm for computing a (1 − ϵ)-approximate mwm for general graphs in the CONGEST model. Our proposed solution extends the algorithm of Fischer, Mitrovic, and Uitto [16], blends in the sequential algorithm from Duan and Pettie [11] and the work of Faour, Fuchs, and Kuhn [13]. Interestingly, this solution also implies a CREW PRAM algorithm with poly(1/ϵ, log n) span using only O(m) processors, and a poly(1/ϵ)-passes algorithm in the semi-streaming model.


  • Open Access

    Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection

    by Shang-En Huang, Seth Pettie, Leqi Zhu

    Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively \emph{corrupt} up to $f<n/3$ parties. Moreover, the problem is insoluble with $f\geq n/3$ corruptions. However, Bracha's 1984 protocol achieved $f<n/3$ resilience at the cost of exponential expected latency $2^{\Theta(n)}$, a bound that has never been improved in this model with $f=\lfloor (n-1)/3 \rfloor$ corruptions. In this paper we prove that Byzantine Agreement in the asynchronous, full information model can be solved with probability 1 against an adaptive adversary that can corrupt $f<n/3$ parties, while incurring only polynomial latency with high probability. Our protocol follows earlier polynomial latency protocols of King and Saia and Huang, Pettie, and Zhu, which had suboptimal resilience, namely $f \approx n/10^9$ and $f<n/4$, respectively. Resilience $f=(n-1)/3$ is uniquely difficult as this is the point at which the influence of the Byzantine and honest players are of roughly equal strength. The core technical problem we solve is to design a collective coin-flipping protocol that eventually lets us flip a coin with an unambiguous outcome. In the beginning the influence of the Byzantine players is too powerful to overcome and they can essentially fix the coin's behavior at will. We guarantee that after just a polynomial number of executions of the coin-flipping protocol, either (a) the Byzantine players fail to fix the behavior of the coin (thereby ending the game) or (b) we can ``blacklist'' players such that the blacklisting rate for Byzantine players is at least as large as the blacklisting rate for good players. The blacklisting criterion is based on a simple statistical test of fraud detection.

  • Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts

    by Shang-En Huang, Seth Pettie

    We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce the diameter of di...