# Alumni Dissertations

#### Filter Dissertations By:

### Computer-Aided Reasoning about Knowledge and Justifications

Author:Natalia NovakYear of Dissertation:2009Program:Computer ScienceAdvisor:Sergei ArtemovAbstract:The dissertation consists of two Chapters. In the first Chapter we compare two well-known type-based computer frameworks for computer aided logical reasoning and verification: MetaPRL and Coq. In particular, we implement in MetaPRL the Calculus of Inductive Constructions which is the theoretical base for Coq. This work has shown the common points of MetaPRL and Coq, and revealed their principal methodological differences. A possible application of this work is a possibility to perform re-validation in MetaPRL of the existing library of Coq proofs which could help to build more trust in the latter. Chapter 2 is the main contribution of the dissertation. It contains the description and testing results of an implementation of realization algorithm in epistemic modal logic that converts cut-free derivations in multi-agent epistemic modal logic into derivations in the corresponding Justification Logic where witnesses of knowledge (justification terms) are recovered for all instances of common knowledge. We also apply this algorithms to several well-known epistemic puzzles, such as Muddy Children, Wise Men, Wise Girls, etc.

### Cancer Progression: Model, Therapy & Extraction

Author:Loes Olde LoohuisYear of Dissertation:2013Program:Computer ScienceAdvisor:Rohit ParikhAbstract:In this thesis we develop Cancer Hybrid Automata (CHAs), a modeling framework based on hybrid automata, to model the progression of cancers through discrete phenotypes. Both transition timing between states as well as the effect of drugs and clinical tests are parameters in the framework, thus allowing for the formalization of temporal statements about the progression as well as timed therapies. Using a game theoretical formulation of the problem we show how existing controller synthesis algorithms can be generalized to CHA models, so that (timed) therapies can be automatically generated. In the second part of this thesis we connect this formal framework to cancer patient data, focusing on copy number variation (CNV) data. The underlying process generating CNV segments is generally assumed to be memory-less, giving rise to an exponential distribution of segment lengths. We provide evidence from TCGA data suggesting that this generative model is too simplistic, and that segment lengths follow a power-law distribution instead. We show how an existing statistical method for detecting genetic regions of relevance for cancer can be improved through more accurate (power-law) null models. Finally, we develop an algorithm to extract CHA-like progression models from cross-sectional patient data. Based on a performance comparison on synthetic data, we show that our algorithm, which is based on a notion of probabilistic causality, outperforms an existing extraction method.

### Service Oriented Wireless Sensor Network

Author:Carolyn OrtegaYear of Dissertation:2013Program:Computer ScienceAdvisor:Theodore BrownAbstract:Quality of service (QoS) applications and network lifetime management are key challenges in Wireless Sensor Networks (WSNs). Service-level guarantees that are achievable in Service Oriented Architecture (SOA) can ensure reliability, availability and overall usability in any application. How to create the necessary structure to implement SOA in a WSN to achieve the required levels of quality of service is still a research topic. The SOA paradigm provides the methodology to improve these qualities in WSNs. We present a strategy that uses sensors in a cluster and dynamic service selection to achieve higher levels in quality of service for WSNs, while preserving network lifetime. The realization of these strategies will be achieved through a SOA middleware layer in the WSN. The concept of SOA dynamic service selection is transformed so that it can be applied to WSNs. The transformation requires that we equate a service in SOA to functions that are performed in a WSN. In our architecture, a service or function will be achieved through a group of sensors called a sensor cluster. Quality metrics will be captured at the sensor cluster level each time it is executed within the WSN. We present sensor cluster selection algorithms that will determine the most effective and efficient sensor clusters to participate in a composite function plan. The sensor cluster selection algorithms guarantee a minimum level of quality by selecting services that meet a client's quality constraints while taking into account the network routing requirements to achieve the operation in the shortest amount of time utilizing the least amount of energy. Additionally, we present methods for implementing service selection using the multiple choice, multiple dimension knapsack (MMKP) algorithm within a composite function that has complex workflow. We make use of the WSN's MMKP selection algorithm using dynamic programming as a proof of concept to demonstrate that there is a significant improvement in the energy utilization, network lifetime and overall quality.

### Secure Critical Care Resource Optimization based on Heterogeneous Vital Signs

Author:Mohamed SaadYear of Dissertation:2010Program:Computer ScienceAdvisor:Bilal KhanAbstract:Preventable, in-hospital errors account for a substantial number of deaths and injuries in the United States. Various studies estimate that such deaths number between 100,000 and 200,000 each year. One of the key challenges in critical care is a legacy of existing largely wired medical networks, which due to the complexity of their constituent heterogeneous medical devices, limit the ability to optimize the allocation of medical resources such as caregivers. The absence of reliable solutions which address the interoperability of different systems inside critical care units, is principally due to market concerns, since competing vendors do not embrace data sharing standards. In this work, we present a solution that integrates heterogeneous wired legacy systems within a backward compatible wireless interconnect system, providing mobility to caregivers, and the ability to coordinate and optimize their assignment to patients. The design and architecture is able to scale as needed in terms of system load and size. We demonstrate, through simulation, that the system is able to, through the optimization of caregiver assignment, significantly reduce total patient risk within health-care institutions. A prototype implementation of the system, demonstrates that the system has great promise in real-world field deployments, and can be instrumented to be compliant with site security requirements and the HIPAA privacy act.

