Playing Games on Sets and Models

The most prominent objective of the thesis is the development of the generalized descriptive set theory, as we call it. There, we study the space of all functions from a fixed uncountable cardinal to itself, or to a finite set of size two. These correspond to generalized notions of the universal Baire space (functions from natural numbers to themselves with the product topology) and the Cantor space (functions from natural numbers to the {0,1}-set) respectively. We generalize the notion of Borel sets in three different ways and study the corresponding Borel structures with the aims of generalizing classical theorems of descriptive set theory or providing counter examples. In particular we are interested in equivalence relations on these spaces and their Borel reducibility to each other. The last chapter shows, using game-theoretic techniques, that the order of Borel equivalence relations under Borel reduciblity has very high complexity. The techniques in the above described set theoretical side of the thesis include forcing, general topological notions such as meager sets and combinatorial games of infinite length. By coding uncountable models to functions, we are able to apply the understanding of the generalized descriptive set theory to the model theory of uncountable models. The links between the theorems of model theory (including Shelah's classification theory) and the theorems in pure set theory are provided using game theoretic techniques from Ehrenfeucht-Fraïssé games in model theory to cub-games in set theory. The bottom line of the research declairs that the descriptive (set theoretic) complexity of an isomorphism relation of a first-order definable model class goes in synch with the stability theoretical complexity of the corresponding first-order theory. The first chapter of the thesis has slightly different focus and is purely concerned with a certain modification of the well known Ehrenfeucht-Fraïssé games. There we (me and my supervisor Tapani Hyttinen) answer some natural questions about that game mainly concerning determinacy and its relation to the standard EF-game

Distributed algorithms for edge dominating sets

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.

Minimal sets of generators for the relation ideals of certain monomial curves

Let O be a monomial curve in the affine algebraic e-space over a field K and P be the relation ideal of O. If O is defined by a sequence of e positive integers some e - 1 of which form an arithmetic sequence then we construct a minimal set of generators for P and write an explicit formula for mu(P).

Training-Symbol Embedded, High-Rate Complex Orthogonal Designs for Relay Networks

Distributed Space-Time Block Codes (DSTBCs) from Complex Orthogonal Designs (CODs) (both square and non-square CODs other than the Alamouti design) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using the amplify and forward protocol. For such a network, a new class of high rate, training-symbol embedded (TSE) SSD DSTBCs are proposed from TSE-CODs. The constructed codes include the training symbols within the structure of the code which is shown to be the key point to obtain high rate along with the SSD property. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations. Non-square TSE-CODs are shown to provide better rates (in symbols per channel use) compared to the known SSD DSTBCs for relay networks when the number of relays is less than 10. Importantly, the proposed DSTBCs do not contain zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on and off transitions within every codeword use. Hence, the proposed DSTBCs eliminate the antenna switching problem.

On the improvement of diversity-multiplexing gain tradeoff in a training based TDD-simo system

This paper investigates the diversity-multiplexing gain tradeoff (DMT) of a time-division duplex (TDD) single-input multiple-output (SIMO) system with perfect channel state information (CSI) at the receiver (CSIR) and partial CSI at the transmitter (CSIT). The partial CSIT is acquired through a training sequence from the receiver to the transmitter. The training sequence is chosen in an intelligent manner based on the CSIR, to reduce the training length by a factor of r, the number of receive antennas. We show that, for the proposed training scheme and a given channel coherence time, the diversity order increases linearly with r for nonzero multiplexing gain. This is a significant improvement over conventional orthogonal training schemes.

A Ten-microRNA Expression Signature Predicts Survival in Glioblastoma

Glioblastoma (GBM) is the most common and aggressive primary brain tumor with very poor patient median survival. To identify a microRNA (miRNA) expression signature that can predict GBM patient survival, we analyzed the miRNA expression data of GBM patients (n = 222) derived from The Cancer Genome Atlas (TCGA) dataset. We divided the patients randomly into training and testing sets with equal number in each group. We identified 10 significant miRNAs using Cox regression analysis on the training set and formulated a risk score based on the expression signature of these miRNAs that segregated the patients into high and low risk groups with significantly different survival times (hazard ratio HR] = 2.4; 95% CI = 1.4-3.8; p < 0.0001). Of these 10 miRNAs, 7 were found to be risky miRNAs and 3 were found to be protective. This signature was independently validated in the testing set (HR = 1.7; 95% CI = 1.1-2.8; p = 0.002). GBM patients with high risk scores had overall poor survival compared to the patients with low risk scores. Overall survival among the entire patient set was 35.0% at 2 years, 21.5% at 3 years, 18.5% at 4 years and 11.8% at 5 years in the low risk group, versus 11.0%, 5.5%, 0.0 and 0.0% respectively in the high risk group (HR = 2.0; 95% CI = 1.4-2.8; p < 0.0001). Cox multivariate analysis with patient age as a covariate on the entire patient set identified risk score based on the 10 miRNA expression signature to be an independent predictor of patient survival (HR = 1.120; 95% CI = 1.04-1.20; p = 0.003). Thus we have identified a miRNA expression signature that can predict GBM patient survival. These findings may have implications in the understanding of gliomagenesis, development of targeted therapy and selection of high risk cancer patients for adjuvant therapy.

