Theory and Algorithms Commons^™

Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi

School of Computing: Dissertations, Theses, and Student Research

The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the …

Towards Erasing The Distinction Between The Computational And Syntactic Accounts Of Scientific Theories, Timothy Luft

Theses

One of the main goals of philosophy of science is to give a proper account of scientific theories and their structure. One way that accounts of the structure of scientific theories can be distinguished is by the mathematical or logical structures that they involve. For instance, syntactic accounts of scientific theories hold that theories are axioms in a logical framework, whereas semantic accounts are more liberal in the range of mathematical and logical structures they take as pertinent to the structure of scientific theories. Paul Thagard (1988) offers a computational account of scientific theories, which holds that theories are complex …

Mathematically Rigorous Deep Learning Paradigms For Data-Driven Scientific Modeling, Owen Nicholas Davis

Mathematics & Statistics ETDs

This dissertation explores the crucial role of data-driven modeling in science and engineering, with a focus on developing surrogate models to accelerate large-scale computational tasks, aiding in both outer-loop functions like uncertainty quantification and expensive inner-loop tasks within broader computational frameworks. Challenges arise with increased problem dimension and sparse, noisy training data, particularly significant when constructing surrogates for very expensive computational models where acquiring sufficient high-fidelity training data is unfeasible. In such scenarios, training surrogates from an ensemble of multifidelity information sources of varying accuracy and cost becomes essential. We emphasize neural network-based modeling paradigms, which are flexible in integrating …

Wang Tilings In Arbitrary Dimensions, Ian Tassin

Rose-Hulman Undergraduate Mathematics Journal

This paper makes a new observation about arbitrary dimensional Wang Tilings,
demonstrating that any d -dimensional tile set that can tile periodically along d − 1 axes must be able to tile periodically along all axes.
This work also summarizes work on Wang Tiles up to the present day, including
definitions for various aspects of Wang Tilings such as periodicity and the validity of a tiling. Additionally, we extend the familiar 2D definitions for Wang Tiles and associated properties into arbitrary dimensional spaces. While there has been previous discussion of arbitrary dimensional Wang Tiles in other works, it has been …

Graph Coloring Reconfiguration, Reem Mahmoud

Theses and Dissertations

Reconfiguration is the concept of moving between different solutions to a problem by transforming one solution into another using some prescribed transformation rule (move). Given two solutions s₁ and s₂ of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s₁ into s₂. Reconfiguration is an area of research with many contributions towards various fields such as mathematics and computer science.
The k-coloring reconfiguration problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type …

Hyperparameter Estimation For Sparse Bayesian Learning Models, Feng Yu, Lixin Shen, Guohui Song

Mathematics & Statistics Faculty Publications

Sparse Bayesian learning (SBL) models are extensively used in signal processing and machine learning for promoting sparsity through hierarchical priors. The hyperparameters in SBL models are crucial for the model’s performance, but they are often difficult to estimate due to the nonconvexity and the high-dimensionality of the associated objective function. This paper presents a comprehensive framework for hyperparameter estimation in SBL models, encompassing well-known algorithms such as the expectation-maximization, MacKay, and convex bounding algorithms. These algorithms are cohesively interpreted within an alternating minimization and linearization (AML) paradigm, distinguished by their unique linearized surrogate functions. Additionally, a novel algorithm within the …

Continuous-Variable Quantum Computation Of The O(3) Model In 1+1 Dimensions, Raghav G. Jha, Felix Ringer, George Siopsis, Shane Thompson

Physics Faculty Publications

We formulate the O(3) nonlinear sigma model in 1+1 dimensions as a limit of a three-component scalar field theory restricted to the unit sphere in the large squeezing limit. This allows us to describe the model in terms of the continuous-variable (CV) approach to quantum computing. We construct the ground state and excited states using the coupled-cluster Ansatz and find excellent agreement with the exact diagonalization results for a small number of lattice sites. We then present the simulation protocol for the time evolution of the model using CV gates and obtain numerical results using a photonic quantum simulator. We …

The Computational Search For Unidentified Central Configurations Of The Newtonian N-Body Problem, Hannah G. Havel

CURE Proceedings

The N-body problem is a field of study in mathematics and physics that involves predicting the motion of particles moving under their mutual gravitational attraction. It is vital in celestial mechanics, such as planning collision-free satellite orbit trajectories. When beginning to understand the N-body problem, we can start by looking at equal masses of these particles or celestial bodies. As particles move, their position and velocity change, both energy and angular momentum are conserved. Sets of constant energy and angular momentum, known as integral manifolds, are higher-dimensional figures that represent constraints of movement to a system. Integral manifolds are described …