### Geometric Graph Theory and Wireless Sensor Networks

Author:Deniz SariozYear of Dissertation:2012Program:Computer ScienceAdvisor:Janos PachAbstract:In this work, we apply geometric and combinatorial methods to explore a variety of problems motivated by wireless sensor networks. Imagine sensors capable of communicating along straight lines except through obstacles like buildings or barriers, such that the communication network topology of the sensors is their visibility graph. Using a standard distributed algorithm, the sensors can build common knowledge of their network topology. We first study the following inverse visibility problem: What positions of sensors and obstacles define the computed visibility graph, with fewest obstacles? This is the problem of finding a minimum obstacle representation of a graph. This minimum number is the obstacle number of the graph. Using tools from extremal graph theory and discrete geometry, we obtain for every constant $h$ that the number of $n$-vertex graphs that admit representations with $h$ obstacles is $2^{o(n^2)}$. We improve this bound to show that graphs requiring $\Omega(n / \log^{2} n)$ obstacles exist. We also study restrictions to convex obstacles, and to obstacles that are line segments. For example, we show that every outerplanar graph admits a representation with five convex obstacles, and that allowing obstacles to intersect sometimes decreases their required number. Finally, we study the corresponding problem for sensors equipped with GPS. Positional information allows sensors to establish common knowledge of their communication network geometry, hence we wish to compute a minimum obstacle representation of a given straight-line graph drawing. We prove that this problem is NP-complete, and provide a $O(\log OPT)$-approximation algorithm by bounding the Vapnik-Chervonenkis dimension for the corresponding hypergraph family.

### Information Transmission in Communication Games: Signaling with an Audience

Author:Farishta SatariYear of Dissertation:2013Program:Computer ScienceAdvisor:Rohit ParikhAbstract:Communication is a goal-oriented activity where interlocutors use language as a means to achieve an end while taking into account the goals and plans of others. Game theory, being the scientific study of strategically interactive decision-making, provides the mathematical tools for modeling language use among rational decision makers. When we speak of language use, it is obvious that questions arise about what someone knows and what someone believes. Such a treatment of statements as moves in a language game has roots in the philosophy of language and in economics. In the first, the idea is prominent with the work of Strawson, later Wittgenstein, Austin, Grice, and Lewis. In the second, the work of Crawford, Sobel, Rabin, and Farrell. We supplement the traditional model of signaling games with the following innovations: We consider the effect of the relationship whether close or distant among players. We consider the role that ethical considerations may play in communication. And finally, in our most significant innovation, we introduce an audience whose presence affects the sender's signal and/or the receiver's response. In our model, we no longer assume that the entire structure of the game is common knowledge as some of the priorities of the players and relationships among some of them might not be known to the other players.

### Optimization Problems in Sensor Network Data Collection

Author:Simon ShamounYear of Dissertation:2011Program:Computer ScienceAdvisor:Amotz Bar-NoyAbstract:Data collection is one of the most important tasks of many sensor networks. The data collected by sensors is used to monitor and analyze various systems, such as volcanoes, forests, and bridges. Large scale wireless sensor networks can provide timely access to a wealth of data, but obtaining this data is challenged by various resource constraints. This thesis proposes and analyzes solutions to three optimization problems that arise from the conflict between data collection and resource constraints: (1) maximize coverage by a set of sensors when the coverage they provide varies with location; (2) select a subset of the sensors, within some budget constraint, that best predict the data streams produced by all the sensors in the network; and (3) minimize the cost needed to find the top ranking sensor readings according to some criteria. The analyses of these problems use three different views of a sensor network: a coverage-centric view, in which each sensor is valued for its coverage ability; a data-centric view, in which each sensor is valued for the data it provides; and an agent-centric view, in which each sensor is viewed as an independent agent with information of value to the application. By choosing an appropriate view of the network, it is possible to separate the analysis from implementation details and apply well-established techniques from other domains to the problem solution. In this case, methodologies from stochastic and computational geometry, graph theory, and search theory are applied to the respective problems. This thesis presents optimal solutions to the coverage and search problems, approximation bounds on the best possible solution to the selection problem, and quantitative comparisons to alternative solutions to each problem in synthetic environments.

### ON THE PROBLEM OF PACKING STEINER TREES OF A GRAPH

Author:MOHAMMAD TALAFHAYear of Dissertation:2010Program:Computer ScienceAdvisor:LOUIS PETINGIAbstract:On The Problem of Packing Steiner Trees of a Graph Let G = (V, E) be an undirected graph with vertex-set V, edge-set E, and a subset of distinguished terminal vertices K of V, where |K| ≥ 2 (the vertices in V - K are called the non-terminal vertices). The degree of a vertex v of G is the number of edges incident at v in G. A K-Steiner tree T of G is a tree containing the terminal vertex-set K, and any vertex of degree one in T must belong to K. The K-edge-connectivity, denoted as λ

