Theory and Algorithms Commons^™

Going Meta On The Minimum Circuit Size Problem: How Hard Is It To Show How Hard Showing Hardness Is?, Zoë Bell

HMC Senior Theses

The Minimum Circuit Size Problem (MCSP) is a problem with a long history in computational complexity theory which has recently experienced a resurgence in attention. MCSP takes as input the description of a Boolean function f as a truth table as well as a size parameter s, and outputs whether there is a circuit that computes f of size ≤ s. It is of great interest whether MCSP is NP-complete, but there have been shown to be many technical obstacles to proving that it is. Most of these results come in the following form: If MCSP is NP-complete …

K-Nearest Neighbors Density-Based Clustering, Avory C. Bryant

Theses and Dissertations

Traditional density-based clustering approaches rely on a distance-based parameter to define data connectivity and density. However, an appropriate value of this parameter can be difficult to determine as it is highly dependent on the underlying distribution of the data. In particular, distribution parameters affect the scale of inter-group distances (e.g., variance); this dependence leads to a well-known inability to simultaneously detect clusters at varying levels of density. In this work, connectivity and density are defined according to the rank-order induced by the distance metric (i.e., invariant to the expected scale of the distances). Connectivity by k-nearest neighbors and density by …

A Literature Review Of Quantum Education In K-12 Level, Yuming He, Shenghua Zha, Wu He, Theo Bastiaens (Ed.)

Information Technology & Decision Sciences Faculty Publications

Quantum computing is an emerging technology paradigm of computing and has the potential to solve computational problems intractable using today’s classical computers or digital technology. Quantum computing is expected to be disruptive for many industries. The power of quantum computing technologies is based on the fundamentals of quantum mechanics, such as quantum superposition, quantum entanglement, or the no-cloning theorem. To build a highly trained and skilled quantum workforce that meets future industry needs, there is a need to introduce quantum concepts early on in K-12 schools since the learning of quantum is a lengthy process. As fundamental quantum concepts derive …

Infinite-Duration All-Pay Bidding Games, Guy Avni, Ismäel Jecker, Dorde Zikelic

Research Collection School Of Computing and Information Systems

In a two-player zero-sum graph game the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In bidding games, however, the players have budgets, and in each turn, we hold an "auction" (bidding) to determine which player moves the token: both players simultaneously submit bids and the higher bidder moves the token. The bidding mechanisms differ in their payment schemes. Bidding games were largely studied with variants of first-price bidding in which only the higher bidder pays his bid. …

Collateral Data Quality Challenges Of Iot Sensor-Generated Data, Richard Allen Herrin

Graduate Student Publications

Thousands of academic articles have been written about the various facets of the Internet of Things (IoT). Added to those are books of multiple flavors, conference proceedings, and a host of web-based content authored by a diverse cast of IoT community constituents. While there are many examples of successful IoT application solutions, participating technologies and how best to use them, are still relatively immature. These solutions are complex, geographically diverse, incorporate a broad spectrum of ever-evolving technologies that allow organizations to gather new data, create new value and do new things they haven’t been able to do effectively before.

Despite …

Xtreme-Noc: Extreme Gradient Boosting Based Latency Model For Network-On-Chip Architectures, Ilma Sheriff

All Graduate Theses, Dissertations, and Other Capstone Projects

Multiprocessor System-on-Chip (MPSoC) integrating heterogeneous processing elements (CPU, GPU, Accelerators, memory, I/O modules ,etc.) are the de-facto design choice to meet the ever-increasing performance/Watt requirements from modern computing machines. Although at consumer level the number of processing elements (PE) are limited to 8-16, for high end servers, the number of PEs can scale up to hundreds. A Network-on-Chip (NoC) is a microscale network that facilitates the packetized communication among the PEs in such complex computational systems. Due to the heterogeneous integration of the cores, execution of diverse (serial and parallel) applications on the PEs, application mapping strategies, and many other …