Adaptive Neh With Constrained Nearest Neighbor Subtours For The Electric Vehicle Routing Problem With Time Windows, Andrew Struthers

All Master's Theses

The development of electric vehicles is currently considered one of the most innovative areas in manufacturing. Largely driven by the desire to reduce greenhouse emissions, electric vehicles are seen as a viable alternative to internal combustion engine cars. Starting from consumer cars, a dedicated effort is being made to translate this into commercial vehicles for freight and delivery. This research introduces a novel adaptive Nawaz, Enscore, Ham (NEH) algorithm with constrained nearest neighbor subtour (NEH-NN). This algorithm is tested on the standard benchmark problems in literature and used as a seed solution for the Genetic Algorithm (GA). The performance and …

Inexact Fixed-Point Proximity Algorithm For The ℓ₀ Sparse Regularization Problem, Ronglong Fang, Yuesheng Xu, Mingsong Yan

Mathematics & Statistics Faculty Publications

We study inexact fixed-point proximity algorithms for solving a class of sparse regularization problems involving the ℓ₀ norm. Specifically, the ℓ₀ model has an objective function that is the sum of a convex fidelity term and a Moreau envelope of the ℓ₀ norm regularization term. Such an ℓ₀ model is non-convex. Existing exact algorithms for solving the problems require the availability of closed-form formulas for the proximity operator of convex functions involved in the objective function. When such formulas are not available, numerical computation of the proximity operator becomes inevitable. This leads to inexact iteration algorithms. We investigate in this …

Reducing Food Scarcity: The Benefits Of Urban Farming, S.A. Claudell, Emilio Mejia

Journal of Nonprofit Innovation

Urban farming can enhance the lives of communities and help reduce food scarcity. This paper presents a conceptual prototype of an efficient urban farming community that can be scaled for a single apartment building or an entire community across all global geoeconomics regions, including densely populated cities and rural, developing towns and communities. When deployed in coordination with smart crop choices, local farm support, and efficient transportation then the result isn’t just sustainability, but also increasing fresh produce accessibility, optimizing nutritional value, eliminating the use of ‘forever chemicals’, reducing transportation costs, and fostering global environmental benefits.

Imagine Doris, who is …

An Empirical Study Of Machine Learning Techniques For Accurate Stock Price Forecasting, Daniel Paliulis, Hari Patchigolla

Honors Scholar Theses

This paper presents a comprehensive approach to predicting future stock prices of companies using machine learning and time series analysis. The research problem is centered around addressing the complexity and emotion-driven nature of stock investment decisions. To create an objective determinant in stock decisions, we propose a machine learning model utilizing time series data from major companies, including Amazon, Apple, Google, Nvidia, Meta, Tesla, Salesforce, Intel, and Microsoft. We explore the use of Long Short-Term Memory (LSTM) neural networks, to capture the temporal dynamics of stock prices. These models are designed to process sequential data, maintaining short term and long …

On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak

Theory & Applications of Graphs

The Balanced Connected Subgraph problem (BCS) was introduced by Bhore et al. In the BCS problem we are given a vertex-colored graph G = (V, E) where each vertex is colored “red” or “blue”. The goal is to find a maximum cardinality induced connected subgraph H of G such that H contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as many special classes of graphs. In this work we explore the time complexity of the BCS problem in case of regular graphs. We prove that the BCS …

The Vulnerabilities To The Rsa Algorithm And Future Alternative Algorithms To Improve Security, James Johnson

Cybersecurity Undergraduate Research Showcase

The RSA encryption algorithm has secured many large systems, including bank systems, data encryption in emails, several online transactions, etc. Benefiting from the use of asymmetric cryptography and properties of number theory, RSA was widely regarded as one of most difficult algorithms to decrypt without a key, especially since by brute force, breaking the algorithm would take thousands of years. However, in recent times, research has shown that RSA is getting closer to being efficiently decrypted classically, using algebraic methods, (fully cracked through limited bits) in which elliptic-curve cryptography has been thought of as the alternative that is stronger than …

Foundations Of Memory Capacity In Models Of Neural Cognition, Chandradeep Chowdhury

Master's Theses

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the …

A Bridge Between Graph Neural Networks And Transformers: Positional Encodings As Node Embeddings, Bright Kwaku Manu

Electronic Theses and Dissertations