_{K}(G), of a connected graph G with terminal vertex-set K, is the minimum number of edges whose removal from G disconnects at least two vertices of K. The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge-disjoint K-Steiner trees, t_{K}(G), contained in G. Specifically, in this thesis, we are interested in finding a lower bound on t_{K}(G) with respect to the K-edge-connectivity, λ_{K}(G). The Steiner Tree Packing problem has attracted considerable attention from many researchers in different areas because of its wide applicability. It has applications in routing problems arising in VLSI circuit design, where an effective way of sharing different signals among cells in a circuit can be achieved by the use of edge-disjoint Steiner trees. It also has a variety of computer network applications such as multicasting, video-conferencing, and network information flow where simultaneous communications can be facilitated by using edge-disjoint Steiner trees. In 2003, Kriesell conjectured that any graph G = (V, E) with terminal vertex-set with subset of terminal vertices K of V has at least λ_{K}(G) / 2 edge-disjoint K-Steiner trees. In this thesis we give a background on this problem and we present most of the major results obtained so far. Moreover, we show that Kriesell's conjecture can be answered affirmatively if the edges of G can be partitioned into K-Steiner trees. This result yields bounds for the problem of packing K-Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex-set K, ; t_{K}(G) ≥ λ_{K}(G) - |V - K| / 2 - 1. Moreover, we study a vulnerability index called the edge-toughness, which connects the connectivity of a network with the problem of packing Steiner trees of a graph.### SEMIPARAMETRIC TEMPORAL CLUSTERING

Author:Suzanne TamangYear of Dissertation:2013Program:Computer ScienceAdvisor:Simon ParsonsAbstract:Although temporal data provides critical context for many real-world reasoning tasks, incorporating the temporal dimension into an analysis can present methodological challenges. Traditional methods from statistics are limited in their ability to process noisy, large-scale secondary data sources. Data mining approaches are better suited for these types of problems, but have primarily focused on static data sets. However, few real-world data sets are static, or measure stationary phenomena; rather, they are dynamic. To facilitate the meaningful use of abundant, unlabeled temporal data, I develop a new temporal clustering method that can assist in the preprocessing, exploration, and discovery of new knowledge from secondary data sources that are subject to arbitrary sampling schemes, and contain observation sequences of different durations. My approach builds on the semiparametric time series clustering framework, which has demonstrated clear benefits over fully parametric, or fully non-parametric methods. The framework combines beneficial parametric assumptions, such as the Markov or hidden-state assumption, to model temporal systems, with a more agnostic, nonparametric approach for clustering the embedded models. Using digital health data as a case study, I broaden the range of scenarios for which semiparametric clustering can be successfully applied. Specifically, I develop a method to use a state-of-the-art continuous-time Bayesian network to more naturally represent temporal information, addressing limitations of discrete- time methods. Also, as an alternative to spectral methods I pair model-based abstraction with a nonparametric Bayesian clustering technique that allows k to be expressed as a function of the size and complexity of the patient population, avoiding the requirement to prespecify the number of clusters using a heuristic. To demonstrate the ability of this approach to produce meaningful results, clusters are evaluated using intrinsic and extrinsic validation. In addition, I compare cluster assignments with that of temporal clustering systems reported in the research literature, showing a 20% relative improvement over the best system's performance and recognizable differences among the patient clusters that are detected.

### A Symbolic Exploration of the Joint State Space and the Underlying Argumentation-based Reasoning Processes for Multiagent Planning

Author:Yuqing TangYear of Dissertation:2012Program:Computer ScienceAdvisor:Simon ParsonsAbstract:Coming up with coherent behaviors for a team of agents in a non-deterministic environment is a complex process. The problem is further complicated by information regarding the environment being defeasible --- new information will disqualify the old information --- while at the same time this information is distributed, uncertain and possibly inconsistent. In this dissertation, I propose an approach based on symbolic model checking techniques to implicitly explore the state space of a system of agents to form a coherent set of joint behaviors for the agents with uncertainty captured as non-deterministism in the state space. The exploration process is based on individual agents' defeasible factored information about the dynamic of the state space towards a set of possibly inconsistent goals. This process can be interpreted using an argumentation-based approach. The exploration of the state space and the argumentation-based reasoning processes are carried out by a sequence of logical operations in the logic of Quantified Boolean Formulae (QBFs) and its model representation --- Binary Decision Diagrams (BDDs). All the algorithms to carry out these processes can be computed with a polynomial number of QBF operations in terms of the number of inputs and the number of boolean variables in the domain. Although general symbolic solving QBFs and BDDs is PSPACE complete, the practices of QBF solvers and BDD implementations allow us to employ various techniques and application-specific heuristics to solve a number of applications. In summary, the approaches proposed in this dissertation provide a formal system and implementation techniques to integrate non-monotonic reasoning and non-deterministic planning into defeasible multiagent decentralized planning so that coherent behaviors can be formed for a system of agents in a very demanding setting where the information regarding the environment and goals regarding what to do are distributed, incomplete, possibly inconsistent and uncertain.