Novel Hedonic Games And Stability Notions, Jacob Schlueter

Theses and Dissertations--Computer Science

We present here work on matching problems, namely hedonic games, also known as coalition formation games. We introduce two classes of hedonic games, Super Altruistic Hedonic Games (SAHGs) and Anchored Team Formation Games (ATFGs), and investigate the computational complexity of finding optimal partitions of agents into coalitions, or finding - or determining the existence of - stable coalition structures. We introduce a new stability notion for hedonic games and examine its relation to core and Nash stability for several classes of hedonic games.

Representing And Learning Preferences Over Combinatorial Domains, Michael Huelsman

Theses and Dissertations--Computer Science

Agents make decisions based on their preferences. Thus, to predict their decisions one has to learn the agent's preferences. A key step in the learning process is selecting a model to represent those preferences. We studied this problem by borrowing techniques from the algorithm selection problem to analyze preference example sets and select the most appropriate preference representation for learning. We approached this problem in multiple steps.

First, we determined which representations to consider. For this problem we developed the notion of preference representation language subsumption, which compares representations based on their expressive power. Subsumption creates a hierarchy of preference …

Deep Unsupervised Anomaly Detection, Tangqing Li, Zheng Wang, Siying Liu, Wen-Yan Lin

Research Collection School Of Computing and Information Systems

This paper proposes a novel method to detect anomalies in large datasets under a fully unsupervised setting. The key idea behind our algorithm is to learn the representation underlying normal data. To this end, we leverage the latest clustering technique suitable for handling high dimensional data. This hypothesis provides a reliable starting point for normal data selection. We train an autoencoder from the normal data subset, and iterate between hypothesizing normal candidate subset based on clustering and representation learning. The reconstruction error from the learned autoencoder serves as a scoring function to assess the normality of the data. Experimental results …

Explainable Feature- And Decision-Level Fusion, Siva Krishna Kakula

Dissertations, Master's Theses and Master's Reports

Information fusion is the process of aggregating knowledge from multiple data sources to produce more consistent, accurate, and useful information than any one individual source can provide. In general, there are three primary sources of data/information: humans, algorithms, and sensors. Typically, objective data---e.g., measurements---arise from sensors. Using these data sources, applications such as computer vision and remote sensing have long been applying fusion at different "levels" (signal, feature, decision, etc.). Furthermore, the daily advancement in engineering technologies like smart cars, which operate in complex and dynamic environments using multiple sensors, are raising both the demand for and complexity of fusion. …

A Hybrid Gene Selection Strategy Based On Fisher And Ant Colony Optimization Algorithm For Breast Cancer Classification, Mohammed Hamim, Ismail El Moudden, Mohan D. Pant, Hicham Moutachaouik, Mustapha Hain

EVMS School of Health Professions Faculty Publications

Breast cancer poses the greatest threat to human life and especially to women's life. Despite the progress made in data mining technology in recent years, the ability to predict and diagnose such fatal diseases based on gene expression data still reveals a limited prediction performance, which may not be surprising since most of the genes in expression data are believed to be irrelevant or redundant. The dimensionality reduction process may be considered as a crucial step to analyze gene expression data, as it can reduce the high dimensionality of the breast cancer datasets, which may result into a better prediction …

Systematizing Confidence In Open Research And Evidence (Score), Nazanin Alipourfard, Beatrix Arendt, Daniel M. Benjamin, Noam Benkler, Michael Bishop, Mark Burstein, Martin Bush, James Caverlee, Yiling Chen, Chae Clark, Anna Dreber Almenberg, Timothy M. Errington, Fiona Fidler, Nicholas Fox, Aaron Frank, Hannah Fraser, Scott Friedman, Ben Gelman, James Gentile, Jian Wu, Et Al., Score Collaboration

Computer Science Faculty Publications