On Training and Training Voids for Receive Antenna Subset Selection in Time-Varying Channels

Antenna selection (AS) provides most of the benefits of multiple-antenna systems at drastically reduced hardware costs. In receive AS, the receiver connects a dynamically selected subset of N available antennas to the L available RF chains. The "best" subset to be used for data reception is determined by means of channel estimates acquired using training sequences. Due to the nature of AS, the channel estimates at different antennas are obtained from different transmissions of the pilot sequence, and are, thus, outdated by different amounts in a time-varying channel. We show that a linear weighting of the estimates is optimum for the subset selection process, where the weights are related to the temporal correlation of the channel variations. When L is not an integer divisor of N, we highlight a new issue of "training voids", in which the last pilot transmission is not fully exploited by the receiver. We present a "void-filling" method for fully exploiting these voids, which essentially provides more accurate training for some antennas, and derive the optimal subset selection rule for any void-filling method. We also derive new closed-form equations for the performance of receive AS with optimal subset selection.

Training-Embedded, Single-Symbol ML-Decodable, Distributed STBCs for Relay Networks

Recently, a special class of complex designs called Training-Embedded Complex Orthogonal Designs (TE-CODs) has been introduced to construct single-symbol Maximum Likelihood decodable (SSD) distributed space-time block codes (DSTBCs) for two-hop wireless relay networks using the amplify and forward protocol. However, to implement DSTBCs from square TE-CODs, the overhead due to the transmission of training symbols becomes prohibitively large as the number of relays increase. In this paper, we propose TE-Coordinate Interleaved Orthogonal Designs (TE-CIODs) to construct SSD DSTBCs. Exploiting the block diagonal structure of TE-CIODs, we show that the overhead due to the transmission of training symbols to implement DSTBCs from TE-CIODs is smaller than that for TE-CODs. We also show that DSTBCs from TE-CIODs offer higher rate than those from TE-CODs for identical number of relays while maintaining the SSD and full-diversity properties.

Application of an evolutionary fuzzy system for the estimation of workforce deployment and cross-training in an assembly environment

Owing to the increased customer demands for make-to-order products and smaller product life-cycles, today assembly lines are designed to ensure a quick switch-over from one product model to another for companies' survival in market place. The complexity associated with the decisions pertaining to the type of training and number of workers and their exposition to the different tasks especially in the current era of customized production is a serious problem that the managers and the HRD gurus are facing in industry. This paper aims to determine the amount of cross-training and dynamic deployment policy caused by workforce flexibility for a make-to-order assembly. The aforementioned issues have been dealt with by adopting the concept of evolutionary fuzzy system because of the linguistic nature of the attributes associated with product variety and task complexity. A fuzzy system-based methodology is proposed to determine the amount of cross-training and dynamic deployment policy. The proposed methodology is tested on 10 sample products of varying complexities and the results obtained are in line with the conclusions drawn by previous researchers.

Training and Voids in Receive Antenna Subset Selection in Time-Varying Channels

