Hoang Ta
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Hoang Ta has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Hoa T. Vu
San Diego State University
1 shared publication - Keke Huang
National University of Singapore, Singapore, Singapore
1 shared publication - Pietro Liò
University of Cambridge
1 shared publication - Quoc-Tung Le
Toulouse School of Economics, Toulouse, France
1 shared publication - Ryan Hildebrant
University of California, Irvine, Irvine, CA, USA
1 shared publication - Van Khu Vu
Singapore University of Technology and Design, Tampines, Singapore
1 shared publication
Latest Publications
- 16 July 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (9) , 7003-7015
An Efficient Parameterized Algorithm for Computing Quantum Channel Fidelity via Symmetries Exploitation
Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon $ in$\mathrm {poly}(1/\epsilon, \text {input dimension})$ time, compared to the$\exp (1/\epsilon, \text {input dimension})$ running time required for direct computation.- 16 July 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (9) , 7003-7015
An Efficient Parameterized Algorithm for Computing Quantum Channel Fidelity via Symmetries Exploitation
Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon $ in$\mathrm {poly}(1/\epsilon, \text {input dimension})$ time, compared to the$\exp (1/\epsilon, \text {input dimension})$ running time required for direct computation.- Open Access
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 1057-1068
Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach
Graph Neural Networks (GNNs), known as spectral graph filters, find a wide range of applications in web networks. To bypass eigendecomposition, polynomial graph filters are proposed to approximate graph filters by leveraging various polynomial bases for filter training. However, no existing studies have explored the diverse polynomial graph filters from a unified perspective for optimization. In this paper, we first unify polynomial graph filters, as well as the optimal filters of identical degrees into the Krylov subspace of the same order, thus providing equivalent expressive power theoretically. Next, we investigate the asymptotic convergence property of polynomials from the unified Krylov subspace perspective, revealing their limited adaptability in graphs with varying heterophily degrees. Inspired by those facts, we design a novel adaptive Krylov subspace approach to optimize polynomial bases with provable controllability over the graph spectrum so as to adapt various heterophily graphs. Subsequently, we propose AdaptKry, an optimized polynomial graph filter utilizing bases from the adaptive Krylov subspaces. Meanwhile, in light of the diverse spectral properties of complex graphs, we extend AdaptKry by leveraging multiple adaptive Krylov bases without incurring extra training costs. As a consequence, extended AdaptKry is able to capture the intricate characteristics of graphs and provide insights into their inherent complexity. We conduct extensive experiments across a series of real-world datasets. The experimental results demonstrate the superior filtering capability of AdaptKry, as well as the optimized efficacy of the adaptive Krylov basis.
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 1057-1068
Open AccessOptimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach
Graph Neural Networks (GNNs), known as spectral graph filters, find a wide range of applications in web networks. To bypass eigendecomposition, polynomial graph filters are proposed to approximate graph filters by leveraging various polynomial bases for filter training. However, no existing studies have explored the diverse polynomial graph filters from a unified perspective for optimization. In this paper, we first unify polynomial graph filters, as well as the optimal filters of identical degrees into the Krylov subspace of the same order, thus providing equivalent expressive power theoretically. Next, we investigate the asymptotic convergence property of polynomials from the unified Krylov subspace perspective, revealing their limited adaptability in graphs with varying heterophily degrees. Inspired by those facts, we design a novel adaptive Krylov subspace approach to optimize polynomial bases with provable controllability over the graph spectrum so as to adapt various heterophily graphs. Subsequently, we propose AdaptKry, an optimized polynomial graph filter utilizing bases from the adaptive Krylov subspaces. Meanwhile, in light of the diverse spectral properties of complex graphs, we extend AdaptKry by leveraging multiple adaptive Krylov bases without incurring extra training costs. As a consequence, extended AdaptKry is able to capture the intricate characteristics of graphs and provide insights into their inherent complexity. We conduct extensive experiments across a series of real-world datasets. The experimental results demonstrate the superior filtering capability of AdaptKry, as well as the optimized efficacy of the adaptive Krylov basis.
- Open Access
- 18 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 155-167
Towards Better Bounds for Finding Quasi-Identifiers
We revisit the problem of finding small ε-separation keys introduced by Motwani and Xu (2008). In this problem, the input is a data set consisting of m-dimensional tuples {x1,x2,...,xn}. The goal is to find a small subset of coordinates that separates at least (1-ε)(n2) pairs of tuples. When n is large, they provided a fast algorithm that runs on Θ(m/ε) tuples sampled uniformly at random. We show that the sample size can be improved to Θ(m/√ε). Our algorithm also enjoys a faster running time. To obtain this result, we consider a decision problem that takes a subset of coordinates A ⊆ [m]. It rejects if A separates fewer than (1-ε)(n2) pairs of tuples, and accepts if A separates all (n2) pairs of tuples. The algorithm must be correct with probability at least 1-δ for all 2m choices of A. We show that for algorithms based on uniform sampling: - Θ (m/√ε) samples are sufficient and necessary so that δ ≤ e-m. - Ω(√log m/ε) samples are necessary so that δ is a constant. Closing the gap between the upper and lower bounds in this case is still an open question. The analysis is based on a constrained version of the balls-into-bins problem whose worst case can be determined using Karush Kuhn Tucker (KKT) conditions. We believe our analysis may be of independent interest. We also study a related problem that asks for the following sketching algorithm: with given parameters α,k and ε, the algorithm takes a subset of coordinates A of size at most k and returns an estimate of the number of unseparated pairs in A up to a (1±ε) factor if it is at least α (n2). We show that even for constant α and success probability, such a sketching algorithm must use Ømega(mk log ε-1) bits of space; on the other hand, uniform sampling yields a sketch of size Θ (mk/αε2) for this purpose.
- 18 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 155-167
Open AccessTowards Better Bounds for Finding Quasi-Identifiers
We revisit the problem of finding small ε-separation keys introduced by Motwani and Xu (2008). In this problem, the input is a data set consisting of m-dimensional tuples {x1,x2,...,xn}. The goal is to find a small subset of coordinates that separates at least (1-ε)(n2) pairs of tuples. When n is large, they provided a fast algorithm that runs on Θ(m/ε) tuples sampled uniformly at random. We show that the sample size can be improved to Θ(m/√ε). Our algorithm also enjoys a faster running time. To obtain this result, we consider a decision problem that takes a subset of coordinates A ⊆ [m]. It rejects if A separates fewer than (1-ε)(n2) pairs of tuples, and accepts if A separates all (n2) pairs of tuples. The algorithm must be correct with probability at least 1-δ for all 2m choices of A. We show that for algorithms based on uniform sampling: - Θ (m/√ε) samples are sufficient and necessary so that δ ≤ e-m. - Ω(√log m/ε) samples are necessary so that δ is a constant. Closing the gap between the upper and lower bounds in this case is still an open question. The analysis is based on a constrained version of the balls-into-bins problem whose worst case can be determined using Karush Kuhn Tucker (KKT) conditions. We believe our analysis may be of independent interest. We also study a related problem that asks for the following sketching algorithm: with given parameters α,k and ε, the algorithm takes a subset of coordinates A of size at most k and returns an estimate of the number of unseparated pairs in A up to a (1±ε) factor if it is at least α (n2). We show that even for constant α and success probability, such a sketching algorithm must use Ømega(mk log ε-1) bits of space; on the other hand, uniform sampling yields a sketch of size Θ (mk/αε2) for this purpose.