# Alumni Dissertations and Theses

#### Filter Dissertations and Theses By:

### PASSIVE INDOOR LEVELED RFID LOCALIZATION ALGORITHMS

Author:Matthew ChanYear of Dissertation:2013Program:Computer ScienceAdvisor:Xiaowen ZhangAbstract:One of the most sought-after innovations in RFID technology is the ability to accurately locate stationary objects and track moving entities in real time. The author proposes three multi-leveled detectable count RFID localization algorithms (nearest-neighbor, multilateration, Bayesian inference) to accomplish these tasks using UHF passive RFID tags--chosen due to low cost and efficient implementation--by affixing them onto the floor as known reference nodes. Simulations are conducted to examine the accuracy and performance of the algorithms to locate stationary and mobile objects. Furthermore, experiments are carried out to test the localization of stationary objects in a real world setting such as a laboratory environment. The outcomes from the simulations and experiments are analyzed. The results are remarkable and most importantly, when the proper parametric values are considered, such as reference tag density and detection range, the accuracy performance of the algorithms achieved are impressive which confirms that the proposed methods are highly preferable when accurate, efficient and cost-effective passive RFID localization systems are to be implemented. Future directions of the study include exploration of different ratios for the three power levels of the RFID reader, use of other reference tag spacing pattern besides square such as hexagon, examination of other multi-level approach beside tri-level such as quad-, penta- or dual-level, experimentation with different kinds of RFID reference tags besides the passive Alien type G, as well as field tests of methods for mobile entities in a realistic real-world settings such as a laboratory.

### Conflict-free coloring

Author:Panagiotis CheilarisYear of Dissertation:2009Program:Computer ScienceAdvisor:Stathis ZachosAbstract:Graph and hypergraph colorings constitute an important subject in combinatorics and algorithm theory. In this work, we study conflict-free coloring for hypergraphs. Conflict-free coloring is one possible generalization of traditional graph coloring. Conflict-free coloring hypergraphs induced by geometric shapes, like intervals on the line, or disks on the plane, has applications in frequency assignment in cellular networks. Colors model frequencies and since the frequency spectrum is limited and expensive, the goal of an algorithm is to minimize the number of assigned frequencies, that is, reuse frequencies as much as possible. We concentrate on an online variation of the problem, especially in the case where the hypergraph is induced by intervals. For deterministic algorithms, we introduce a hierarchy of models ranging from static to online and we compute lower and upper bounds on the numbers of colors used. In the randomized oblivious adversary model, we introduce a framework for conflict-free coloring a specific class of hypergraphs with a logarithmic number of colors. This specific class includes many hypergraphs arising in geometry and gives online randomized algorithm that use fewer colors and fewer random bits than other algorithms in the literature. Based on the same framework, we initiate the study of online deterministic algorithms that recolor few points. For the problem of conflict-free coloring points with respect to a given set of intervals, we describe an efficient algorithm that computes a coloring with at most twice the number of colors of an optimal coloring. We also show that there is a family of inputs that force our algorithm to use two times the number of colors of an optimal solution. Then, we study conflict-free coloring problems in graphs. We compare conflict-free coloring with respect to paths of graphs to a closely related problem, called vertex ranking, or ordered coloring. For conflict-free coloring with respect to neighborhoods of vertices of graphs, we prove that number of colors in the order of the square root of the number of vertices is sufficient and sometimes necessary. Finally, we initiate the study of Ramsey-type problems for conflict-free colorings and compute a van der Waerden-like number.

### Efficient controls for finitely convergent sequential algorithms and their applications

