Theory and Algorithms Commons^™

The History Of The Enigma Machine, Jenna Siobhan Parkinson

History Publications

The history of the Enigma machine begins with the invention of the rotor-based cipher machine in 1915. Various models for rotor-based cipher machines were developed somewhat simultaneously in different parts of the world. However, the first documented rotor machine was developed by Dutch naval officers in 1915. Nonetheless, the Enigma machine was officially invented following the end of World War I by Arthur Scherbius in 1918 (Faint, 2016).

Improving Adjacency List Storage Methods For Polypeptide Similarity Analysis, Arianna Swensen

Honors Theses

Protein design is a complex biomolecular and computational problem. Working on increasingly large protein folding problems requires an improvement in current analysis methods available. This work first discusses various methods of protein design, including de novo protein design, which is the primary focus of this thesis. Then, a new approach utilizing a B+ tree to effectively store and query a graph of keys and vertices is proposed in order to store the number of times two polypeptides are considered to be similar. This approach is found to have a reduction in time complexity from current mapping methods and thus provides …

Obstacles In Learning Algorithm Run-Time Complexity Analysis, Bailey Licht

Theses/Capstones/Creative Projects

Algorithm run-time complexity analysis is an important topic in data structures and algorithms courses, but it is also a topic that many students struggle with. Commonly cited difficulties include the necessary mathematical background knowledge, the abstract nature of the topic, and the presentation style of the material. Analyzing the subject of algorithm analysis using multiple learning theories shows that course materials often leave out key steps in the learning process and neglect certain learning styles. Students can be more successful at learning algorithm run-time complexity analysis if these missing stages and learning styles are addressed.

An Efficient Annealing-Assisted Differential Evolution For Multi-Parameter Adaptive Latent Factor Analysis, Qing Li, Guansong Pang, Mingsheng Shang

Research Collection School Of Computing and Information Systems

A high-dimensional and incomplete (HDI) matrix is a typical representation of big data. However, advanced HDI data analysis models tend to have many extra parameters. Manual tuning of these parameters, generally adopting the empirical knowledge, unavoidably leads to additional overhead. Although variable adaptive mechanisms have been proposed, they cannot balance the exploration and exploitation with early convergence. Moreover, learning such multi-parameters brings high computational time, thereby suffering gross accuracy especially when solving a bilinear problem like conducting the commonly used latent factor analysis (LFA) on an HDI matrix. Herein, an efficient annealing-assisted differential evolution for multi-parameter adaptive latent factor analysis …

Multivariate Fairness For Paper Selection, Reem Alsaffar

Graduate Theses and Dissertations

Peer review is the process by which publishers select the best publications for inclusion in a journal or a conference. Bias in the peer review process can impact which papers are selected for inclusion in conferences and journals. Although often implicit, race, gender and other demographics can prevent members of underrepresented groups from presenting at major conferences. To try to avoid bias, many conferences use a double-blind review process to increase fairness during reviewing. However, recent studies argue that the bias has not been removed completely. Our research focuses on developing fair algorithms that correct for these biases and select …

Distilled Siamese Networks For Visual Tracking, Jianbing Shen, Yuanpei Liu, Xingping Dong, Xiankai Lu, Fahad Shahbaz Khan, Steven Hoi

Research Collection School Of Computing and Information Systems

In recent years, Siamese network based trackers have significantly advanced the state-of-the-art in real-time tracking. Despite their success, Siamese trackers tend to suffer from high memory costs, which restrict their applicability to mobile devices with tight memory budgets. To address this issue, we propose a distilled Siamese tracking framework to learn small, fast and accurate trackers (students), which capture critical knowledge from large Siamese trackers (teachers) by a teacher-students knowledge distillation model. This model is intuitively inspired by the one teacher versus multiple students learning method typically employed in schools. In particular, our model contains a single teacher-student distillation module …

Forks Over Knives: Predictive Inconsistency In Criminal Justice Algorithmic Risk Assessment Tools, Travis Greene, Galit Shmueli, Jan Fell, Ching-Fu Lin, Han-Wei Liu

Research Collection Yong Pung How School Of Law