Receive antenna selection (AS) provides many benefits of multiple-antenna systems at drastically reduced hardware costs. In it, the receiver connects a dynamically selected subset of N available antennas to the L available RF chains. Due to the nature of AS, the channel estimates at different antennas, which are required to determine the best subset for data reception, are obtained from different transmissions of the pilot sequence. Consequently, they are outdated by different amounts in a time-varying channel. We show that a linear weighting of the estimates is necessary and optimum for the subset selection process, where the weights are related to the temporal correlation of the channel variations. When L is not an integer divisor of N , we highlight a new issue of ``training voids'', in which the last pilot transmission is not fully exploited by the receiver. We then present new ``void-filling'' methods that exploit these voids and greatly improve the performance of AS. The optimal subset selection rules with void-filling, in which different antennas turn out to have different numbers of estimates, are also explicitly characterized. Closed-form equations for the symbol error probability with and without void-filling are also developed.

Discovery of Application Workloads from Network File Traces

An understanding of application I/O access patterns is useful in several situations. First, gaining insight into what applications are doing with their data at a semantic level helps in designing efficient storage systems. Second, it helps create benchmarks that mimic realistic application behavior closely. Third, it enables autonomic systems as the information obtained can be used to adapt the system in a closed loop.All these use cases require the ability to extract the application-level semantics of I/O operations. Methods such as modifying application code to associate I/O operations with semantic tags are intrusive. It is well known that network file system traces are an important source of information that can be obtained non-intrusively and analyzed either online or offline. These traces are a sequence of primitive file system operations and their parameters. Simple counting, statistical analysis or deterministic search techniques are inadequate for discovering application-level semantics in the general case, because of the inherent variation and noise in realistic traces.In this paper, we describe a trace analysis methodology based on Profile Hidden Markov Models. We show that the methodology has powerful discriminatory capabilities that enable it to recognize applications based on the patterns in the traces, and to mark out regions in a long trace that encapsulate sets of primitive operations that represent higher-level application actions. It is robust enough that it can work around discrepancies between training and target traces such as in length and interleaving with other operations. We demonstrate the feasibility of recognizing patterns based on a small sampling of the trace, enabling faster trace analysis. Preliminary experiments show that the method is capable of learning accurate profile models on live traces in an online setting. We present a detailed evaluation of this methodology in a UNIX environment using NFS traces of selected commonly used applications such as compilations as well as on industrial strength benchmarks such as TPC-C and Postmark, and discuss its capabilities and limitations in the context of the use cases mentioned above.

Training Young Minds for Nanoscience and Technology: Issues and Challenges

This article explores issues and challenges in the field of education in nanoscience and technology with special emphasis with respect to India, where an expanding programme of research in nano science and technology is in place. The article does not concentrate on actual curricula that are needed in nano science and technology education course. Rather it focuses on the desirability of nanoscience and technology education at different levels of education and future prospect of students venturing into this within the economic and cultural milieu of India. We argue that care is needed in developing the education programme in India. However, the risk is worth taking as the education on nanoscience and technology can bridge the man power gap not only in this area of technology but also related technologies of hardware and micro electronics for which the country is a promising destination at global level. This will also unlock the demographical advantage that India will enjoy in the next five decades.

Tree structure for efficient data mining using rough sets

In data mining, an important goal is to generate an abstraction of the data. Such an abstraction helps in reducing the space and search time requirements of the overall decision making process. Further, it is important that the abstraction is generated from the data with a small number of disk scans. We propose a novel data structure, pattern count tree (PC-tree), that can be built by scanning the database only once. PC-tree is a minimal size complete representation of the data and it can be used to represent dynamic databases with the help of knowledge that is either static or changing. We show that further compactness can be achieved by constructing the PC-tree on segmented patterns. We exploit the flexibility offered by rough sets to realize a rough PC-tree and use it for efficient and effective rough classification. To be consistent with the sizes of the branches of the PC-tree, we use upper and lower approximations of feature sets in a manner different from the conventional rough set theory. We conducted experiments using the proposed classification scheme on a large-scale hand-written digit data set. We use the experimental results to establish the efficacy of the proposed approach. (C) 2002 Elsevier Science B.V. All rights reserved.