Graph Neural Networks and Transformers are very powerful frameworks for learning machine learning tasks. While they were evolved separately in diverse fields, current research has revealed some similarities and links between them. This work focuses on bridging the gap between GNNs and Transformers by offering a uniform framework that highlights their similarities and distinctions. We perform positional encodings and identify key properties that make the positional encodings node embeddings. We found that the properties of expressiveness, efficiency and interpretability were achieved in the process. We saw that it is possible to use positional encodings as node embeddings, which can be …

Evaluation Of Symmetric Functions And Boolean Functions Over Stochastic Input, Naifeng Liu

Dissertations, Theses, and Capstone Projects

In our daily life, we often face situations where we need to make precise judgments based on initially unknown information, while gathering all the evidence to make informed conclusions can be very costly. In this dissertation, we explore the problem of optimizing the decision-making process under uncertainty, and we focus on problems that can be found in both theoretical computer science and discrete mathematics. The primary goal is to develop approximation algorithms with guaranteed worst-case performance. These algorithms aim to minimize the expected cost of acquiring information necessary for evaluating fundamental functions, such as Boolean and symmetric functions. Furthermore, we …

Signings Of Graphs And Sign-Symmetric Signed Graphs, Ahmad Asiri

Theses and Dissertations

In this dissertation, we investigate various aspects of signed graphs, with a particular focus on signings and sign-symmetric signed graphs. We begin by examining the complete graph on six vertices with one edge deleted ($K_6$\textbackslash e) and explore the different ways of signing this graph up to switching isomorphism. We determine the frustration index (number) of these signings and investigate the existence of sign-symmetric signed graphs. We then extend our study to the $K_6$\textbackslash 2e graph and the McGee graph with exactly two negative edges. We investigate the distinct ways of signing these graphs up to switching isomorphism and demonstrate …

A Survey On Online Matching And Ad Allocation, Ryan Lee

Theses

One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …

Partitions Of R^N With Maximal Seclusion And Their Applications To Reproducible Computation, Jason Vander Woude

Department of Mathematics: Dissertations, Theses, and Student Research

We introduce and investigate a natural problem regarding unit cube tilings/partitions of Euclidean space and also consider broad generalizations of this problem. The problem fits well within a historical context of similar problems and also has applications to the study of reproducibility in randomized computation.

Given $k\in\mathbb{N}$ and $\epsilon\in(0,\infty)$, we define a $(k,\epsilon)$-secluded unit cube partition of $\mathbb{R}^{d}$ to be a unit cube partition of $\mathbb{R}^{d}$ such that for every point $\vec{p}\in\R^d$, the closed $\ell_{\infty}$ $\epsilon$-ball around $\vec{p}$ intersects at most $k$ cubes. The problem is to construct such partitions for each dimension $d$ with the primary goal of minimizing …

Machine Learning-Based Data And Model Driven Bayesian Uncertanity Quantification Of Inverse Problems For Suspended Non-Structural System, Zhiyuan Qin

All Dissertations

Inverse problems involve extracting the internal structure of a physical system from noisy measurement data. In many fields, the Bayesian inference is used to address the ill-conditioned nature of the inverse problem by incorporating prior information through an initial distribution. In the nonparametric Bayesian framework, surrogate models such as Gaussian Processes or Deep Neural Networks are used as flexible and effective probabilistic modeling tools to overcome the high-dimensional curse and reduce computational costs. In practical systems and computer models, uncertainties can be addressed through parameter calibration, sensitivity analysis, and uncertainty quantification, leading to improved reliability and robustness of decision and …

Applying Hallgren’S Algorithm For Solving Pell’S Equation To Finding The Irrational Slope Of The Launch Of A Billiard Ball, Sangheon Choi

Mathematical Sciences Technical Reports (MSTR)

This thesis is an exploration of Quantum Computing applied to Pell’s equation in an attempt to find solutions to the Billiard Ball Problem. Pell’s equation is a Diophantine equation in the form of x² − ny² = 1, where n is a given positive nonsquare integer, and integer solutions are sought for x and y. We will be applying Hallgren’s algorithm for finding irrational periods in functions, in the context of billiard balls and their movement on a friction-less unit square billiard table. Our central research question has been the following: Given the cutting sequence of the billiard …

Time Evolution Is A Source Of Bias In The Wolf Algorithm For Largest Lyapunov Exponents, Kolby Brink, Tyler Wiles, Nicholas Stergiou, Aaron Likens

UNO Student Research and Creative Activity Fair

