Browsing by Author "Chen, Hong-Bin"

Now showing 1 - 12 of 12

A survey on nonadaptive group testing algorithms through the angle of decoding
(2008-01-01)
Chen, Hong-Bin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
Group testing, sometimes called pooling design, has been applied to a variety of problems such as blood testing, multiple access communication, coding theory, among others. Recently, screening experiments in molecular biology has become the most important application. In this paper, we review several models in this application by focusing on decoding, namely, giving a comparative study of how the problem is solved in each of these models.
An Almost Optimal Algorithm for Generalized Threshold Group Testing with Inhibitors
(2011-06-01)
Chen, Hong-Bin
;
De Bonis, Annalisa
;
應用數學系
;
Department of Applied Mathematics
Group testing is a search paradigm where one is given a population S of n elements and an unknown subset P subset of S of defective elements and the goal is to determine P by performing tests on subsets of S. In classical group testing a test on a subset Q subset of S receives a YES response if vertical bar Q boolean AND P vertical bar >= 1, and a NO response otherwise. In group testing with inhibitors (GTI), identifying the defective items is more difficult due to the presence of elements called inhibitors that interfere with the queries so that the answer to a query is YES if and only if the queried group contains at least one defective item and no inhibitor. In the present article, we consider a new generalization of the GTI model in which there are two unknown thresholds h and g and the response to a test is YES both in the case when the queried subset contains at least one defective item and less than h inhibitors, and in the case when the queried subset contains at least g defective items. Moreover, our search model assumes that no knowledge on the number vertical bar P vertical bar of defective items is given. We derive lower bounds on the minimum number of tests required to determine the defective items under this model and present an algorithm that uses an almost optimal number of tests.
An upper bound of the number of tests in pooling designs for the error-tolerant complex model
(2008-06-01)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
Recently pooling designs have been used in screening experiments in molecular biology. In some applications, the property to be screened is defined on subsets of items, instead of on individual items. Such a model is usually referred to as the complex model. In this paper we give an upper bound of the number of tests required in a pooling design for the complex model (with given design parameters) where experimental errors are allowed.
Are there more almost separable partitions than separable partitions?
(2014-04-01)
Chang, Fei-Huang
;
Chen, Hong-Bin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
A partition of a set of n points in d-dimensional space into p parts is called an (almost) separable partition if the convex hulls formed by the parts are (almost) pairwise disjoint. These two partition classes are the most encountered ones in clustering and other partition problems for high-dimensional points and their usefulness depends critically on the issue whether their numbers are small. The problem of bounding separable partitions has been well studied in the literature (Alon and Onn in Discrete Appl. Math. 91:39-51, 1999; Barnes et al. in Math. Program. 54:69-86, 1992; Harding in Proc. Edinb. Math. Soc. 15:285-289, 1967; Hwang et al. in SIAM J. Optim. 10:70-81, 1999; Hwang and Rothblum in J. Comb. Optim. 21:423-433, 2011a). In this paper, we prove that for da parts per thousand currency sign2 or pa parts per thousand currency sign2, the maximum number of almost separable partitions is equal to the maximum number of separable partitions.
Exploring the missing link among d-separable, d-separable and d-disjunct matrices
(2007-03-15)
Chen, Hong-Bin
;
Hwang, Frank K.
;
應用數學系
;
Department of Applied Mathematics
d-Disjunct matrices, (d) over bar -separable matrices and d-separable matrices are well studied in various problems including group testing, coding, extremal set theory and, recently, DNA sequencing. The implications from the first two matrices to the last one are well documented. This paper gives an implication of the other direction for the first time. (c) 2006 Elsevier B.X. All rights reserved.
FEEDBACK VERTEX SET ON PLANAR GRAPHS
(2012-12-01)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Shih, Chie-Huai
;
應用數學系
;
Department of Applied Mathematics
A feedback vertex set of a graph is a set of vertices whose removal results an acyclic graph. This paper shows that for every planar graph the minimum cardinality of a feedback vertex set is at most three times the maximum number of vertex disjoint cycles in the graph.
Identification and Classification Problems on Pooling Designs for Inhibitor Models
(2010-07-01)
Chang, Huilan
;
Chen, Hong-Bin
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
Pooling designs are common tools to efficiently distinguish positive clones from negative clones in clone library screening. In some applications, there is a third type of clones called "inhibitors'' whose effect is in a sense to obscure the positive clones in pools. Various inhibitor models have been proposed in the literature. We address the inhibitor problems of designing efficient nonadaptive procedures for both identification and classification problems, and improve previous results in three aspects: (1) The algorithm that is used to identify the positive clones works on a more general inhibitor model and has a polynomial-time decoding procedure that recovers the set of positives from the knowledge of the outcomes. (2) The algorithm that is used to classify all clones works in one-stage, i.e., all tests are arranged in advance without knowing the outcomes of other tests, along with a polynomial-time decoding procedure. (3) We extend our results to pooling designs on complexes where the property to be screened is defined on subsets of biological objects, instead of on individual ones.
Nonadaptive algorithms for threshold group testing
(2009-04-06)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
應用數學系
;
Department of Applied Mathematics
Threshold group testing first proposed by Damaschke is a generalization of classic group testing. Specifically, a group test is positive (negative) if it contains at least u (at most 1) positives, and if the number of positives is between I and u, the test outcome is arbitrary. Although sequential group testing algorithms have been proposed, it is unknown whether an efficient nonadaptive algorithm exists. In this paper, we give an affirmative answer to this problem by providing efficient nonadaptive algorithms for the threshold model. The key observation is that disjunct matrices, a standard tool for group testing designs, also work in this threshold model. This paper improves and extends previous results in three ways: 1. The algorithms we propose work in one stage, which saves time for testing. 2. The test complexity is lower than previous results, at least for the number of elements which need to be tested is sufficiently large. 3. A limited number of erroneous test outcomes are allowed. (C) 2008 Elsevier B.V. All rights reserved.
Quantifying the nonclassicality of pure dephasing
(2019-08-22)
Chen, Hong-Bin
;
Lo, Ping-Yuan
;
Gneiting, Clemens
;
Bae, Joonwoo
;
Chen, Yueh-Nan
One of the central problems in quantum theory is to characterize, detect, and quantify quantumness in terms of classical strategies. Dephasing processes, caused by non-dissipative information exchange between quantum systems and environments, provides a natural platform for this purpose, as they control the quantum-to-classical transition. Recently, it has been shown that dephasing dynamics itself can exhibit (non)classical traits, depending on the nature of the system-environment correlations and the related (im)possibility to simulate these dynamics with Hamiltonian ensembles-the classical strategy. Here we establish the framework of detecting and quantifying the nonclassicality for pure dephasing dynamics. The uniqueness of the canonical representation of Hamiltonian ensembles is shown, and a constructive method to determine the latter is presented. We illustrate our method for qubit, qutrit, and qubit-pair pure dephasing and describe how to implement our approach with quantum process tomography experiments. Our work is readily applicable to present-day quantum experiments.
Reconstruction of hidden graphs and threshold group testing
(2011-08-01)
Chang, Huilan
;
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Shi, Chie-Huai
;
應用數學系
Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form "Does a set of elements contain a positive one?". A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form "Whether a set of vertices induces an edge". Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2nlg n,(1+o(1))(nlg n),2n and 2n queries were proposed, respectively. In this paper we improve them to (1 + 0(1))(nlgn), (1+0(1)) (nlgn/2), n + 2lgn and n+lg n, respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements under a more general setting, in which there are two fixed thresholds l and u, with l
Simulating Open Quantum Systems with Hamiltonian Ensembles and the Nonclassicality of the Dynamics
(2018-01-19)
Chen, Hong-Bin
;
Gneiting, Clemens
;
Lo, Ping-Yuan
;
Chen, Yueh-Nan
;
Nori, Franco
The incoherent dynamical properties of open quantum systems are generically attributed to an ongoing correlation between the system and its environment. Here, we propose a novel way to assess the nature of these system-environment correlations by examining the system dynamics alone. Our approach is based on the possibility or impossibility to simulate open-system dynamics with Hamiltonian ensembles. As we show, such (im) possibility to simulate is closely linked to the system-environment correlations. We thus define the nonclassicality of open-system dynamics in terms of the nonexistence of a Hamiltonian-ensemble simulation. This classifies any nonunital open-system dynamics as nonclassical. We give examples for open-system dynamics that are unital and classical, as well as unital and nonclassical.
Transforming an error-tolerant separable matrix to an error-tolerant disjunct matrix
(2009-01-28)
Chen, Hong-Bin
;
Cheng, Yongxi
;
He, Qian
;
Zhong, Chongchong
;
應用數學系
Recently, Chen and Hwang [H.B. Chen, F.K. Hwang, Exploring the missing link among d-separable, (d) over bar -separable and d-disjunct matrices, Discrete Applied Mathematics 133 (2007) 662-664] provided a method for transforming a separable matrix to a disjunct matrix. In [D.Z. Du, F.K. Hwang, Pooling Designs and Nonadaptive Group Testing - Important Tools for DNA Sequencing, World Scientific, 2006], Du and Hwang attempted to extend this result to its error-tolerant version; unfortunately, they gave an incorrect extension. This note gives a solution to this problem. (C) 2008 Elsevier B.V. All rights reserved.