Browsing by Author "Tsai, SC"

Now showing 1 - 5 of 5

A note on unscrambling address lines
(2003-02-28)
Lu, CC
;
Tsai, SC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
A writer stores some data in memory accessible via address lines. If an adversary permutes the address lines after the writer leaves the message, then how can a reader find the permutation? This is the so-called unscrambling address lines problem of Broder et al. [SODA'99, 1999, pp. 870-871]. By a divide-and-conquer approach, we give a very simple algorithm to recover the permutation. Our method is much easier to understand than Broder et al.'s previous ad hoc solution. (C) 2002 Elsevier Science B.V. All rights reserved.
An isolated Candida albicans TL3 capable of degrading phenol at large concentration
(2005-12-01)
Tsai, SC
;
Tsai, LD
;
Li, YK
;
應用化學系
;
應用化學系分子科學碩博班
An isolated yeast strain was grown aerobically on phenol as a sole carbon source up to 24 mm; the rate of degradation of phenol at 30 degrees C was greater than other microorganisms at the comparable phenol concentrations. This microorganism was further identified and is designated Candida albicans TL3. The catabolic activity of C. albicans TL3 for degradation of phenol was evaluated with the K-s and V-max values of 1.7 +/- 0.1 mm and 0.66 +/- 0.02 mu mol/min/mg of protein, respectively. With application of enzymatic, chromatographic and mass-spectrometric analyses, we confirmed that catechol and cis,cis-muconic acid were produced during the biodegradation of phenol performed by C. albicans TL3, indicating the occurrence of an ortho-fission pathway. The maximum activity of phenol hydroxylase and catechol-1,2-dioxygenase were induced when this strain grew in phenol culture media at 22 mm and 10 mm, respectively. In addition to phenol, C. albicans TL3 was effective in degrading formaldehyde, which is another major pollutant in waste water from a factory producing phenolic resin. The promising result from the bio-treatment of such factory effluent makes Candida albicans TL3 be a potentially useful strain for industrial application.
Distance-preserving mappings from binary vectors to permutations
(2003-04-01)
Chang, JC
;
Chen, RJ
;
Klove, T
;
Tsai, SC
;
資訊工程學系
Mappings of the set of binary vectors of a fixed length to the set of permutations of the same length are useful for the construction of permutation codes. In this correspondence, several explicit constructions of such mappings preserving or increasing the Hamming distance are given. Some applications are given to illustrate the usefulness (if the construction. In particular, a new lower bound on the maximal size of permutation arrays (PAs) is given.
Extracting randomness from multiple independent sources
(2005-06-01)
Lee, CJ
;
Lu, CJ
;
Tsai, SC
;
Tzeng, WG
;
資訊科學與工程研究所
We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches them best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.
On the Jensen-Shannon divergence and variational distance
(2005-09-01)
Tsai, SC
;
Tzeng, WG
;
Wu, HL
;
資訊工程學系
;
Department of Computer Science
We study the distance measures between two probability distributions via two different distance metrics, a new metric induced from Jensen-Shannon divergence, and the well known L-1 metric. We show that several important results and constructions in computational complexity under the L-1 metric carry over to the new metric, such as Yao's next-bit predictor, the existence of extractors, the leftover hash lemma, and the construction of expander graph based extractor. Finally, we show that the useful parity lemma in studying pseudorandomness does not hold in the new metric.