Human movement is inherently variable by nature. One of the most common analytical tools for assessing movement variability is the largest Lyapunov exponent (LyE) which quantifies the rate of trajectory divergence or convergence in an n-dimensional state space. One popular method for assessing LyE is the Wolf algorithm. Many studies have investigated how Wolf’s calculation of the LyE changes due to sampling frequency, filtering, data normalization, and stride normalization. However, a surprisingly understudied parameter needed for LyE computation is evolution time. The purpose of this study is to investigate how the LyE changes as a function of evolution time …

Generalizing Math Word Problem Solvers Via Solution Diversification, Zhenwen Liang, Jipeng Zhang, Lei Wang, Yan Wang, Jie Shao, Xiangliang Zhang

Research Collection School Of Computing and Information Systems

Current math word problem (MWP) solvers are usually Seq2Seq models trained by the (one-problem; one-solution) pairs, each of which is made of a problem description and a solution showing reasoning flow to get the correct answer. However, one MWP problem naturally has multiple solution equations. The training of an MWP solver with (one-problem; one-solution) pairs excludes other correct solutions, and thus limits the generalizability of the MWP solver. One feasible solution to this limitation is to augment multiple solutions to a given problem. However, it is difficult to collect diverse and accurate augment solutions through human efforts. In this paper, …

Peer-To-Peer Energy Trading In Smart Residential Environment With User Behavioral Modeling, Ashutosh Timilsina

Theses and Dissertations--Computer Science

Electric power systems are transforming from a centralized unidirectional market to a decentralized open market. With this shift, the end-users have the possibility to actively participate in local energy exchanges, with or without the involvement of the main grid. Rapidly reducing prices for Renewable Energy Technologies (RETs), supported by their ease of installation and operation, with the facilitation of Electric Vehicles (EV) and Smart Grid (SG) technologies to make bidirectional flow of energy possible, has contributed to this changing landscape in the distribution side of the traditional power grid.

Trading energy among users in a decentralized fashion has been referred …

Clusters, Curves, And Centroids: Stellar Flare Morphology In The Ultraviolet, Vera Berger

Pomona Senior Theses

With a novel sample of 495 high-cadence light curves for stellar flares in the near-ultraviolet, I explore similarity measures, clustering algorithms, averaging methods, and curve fitting techniques for time series. This work seeks to provide insight into whether stellar flares are similar across stars, if we can identify physically meaningful patterns in their light curves, and how to construct a comprehensive model for flares. I construct the first empirical template for flare light curves in the ultraviolet, and compute ``average elements" of flares displaying complex features such as quasi-periodic oscillations and multipeak structures. Developing accurate models for flares in the …

Machine-Assisted Discovery Of Integrable Symplectic Mappings, T. Zolkin, Y. Kharkov, S. Nagaitsev

Physics Faculty Publications

We present a new automated method for finding integrable symplectic maps of the plane. These dynamical systems possess a hidden symmetry associated with an existence of conserved quantities, i.e., integrals of motion. The core idea of the algorithm is based on the knowledge that the evolution of an integrable system in the phase space is restricted to a lower-dimensional submanifold. Limiting ourselves to polygon invariants of motion, we analyze the shape of individual trajectories thus successfully distinguishing integrable motion from chaotic cases. For example, our method rediscovers some of the famous McMillan-Suris integrable mappings and ultradiscrete Painlevé equations. In total, …

Generalized Sparse Bayesian Learning And Application To Image Reconstruction, Jan Glaubitz, Anne Gelb, Guohui Song

Mathematics & Statistics Faculty Publications

Image reconstruction based on indirect, noisy, or incomplete data remains an important yet challenging task. While methods such as compressive sensing have demonstrated high-resolution image recovery in various settings, there remain issues of robustness due to parameter tuning. Moreover, since the recovery is limited to a point estimate, it is impossible to quantify the uncertainty, which is often desirable. Due to these inherent limitations, a sparse Bayesian learning approach is sometimes adopted to recover a posterior distribution of the unknown. Sparse Bayesian learning assumes that some linear transformation of the unknown is sparse. However, most of the methods developed are …

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).

The Dope Distance Is Sic: A Stable, Informative, And Computable Metric On Ordered Merge Trees, Jose Arbelo, Antonio Delgado, Charley Kirk, Zach Schlamowitz

Mathematics Summer Fellows

When analyzing time series data, it is often of interest to categorize them based on how different they are. We define a new dissimilarity measure between time series: Dynamic Ordered Persistence Editing (DOPE). DOPE satisfies metric properties, is stable to noise, is as informative as alternative approaches, and efficiently computable. Satisfying these properties simultaneously makes DOPE of interest to both theoreticians and data scientists alike.