DSpace Community: KAIST Dept. of Mathematical Sciences
http://hdl.handle.net/10203/527
KAIST Dept. of Mathematical Sciences2017-12-11T05:48:24ZLEVY-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.2018-01-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.2017-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.2017-11-01T00:00:00ZA NEW ANALYTICAL MODEL FOR OPTIMIZED COGNITIVE RADIO NETWORKS BASED ON STOCHASTIC GEOMETRY
http://hdl.handle.net/10203/226609
Title: A NEW ANALYTICAL MODEL FOR OPTIMIZED COGNITIVE RADIO NETWORKS BASED ON STOCHASTIC GEOMETRY
Authors: Lee, Seung Hee; Hwang, Ganguk
Abstract: In this paper, we consider an underlay type cognitive radio network with multiple secondary users who contend to access multiple heterogeneous licensed channels. With the help of stochastic geometry we develop a new analytical model to analyze a random channel access protocol where each secondary user determines whether to access a licensed channel based on a given access probability. In our analysis we introduce the so-called interference-free region to derive the coverage probability for an arbitrary secondary user. With the help of the interference-free region we approximate the interferences at an arbitrary secondary user from primary users as well as from secondary users in a simple way. Based on our analytical model we obtain the optimal access probabilities that maximize the throughput. Numerical examples are provided to validate our analysis.2017-10-01T00:00:00Z