Assessing the credibility of research claims is a central, continuous, and laborious part of the scientific process. Credibility assessment strategies range from expert judgment to aggregating existing evidence to systematic replication efforts. Such assessments can require substantial time and effort. Research progress could be accelerated if there were rapid, scalable, accurate credibility indicators to guide attention and resource allocation for further assessment. The SCORE program is creating and validating algorithms to provide confidence scores for research claims at scale. To investigate the viability of scalable tools, teams are creating: a database of claims from papers in the social and behavioral …

Understanding The Research And Applications Of Quantum Computing, Joshua Foss

Williams Honors College, Honors Research Projects

In-Depth research of current quantum computing understanding and practices. Presentation of possible new and creative applications of quantum computing.

Learning From Multi-Class Imbalanced Big Data With Apache Spark, William C. Sleeman Iv

Theses and Dissertations

With data becoming a new form of currency, its analysis has become a top priority in both academia and industry, furthering advancements in high-performance computing and machine learning. However, these large, real-world datasets come with additional complications such as noise and class overlap. Problems are magnified when with multi-class data is presented, especially since many of the popular algorithms were originally designed for binary data. Another challenge arises when the number of examples are not evenly distributed across all classes in a dataset. This often causes classifiers to favor the majority class over the minority classes, leading to undesirable results …

Scaling Up Exact Neural Network Compression By Relu Stability, Thiago Serra, Xin Yu, Abhinav Kumar, Srikumar Ramalingam

Faculty Conference Papers and Presentations

We can compress a rectifier network while exactly preserving its underlying functionality with respect to a given input domain if some of its neurons are stable. However, current approaches to determine the stability of neurons with Rectified Linear Unit (ReLU) activations require solving or finding a good approximation to multiple discrete optimization problems. In this work, we introduce an algorithm based on solving a single optimization problem to identify all stable neurons. Our approach is on median 183 times faster than the state-of-art method on CIFAR-10, which allows us to explore exact compression on deeper (5 x 100) and wider …

Learning Accurate And Robust Deep Visual Models, Yandong Li

Electronic Theses and Dissertations, 2020-2023

Over the last decade, we have witnessed the renaissance of deep neural networks (DNNs) and their successful applications in computer vision. There is still a long way to build intelligent and reliable machine vision systems, but DNNs provide a promising direction. The goal of this thesis is to present a few small steps along this road. We mainly focus on two questions: How to design label-efficient learning algorithms for computer vision tasks? How to improve the robustness of DNN based visual models? Concerning label-efficiency, we investigate a reinforced sequential model for video summarization, a background hallucination strategy for high-resolution image …

Ssentiaa: A Self-Supervised Sentiment Analyzer For Classification From Unlabeled Data, Salim Sazzed, Sampath Jayarathna

Computer Science Faculty Publications

In recent years, supervised machine learning (ML) methods have realized remarkable performance gains for sentiment classification utilizing labeled data. However, labeled data are usually expensive to obtain, thus, not always achievable. When annotated data are unavailable, the unsupervised tools are exercised, which still lag behind the performance of supervised ML methods by a large margin. Therefore, in this work, we focus on improving the performance of sentiment classification from unlabeled data. We present a self-supervised hybrid methodology SSentiA (Self-supervised Sentiment Analyzer) that couples an ML classifier with a lexicon-based method for sentiment classification from unlabeled data. We first introduce LRSentiA …

Modified Firearm Discharge Residue Analysis Utilizing Advanced Analytical Techniques, Complexing Agents, And Quantum Chemical Calculations, William J. Feeney

Graduate Theses, Dissertations, and Problem Reports (ETD)

The use of gunshot residue (GSR) or firearm discharge residue (FDR) evidence faces some challenges because of instrumental and analytical limitations and the difficulties in evaluating and communicating evidentiary value. For instance, the categorization of GSR based only on elemental analysis of single, spherical particles is becoming insufficient because newer ammunition formulations produce residues with varying particle morphology and composition. Also, one common criticism about GSR practitioners is that their reports focus on the presence or absence of GSR in an item without providing an assessment of the weight of the evidence. Such reports leave the end-used with unanswered questions, …