Big data and algorithmic risk prediction tools promise to improve criminal justice systems by reducing human biases and inconsistencies in decision-making. Yet different, equally justifiable choices when developing, testing and deploying these socio-technical tools can lead to disparate predicted risk scores for the same individual. Synthesising diverse perspectives from machine learning, statistics, sociology, criminology, law, philosophy and economics, we conceptualise this phenomenon as predictive inconsistency. We describe sources of predictive inconsistency at different stages of algorithmic risk assessment tool development and deployment and consider how future technological developments may amplify predictive inconsistency. We argue, however, that in a diverse and …

Inception Transformer, Chenyang Si, Weihao Yu, Pan Zhou, Yichen Zhou, Xinchao Wang, Shuicheng Yan

Research Collection School Of Computing and Information Systems

Recent studies show that Transformer has strong capability of building long-range dependencies, yet is incompetent in capturing high frequencies that predominantly convey local information. To tackle this issue, we present a novel and general-purpose Inception Transformer, or iFormer for short, that effectively learns comprehensive features with both high- and low-frequency information in visual data. Specifically, we design an Inception mixer to explicitly graft the advantages of convolution and max-pooling for capturing the high-frequency information to Transformers. Different from recent hybrid frameworks, the Inception mixer brings greater efficiency through a channel splitting mechanism to adopt parallel convolution/max-pooling path and self-attention path …

A Quality Metric For K-Means Clustering Based On Centroid Locations, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

K-Means clustering algorithm does not offer a clear methodology to determine the appropriate number of clusters; it does not have a built-in mechanism for K selection. In this paper, we present a new metric for clustering quality and describe its use for K selection. The proposed metric, based on the locations of the centroids, as well as the desired properties of the clusters, is developed in two stages. In the initial stage, we take into account the full covariance matrix of the clustering variables, thereby making it mathematically similar to a reduced chi2. We then extend it to account for …

Meta-Complementing The Semantics Of Short Texts In Neural Topic Models, Ce Zhang, Hady Wirawan Lauw

Research Collection School Of Computing and Information Systems

Topic models infer latent topic distributions based on observed word co-occurrences in a text corpus. While typically a corpus contains documents of variable lengths, most previous topic models treat documents of different lengths uniformly, assuming that each document is sufficiently informative. However, shorter documents may have only a few word co-occurrences, resulting in inferior topic quality. Some other previous works assume that all documents are short, and leverage external auxiliary data, e.g., pretrained word embeddings and document connectivity. Orthogonal to existing works, we remedy this problem within the corpus itself by proposing a Meta-Complement Topic Model, which improves topic quality …

An Algorithm For Indoor Sars-Cov-2 Transmission, Daniel Maxin, Spencer Gannon

Journal of Mind and Medical Sciences

We propose a computer modeling approach for SARS-CoV-2 transmission that can be preferable to a purely mathematical framework. It is illustrated its functionality in a specific case of indoor transmission. Based on literature, we assume that infection is due to aerosols with viral particles that persist and accumulate for hours in the air even after the persons who produced them left the space. We incorporate also restricted opening hours as a mitigation measure and one possible behavioral change in response to this measure. It is shown via several examples how this algorithmic modeling approach can be used to run various …

Path Choice Of Algorithm Intellectual Property Protection, Yulu Jin, Youdan Xiao

Bulletin of Chinese Academy of Sciences (Chinese Version)

Protection of algorithm by intellectual property is a powerful way to stimulate innovation and regulate the risk of the algorithm. Algorithm that can be protected by intellectual property right is the program algorithm, which is compiled in computer language, in the form of coded instruction sequence, run by the computer and produce independent rational value results. The article is combed out that there are drawbacks to the traditional path of IP to protect program algorithms:it has conflict between program algorithm and copyright law system; the trade secret path is at odds with program algorithmic governance; and program algorithm can hardly …

Artificial Intelligence And The Situational Rationality Of Diagnosis: Human Problem-Solving And The Artifacts Of Health And Medicine, Michael W. Raphael

Publications and Research