Author:Wei ChenYear of Dissertation:2010Program:Computer ScienceAdvisor:Gabor HermanAbstract:Finding a feasible point that satisfies a set of constraints or a point that optimizes a function subject to a set of constraints is a common task in scientific computing: examples are the linear/convex feasibility/optimization problems. Projection methods have been used widely in solving many such problems of large size much more efficiently than other alternatives. Finitely convergent sequential algorithms are projection methods that sequentially iterate on individual constraints, one at a time, but overall find a feasible point in a finite number of iterations. ART3 is an example using cyclic control in the sense that it repeatedly cycles through the given constraints. The skipping unnecessary checks on constraints that are likely to be satisfied, lead to the new algorithm ART3+, a variant of ART3 whose control is no longer cyclic, but which is still finitely convergent. Experiments in fitting pixel images by blob images show that ART3+ is statistically significantly faster than ART3. Furthermore, a general methodology is proposed for automatic transformation of any finitely convergent sequential algorithm in such a way that (1) finite convergence is retained and (2) the speed of finite convergence is improved. The first property is proved by mathematical theorems, the second is illustrated by applying the algorithms to practical problems. This transformation is applicable, for example, to the finitely convergent modified cyclic subgradient projection algorithm for solving convex feasibility problems. One application is to intensity modulated radiation therapy (IMRT), whose goal is to deliver sufficient doses to tumors to kill them, but without causing irreparable damage to critical organs. The superior performance of the ART3+ for IMRT is demonstrated. An optimization algorithm based on ART3+ is proposed to handle linear constraints with either linear objectives or certain convex objectives. It is on average more than two orders of magnitude faster than the state of art industry-standard commercial algorithms (MOSEK's interior point optimizer and primal/dual simplex optimizer) and has almost no memory overhead. This allows for fast creation of multi-criteria treatment plan databases that span the global planning options available to the treatment planner.

### COLLABORATIVE RANKING AND COLLABORATIVE CLUSTERING

Author:Zheng ChenYear of Dissertation:2013Program:Computer ScienceAdvisor:Heng JiAbstract:Ranking and clustering are two important problems in machine learning and have wide applications in Natural Language Processing (NLP). A ranking problem is typically formulated as ranking a collection of candidate "objects" with respect to a "query" while a clustering problem is formulated as organizing a set of instances into groups such that members in each group share some similarity while members across groups are dissimilar. In this thesis, we introduce collaborative schemes into ranking and clustering problems, and name them as "collaborative ranking" and "collaborative clustering" respectively. Contrast to the tradition non-collaborative schemes, collaborative ranking leverages strengths from multiple query collaborators and ranker collaborators while collaborative clustering leverages strengths from multiple instance collaborators and clusterer collaborators. We select several typical NLP problems as our case studies including entity linking, document clustering and name entity clustering.

### RANDOMIZED SEARCH OF GRAPHS IN LOG SPACE AND PROBABILISTIC COMPUTATION

Author:Wen-Ju ChengYear of Dissertation:2014Program:Computer ScienceAdvisor:James CoxAbstract:italic

### KNOWLEDGE DISCOVERY AND PREDICTION MODELING OF PROTEIN-DRUG BINDING KINETIC BY INTEGRATING MACHINE LEARNING, NORMAL MODE ANALYSIS AND MOLECULAR DYNAMICS SIMULATION

Author:See Hong ChiuYear of Dissertation:2015Program:Computer ScienceAdvisor:Lei XieAbstract:One of the unaddressed challenges in drug discovery is that drug potency measured by protein-ligand binding affinity, such as IC50 and Kd in vitro, is not correlated with drug activity in vivo. Computational modeling is playing an increasing role in designing efficient therapeutics. However, existing computational methods for the high-throughput study of protein-ligand interactions (PLI) mainly focus on the prediction of the binding affinity. This is the combined effect of association (kon) and dissociation (koff) rate constants. Few works have been produced to predict koff or its reciprocal, residence time, which is a key measuring function of drug efficacy in vivo. This study addresses the unmet need of the accurate and scalable prediction of kon and koff simultaneously. The fundamental strategy of our method is to develop a machine learning model using PLI kinetic features computed by normal mode analysis (NMA). To test our method, HIV-1 protease complex was used as a model system. There are three major findings of this study. First, kinetic properties are more important than thermal dynamic characteristics in determining protein-ligand binding kinetics. We propose that coherent conformational dynamics coupling between protein and ligand were proven to be more significant than pairwise residue binding energy in the prediction of kinetic rate constants. Second, NMA is an efficient method to capture conformational dynamics features for the large scale modeling of protein-ligand binding. Third, multi-target classification as well as multi-target regression, is a potentially valuable tool for modeling PLI kinetics. With the rapid increase of PLI kinetics data, the further improvement of proposed computational methodology may provide a powerful tool for large-scale modeling of PLI kinetics, thereby accelerating drug discovery process.

### The Bilinear Brain, Bilinear Methods For EEG Analysis And Brain Computer Interfaces.

Author:Christoforos ChristoforouYear of Dissertation:2009Program:Computer ScienceAdvisor:Robert HaralickAbstract:Analysis of electro-encephalographic (EEG) signals has been proven an extremely useful research tool for studying the neural correlates of behavior. Single-trial analysis of these signals is essential for the development of non-invasive Brain Computer Interfaces. Analysis of these signals is often expressed as a single-trial classi¯cation problem. The goal is to infer the underling cognitive state of an individual using purely EEG signals. The high dimensional space of EEG observations and the low signal-to-noise ratio (SNR) -often -20db or less - as well as the inter-subject variability and limited observations available for training, make the single-trial classi¯cation of EEG an extremely challenging computational task. To address these challenges we introduce concepts from Multi-linear Algebra and incorporate EEG domain knowledge. More precisely, we formulate the problem in a matrix space and introduce a bilinear combination of a matrix to reduce the space dimensions. Thus the title of this dissertation: "The Bilinear Brain". We also address the issue of inter-subject variability by de¯ning a model that is partially subject-invariant. We develop two classi¯cation algorithms based on the Bilinear model. We term the ¯rst algorithm Second Order Bilinear Discriminant Analysis (SOBDA). It combines ¯rst order and second order statistics of the observation space. The second algorithm we term Bilinear Feature Based Discriminant (BFBD) and addresses the issue of inter-subject variability. We evaluate our methods on both simulated and real human EEG data-sets and show that our method outperforms state-of-the-art methods on di®erent experimental paradigms.

### Hash Functions, Latin Squares and Secret Sharing Schemes

Author:Chi ChumYear of Dissertation:2010Program:Computer ScienceAdvisor:Xiaowen ZhangAbstract:A secret sharing scheme creates an effective method to safeguard a secret by dividing it among several participants. Since the original idea introduced by Shamir and Blakley in 1979, a variety of threshold secret sharing schemes and other types have been suggested by researchers. The first part of this thesis shows how to apply hash functions in secret sharing scheme designs. By using hash functions and the herding hashes technique, we first set up a (t + 1, n) threshold scheme which is perfect and ideal, and then extend it to schemes for any general access structure. The schemes can be further set up as verifiable if necessary. The secret can be quickly recovered due to the fast calculation of the hash function. In particular, secret sharing schemes based on Latin squares will be discussed. The practical hash functions used today, such as SHA-1 and SHA-2 families, are iterative hash functions. Although there are many suggestions to improve the security of an iterative hash function, the general idea of processing the message block by block still enables many attacks, which make use of the intermediate hash values, possible. The second part of this thesis proposes a new hash function construction scheme that applies the randomize-then-combine technique, which was used in the incremental hash functions, to the iterative hash construction to prevent those attacks.

### Algorithms for Superiorization and their Applications to Image Reconstruction

Author:Ran DavidiYear of Dissertation:2010Program:Computer ScienceAdvisor:Gabor HermanAbstract:Computational tractability with limited computing resources is a major barrier for the ever increasing problem sizes of constrained optimization models that seek a minimum of an objective function satisfying a set of constraints. On the other hand, there exist efficient and computationally much less demanding iterative methods for finding a feasible solution that only fulfills the constraints. These methods can handle problem sizes beyond which existing optimization algorithms cannot function. To bridge this gap we present a new concept called superiorization, envisioned methodologically as lying between optimization and feasibility seeking. It enables us to use efficient iterative methods to steer the iterates toward a point that is feasible and superior, but not necessarily optimal, with respect to the given objective/merit function. Using efficient iterative methods to do `superiorization' instead of `full constrained optimization' or only `feasibility' is a new tool for handling mathematical models that include constraints and a merit function. The target improvement of the superiorization methodology is to affect the computational treatment of the mathematical models so that we can reach solutions that are desirable from the point of view of the application at hand at a relatively small computational cost. The key to superiorization is our discovery that two principal prototypical algorithmic schemes, string-averaging projections and block-iterative projections, which include many projection methods, are bounded perturbation resilient. While stability of algorithms under perturbations is usually made to cope with all kinds of imperfections in the data, here we have taken a proactive approach designed to extract specific benefits from the kind of stability that we term perturbation-resilience. Superiorization uses perturbations proactively to reach feasible points that are superior, according to some criterion, to the ones to which we would get without employing perturbations. In this work, we set forth the fundamental principle of the superiorization methodology, give some mathematical formulations, theorems and results, and show potential benefits in the field of image reconstruction from projections.

### Epistemic paradox and explicit modal logic

Author:Walter DeanYear of Dissertation:2010Program:Computer ScienceAdvisor:Sergei ArtemovAbstract:The dissertation presents a unified treatment of what I refer to as the epistemic paradoxes (i.e. the Knower Paradox of Montague and Kaplan and Fitch's Paradox of Knowability) in the context of a quantified extension of Artemov's Logic of Proofs [LP]. The system adopted is a modified form of Fitting's Quantified Logic of Proofs [QLP] and contains not only so-called explicit modalities (i.e. statements of the form t:F with intended interpretation of "t denotes a proof of F") but also first-order quantifiers intended to range over proofs or informal justifications. This allows for a formalization of a justification-based notion of knowledge via statements of the form (exists x) x:F. The first chapter seeks to motivate the use of explicit modalities for reasoning about knowledge and informal provability relative to the tradition of epsitemic logic. The second chapter contains a consolidated treatment of the syntax and arithmetic and semantics of LP and QLP. A relational semantics for QLP is developed and several new results are presented. The third chapter focuses on the reconstruction of the Knower Paradox in QLP. The central observation is that by analyzing the K(x) predicate employed by Montague and Kaplan in terms of proof quantification by replacing K("F") with (exists x) x:F, we realize that an additional logic principle is required for the derivation of the Knower. This principle -- which is similar to a form of Universal Generalization for proofs anticipated by G\"odel [1938a] -- is examined both proof theoretically and through the use of an arithmetic semantics for QLP. The fourth chapter focuses on the reconstruction of the Knowability Paradox in QLP. The central observation is the so-called Knowability Principle on which the paradox is based -- i.e. the claim that if F is true, then it is possible to know F -- is most appropriately formulated via the use of proof quantifiers as (exists x) x:F as opposed to the use of propositional possibility and knowledge operators.