Partial Adversarial Behavior Deception In Security Games, Thanh H. Nguyen, Arunesh Sinha, He He

Research Collection School Of Computing and Information Systems

Learning attacker behavior is an important research topic in security games as security agencies are often uncertain about attackers’ decision making. Previous work has focused on developing various behavioral models of attackers based on historical attack data. However, a clever attacker can manipulate its attacks to fail such attack-driven learning, leading to ineffective defense strategies. We study attacker behavior deception with three main contributions. First, we propose a new model, named partial behavior deception model, in which there is a deceptive attacker (among multiple attackers) who controls a portion of attacks. Our model captures real-world security scenarios such as wildlife …

Optimal Construction Of A Layer-Ordered Heap And Its Applications, Jake Pennington

Graduate Student Theses, Dissertations, & Professional Papers

The layer-ordered heap (LOH) is a simple data structure used in algorithms that perform optimal top-$k$ on $X+Y$, algorithms with the best known runtime for top-$k$ on $X_1+X_2+\cdots+X_m$, and the fastest method in practice for computing the most abundant isotopologue peaks in a chemical compound. In the analysis of these algorithms, the rank, $\alpha$, has been treated as a constant and $n$, the size of the array, has been treated as the sole parameter. Here, we explore the algorithmic complexity of LOH construction with $\alpha$ as a parameter, introduce a few algorithms for constructing LOHs, analyze their complexity in both …

Efficient Algorithms For Identifying Loop Formation And Computing Θ Value For Solving Minimum Cost Flow Network Problems, Timothy Michael Chávez, Duc Thai Nguyen

Computational Modeling & Simulation Engineering Faculty Publications

While the minimum cost flow (MCF) problems have been well documented in many publications, due to its broad applications, little or no effort have been devoted to explaining the algorithms for identifying loop formation and computing the value needed to solve MCF network problems. This paper proposes efficient algorithms, and MATLAB computer implementation, for solving MCF problems. Several academic and real-life network problems have been solved to validate the proposed algorithms; the numerical results obtained by the developed MCF code have been compared and matched with the built-in MATLAB function Linprog() (Simplex algorithm) for further validation.

Gene Selection For Cancer Classification: A New Hybrid Filter-C5.0 Approach For Breast Cancer Risk Prediction, Mohammed Hamim, Ismail El Moudden, Hicham Moutachaouik, Mustapha Hain

Department of Medicine Faculty Publications

Despite the significant progress made in data mining technologies in recent years, breast cancer risk prediction and diagnosis at an early stage using DNA microarray technology still a real challenging task. This challenge comes especially from the high-dimensionality in gene expression data, i.e., an enormous number of genes versus a few tens of subjects (samples). To overcome this problem of data imbalance, a gene selection phase becomes a crucial step for gene expression data analysis. This study proposes a new Decision Tree model-based attributes (genes) selection strategy, which incorporates two stages: fisher-score-based filter technique and the gene selection ability of …

A Novel Dimensionality Reduction Approach To Improve Microarray Data Classification, Mohammed Hasim, Ismail El Mouden, Mounir Ouzir, Hicham Moutachaouik, Mustapha Hain

Department of Medicine Faculty Publications

Cancer tumor prediction and diagnosis at an early stage has become a necessity in cancer research, as it provides an increase in the treatment success chances. Recently, DNA microarray technology became a powerful tool for cancer identification, that can analyze the expression level of a different and huge number of genes simultaneously. In microarray data, the large genes number versus a few records may affect the prediction performance. In order to handle this "curse of dimensionality” constraint of microarray dataset while improving the cancer identification performance, a dimensional reduction phase is necessary. In this paper, we proposed a framework that …