DSpace Community: KAIST Dept. of Mathematical Sciences
http://hdl.handle.net/10203/527
KAIST Dept. of Mathematical SciencesFri, 19 Jan 2018 12:07:08 GMT2018-01-19T12:07:08ZLEVY-KHINTCHINE RANDOM MATRICES AND THE POISSON WEIGHTED INFINITE SKELETON TREE
http://hdl.handle.net/10203/227175
Title: LEVY-KHINTCHINE RANDOM MATRICES AND THE POISSON WEIGHTED INFINITE SKELETON TREE
Authors: Jung, Paul Heajoon
Abstract: We study a class of Hermitian random matrices which includes Wigner matrices, heavy-tailed random matrices, and sparse random matrices such as adjacency matrices of Erdos-Renyi random graphs with p(n) similar to 1/n. Our n x n random matrices have real entries which are i.i.d. up to symmetry. The distribution of entries depends on n, and we require row sums to converge in distribution. It is then well- known that the limit distribution must be infinitely divisible. We show that a limiting empirical spectral distribution (LSD) exists and, via local weak convergence of associated graphs, that the LSD corresponds to the spectral measure associated to the root of a graph which is formed by connecting infinitely many Poisson weighted infinite trees using a backbone structure of special edges called "cords to infinity". One example covered by the results are matrices with i.i.d. entries having infinite second moments but normalized to be in the Gaussian domain of attraction. In this case, the limiting graph is N rooted at 1, so the LSD is the semicircle law.Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10203/2271752018-01-01T00:00:00ZBeyond the Michaelis-Menten equation: Accurate and efficient estimation of enzyme kinetic parameters
http://hdl.handle.net/10203/228574
Title: Beyond the Michaelis-Menten equation: Accurate and efficient estimation of enzyme kinetic parameters
Authors: Choi, Boseung; Rempala, Grzegorz A.; Kim, Jae Kyoung
Abstract: Examining enzyme kinetics is critical for understanding cellular systems and for using enzymes in industry. The Michaelis-Menten equation has been widely used for over a century to estimate the enzyme kinetic parameters from reaction progress curves of substrates, which is known as the progress curve assay. However, this canonical approach works in limited conditions, such as when there is a large excess of substrate over enzyme. Even when this condition is satisfied, the identifiability of parameters is not always guaranteed, and often not verifiable in practice. To overcome such limitations of the canonical approach for the progress curve assay, here we propose a Bayesian approach based on an equation derived with the total quasi-steady-state approximation. In contrast to the canonical approach, estimates obtained with this proposed approach exhibit little bias for any combination of enzyme and substrate concentrations. Importantly, unlike the canonical approach, an optimal experiment to identify parameters with certainty can be easily designed without any prior information. Indeed, with this proposed design, the kinetic parameters of diverse enzymes with disparate catalytic efficiencies, such as chymotrypsin, fumarase, and urease, can be accurately and precisely estimated from a minimal amount of timecourse data. A publicly accessible computational package performing such accurate and efficient Bayesian inference for enzyme kinetics is provided.Fri, 01 Dec 2017 00:00:00 GMThttp://hdl.handle.net/10203/2285742017-12-01T00:00:00ZRank-width: algorithmic and structural results
http://hdl.handle.net/10203/226702
Title: Rank-width: algorithmic and structural results
Authors: Oum, Sang-il
Abstract: Rank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by 'simple' cuts. This survey aims to summarize known algorithmic and structural results on rank-width of graphs.Wed, 01 Nov 2017 00:00:00 GMThttp://hdl.handle.net/10203/2267022017-11-01T00:00:00ZThe "Art of Trellis Decoding" Is Fixed-Parameter Tractable
http://hdl.handle.net/10203/227051
Title: The "Art of Trellis Decoding" Is Fixed-Parameter Tractable
Authors: Jeong, Jisu; Kim, Eun Jung; Oum, Sang-il
Abstract: Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a linear layout V-1, V-2, ... , V-n of the subspaces such that dim((V-1 + V-2 + ... + V-i) boolean AND (Vi+1 + ... + V-n)) <= k for all i; such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an F-represented matroid in matroid theory. We present a fixed parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite dimensional vector space over F. As corollaries, we obtain a fixed parameter tractable algorithm to produce a path-decomposition of width at most k for an input. F-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs. It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden F-representable minors for the class of matroids of path-width at most k. An algorithm by Hlineny (2006) can detect a minor in an input F-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.Wed, 01 Nov 2017 00:00:00 GMThttp://hdl.handle.net/10203/2270512017-11-01T00:00:00Z