What is the problem-solving capacity of artificial intelligence (AI) for health and medicine? This paper draws out the cognitive sociological context of diagnostic problem-solving for medical sociology regarding the limits of automation for decision-based medical tasks. Specifically, it presents a practical way of evaluating the artificiality of symptoms and signs in medical encounters, with an emphasis on the visualization of the problem-solving process in doctor-patient relationships. In doing so, the paper details the logical differences underlying diagnostic task performance between man and machine problem-solving: its principle of rationality, the priorities of its means of adaptation to abstraction, and the effects …

Generic Conversions From Cpa To Cca Without Ciphertext Expansion For Threshold Abe With Constant-Size Ciphertexts, J Lai, F Guo, W Susilo, P Jiang, Guomin Yang, X. Huang

Research Collection School Of Computing and Information Systems

CCA security is desirable when designing encryption schemes because it captures active attackers. One efficient approach for achieving CCA security is to use generic conversions. We first design a CPA secure scheme, and then transform it into a CCA secure scheme using the Fujisaki-Okamoto technique (CRYPTO ’99) in the random oracle model or the Canetti-Halevi-Katz technique (EUROCRYPT ’04) in the standard model if the CPA secure scheme satisfies some conditions. These transformations are generic so they can be applied to encryption primitives such as IBE and ABE. Nevertheless, both techniques result in an inevitable ciphertext expansion. Subsequent generic constructions mainly …

Dynamic Return Relationships In The Market For Cryptocurrency: A Var Approach, Julian Gouffray

James Madison Undergraduate Research Journal (JMURJ)

This paper examines how the Bitcoin-altcoin return relationship has evolved in periods between 2015 and 2020. To understand this relation, we observe data on the cryptocurrency Bitcoin and prominent altcoins Ethereum, Litecoin, Ripple, Stellar, and Monero, which collectively represent over 90% of the market throughout the observed period. We employ a vector autoregressive model (VAR) to produce forecast error variance decompositions, orthogonal impulse response functions, and Granger-causality tests. We find evidence that Bitcoin return variation has increasingly explained altcoin returns and that market inefficiency increased between 2017 and 2020, as shown by increased Granger causality between Bitcoin and altcoins. These …

Cov-Inception: Covid-19 Detection Tool Using Chest X-Ray, Aswini Thota, Ololade Awodipe, Rashmi Patel

SMU Data Science Review

Since the pandemic started, researchers have been trying to find a way to detect COVID-19 which is a cost-effective, fast, and reliable way to keep the economy viable and running. This research details how chest X-ray radiography can be utilized to detect the infection. This can be for implementation in Airports, Schools, and places of business. Currently, Chest imaging is not a first-line test for COVID-19 due to low diagnostic accuracy and confounding with other viral pneumonia. Different pre-trained algorithms were fine-tuned and applied to the images to train the model and the best model obtained was fine-tuned InceptionV3 model …

Application Of Probabilistic Ranking Systems On Women’S Junior Division Beach Volleyball, Cameron Stewart, Michael Mazel, Bivin Sadler

SMU Data Science Review

Women’s beach volleyball is one of the fastest growing collegiate sports today. The increase in popularity has come with an increase in valuable scholarship opportunities across the country. With thousands of athletes to sort through, college scouts depend on websites that aggregate tournament results and rank players nationally. This project partnered with the company Volleyball Life, who is the current market leader in the ranking space of junior beach volleyball players. Utilizing the tournament information provided by Volleyball Life, this study explored replacements to the current ranking systems, which are designed to aggregate player points from recent tournament placements. Three …

A Novel Qkd Approach To Enhance Iiot Privacy And Computational Knacks, Kranthi Kumar Singamaneni, Gaurav Dhiman, Sapna Juneja, Ghulam Muhammad, Salman A Alqahtani, John Zaki

Faculty, Staff and Student Publications

The industry-based internet of things (IIoT) describes how IIoT devices enhance and extend their capabilities for production amenities, security, and efficacy. IIoT establishes an enterprise-to-enterprise setup that means industries have several factories and manufacturing units that are dependent on other sectors for their services and products. In this context, individual industries need to share their information with other external sectors in a shared environment which may not be secure. The capability to examine and inspect such large-scale information and perform analytical protection over the large volumes of personal and organizational information demands authentication and confidentiality so that the total data …

An Analysis Of The Friendship Paradox And Derived Sampling Methods, Yitzchak Novick

Dissertations, Theses, and Capstone Projects

The friendship paradox (FP) is the famous sampling-bias phenomenon that leads to the seemingly paradoxical truth that, on average, people’s friends have more friends than they do. Among the many far-reaching research findings the FP inspired is a sampling method that samples neighbors of vertices in a graph in order to acquire random vertices that are of higher expected degree than average.

Our research examines the friendship paradox on a local level. We seek to quantify the impact of the FP on an individual vertex by defining the vertex’s “friendship index”, a measure of the extent to which the phenomenon …

On The Cryptographic Deniability Of The Signal Protocol, Nihal Vatandas

Dissertations, Theses, and Capstone Projects

Offline deniability is the ability to a posteriori deny having participated in a particular communication session. This property has been widely assumed for the Signal messaging application, yet no formal proof has appeared in the literature. In this work, we present the first formal study of the offline deniability of the Signal protocol. Our analysis shows that building a deniability proof for Signal is non-trivial and requires strong assumptions on the underlying mathematical groups where the protocol is run.

To do so, we study various implicitly authenticated key exchange protocols, including MQV, HMQV, and 3DH/X3DH, the latter being the core …

Towards An Optimal Bus Frequency Scheduling: When The Waiting Time Matters, Songsong Mo, Zhifeng Bao, Baihua Zheng, Zhiyong Peng

Research Collection School Of Computing and Information Systems

Reorganizing bus frequencies to cater for actual travel demands can significantly save the cost of the public transport system. This paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an …

Two-Phase Matheuristic For The Vehicle Routing Problem With Reverse Cross-Docking, Aldy Gunawan, Audrey Tedja Widjaja, Pieter Vansteenwegen, Vincent F. Yu

Research Collection School Of Computing and Information Systems

Cross-dockingis a useful concept used by many companies to control the product flow. It enables the transshipment process of products from suppliers to customers. This research thus extends the benefit of cross-docking with reverse logistics, since return process management has become an important field in various businesses. The vehicle routing problem in a distribution network is considered to be an integrated model, namely the vehicle routing problem with reverse cross-docking (VRP-RCD). This study develops a mathematical model to minimize the costs of moving products in a four-level supply chain network that involves suppliers, cross-dock, customers, and outlets. A matheuristic based …

A Carbon-Aware Planning Framework For Production Scheduling In Mining, Nurual Asyikeen Azhar, Aldy Gunawan, Shih-Fen Cheng, Erwin Leonardi

Research Collection School Of Computing and Information Systems

Managing the flow of excavated materials from a mine pit and the subsequent processing steps is the logistical challenge in mining. Mine planning needs to consider various geometric and resource constraints while maximizing the net present value (NPV) of profits over a long horizon. This mine planning problem has been modelled and solved as a precedence constrained production scheduling problem (PCPSP) using heuristics, due to its NP-hardness. However, the recent push for sustainable and carbon-aware mining practices calls for new planning approaches. In this paper, we propose an efficient temporally decomposed greedy Lagrangian relaxation (TDGLR) approach to maximize profits while …

Neural-Progressive Hedging: Enforcing Constraints In Reinforcement Learning With Stochastic Programming, Supriyo Ghosh, Laura Wynter, Shiau Hong Lim, Duc Thien Nguyen

Research Collection School Of Computing and Information Systems

We propose a framework, called neural-progressive hedging (NP), that leverages stochastic programming during the online phase of executing a reinforcement learning (RL) policy. The goal is to ensure feasibility with respect to constraints and risk-based objectives such as conditional value-at-risk (CVaR) during the execution of the policy, using probabilistic models of the state transitions to guide policy adjustments. The framework is particularly amenable to the class of sequential resource allocation problems since feasibility with respect to typical resource constraints cannot be enforced in a scalable manner. The NP framework provides an alternative that adds modest overhead during the online phase. …

Parallel Algorithms For Scalable Graph Mining: Applications On Big Data And Machine Learning, Naw Safrin Sattar

LSU New Orleans Theses and Dissertations

Parallel computing plays a crucial role in processing large-scale graph data. Complex network analysis is an exciting area of research for many applications in different scientific domains e.g., sociology, biology, online media, recommendation systems and many more. Graph mining is an area of interest with diverse problems from different domains of our daily life. Due to the advancement of data and computing technologies, graph data is growing at an enormous rate, for example, the number of links in social networks is growing every millisecond. Machine/Deep learning plays a significant role for technological accomplishments to work with big data in modern …

Directed Acyclic Graph-Based Neural Networks For Tunable Low-Power Computer Vision, Abhinav Goel, Caleb Tung, Nick Eliopoulos, Xiao Hu, George K. Thiruvathukal, James C. Davis, Yung-Hisang Lu

Computer Science: Faculty Publications and Other Works

Processing visual data on mobile devices has many applications, e.g., emergency response and tracking. State-of-the-art computer vision techniques rely on large Deep Neural Networks (DNNs) that are usually too power-hungry to be deployed on resource-constrained edge devices. Many techniques improve DNN efficiency of DNNs by compromising accuracy. However, the accuracy and efficiency of these techniques cannot be adapted for diverse edge applications with different hardware constraints and accuracy requirements. This paper demonstrates that a recent, efficient tree-based DNN architecture, called the hierarchical DNN, can be converted into a Directed Acyclic Graph-based (DAG) architecture to provide tunable accuracy-efficiency tradeoff options. We …

Variational Graph Author Topic Modeling, Ce Zhang, Hady Wirawan Lauw

Research Collection School Of Computing and Information Systems

While Variational Graph Auto-Encoder (VGAE) has presented promising ability to learn representations for documents, most existing VGAE methods do not model a latent topic structure and therefore lack semantic interpretability. Exploring hidden topics within documents and discovering key words associated with each topic allow us to develop a semantic interpretation of the corpus. Moreover, documents are usually associated with authors. For example, news reports have journalists specializing in writing certain type of events, academic papers have authors with expertise in certain research topics, etc. Modeling authorship information could benefit topic modeling, since documents by the same authors tend to reveal …

Distributed Learning With Automated Stepsizes, Benjamin Liggett

All Theses

Stepsizes for optimization problems play a crucial role in algorithm convergence, where the stepsize must undergo tedious manual tuning to obtain near-optimal convergence. Recently, an adaptive method for automating stepsizes was proposed for centralized optimization. However, this method is not directly applicable to decentralized optimization because it allows for heterogeneous agent stepsizes. Furthermore, directly using consensus between agent stepsizes to mitigate stepsize heterogeneity can decrease performance and even lead to divergence.

This thesis proposes an algorithm to remedy the tedious manual tuning of stepsizes in decentralized optimization. Our proposed algorithm automates the stepsize and uses dynamic consensus between agents’ stepsizes …

Unsupervised Contrastive Representation Learning For Knowledge Distillation And Clustering, Fei Ding

All Dissertations

Unsupervised contrastive learning has emerged as an important training strategy to learn representation by pulling positive samples closer and pushing negative samples apart in low-dimensional latent space. Usually, positive samples are the augmented versions of the same input and negative samples are from different inputs. Once the low-dimensional representations are learned, further analysis, such as clustering, and classification can be performed using the representations. Currently, there are two challenges in this framework. First, the empirical studies reveal that even though contrastive learning methods show great progress in representation learning on large model training, they do not work well for small …

Submodularity And Local Search Approaches For Maximum Capture Problems Under Generalized Extreme Value Models, Tien Thanh Dam, Thuy Anh Ta, Tien Mai

Research Collection School Of Computing and Information Systems

We study the maximum capture problem in facility location under random utility models, i.e., the problem of seeking to locate new facilities in a competitive market such that the captured user demand is maximized, assuming that each customer chooses among all available facilities according to a random utility maximization model. We employ the generalized extreme value (GEV) family of discrete choice models and show that the objective function in this context is monotonic and submodular. This finding implies that a simple greedy heuristic can always guarantee a (1−1/e) approximation solution. We further develop a new algorithm combining a greedy heuristic, …