Theory and Algorithms Commons^™

Late-Night And Early-Morning Train Scheduling With Non-Traffic Hour Maintenance Window In Urban Rail Transit Systems, Yaochen Ma, Hai Yang, Hai Wang

Research Collection School Of Computing and Information Systems

Regular maintenance during non-traffic hours (NTH) is vital for the resilience of urban rail transit (URT) systems, yet an insufficient NTH maintenance window poses a challenge for URT systems in various cities. For instance, the Hong Kong MTR Corporation has noted that the required NTH maintenance time often exceeds the available window, prompting service adjustments such as earlier late-night closures and/or later early-morning starts. To address this challenge, this study develops an optimal scheduling framework that links late-night and early-morning URT services through the NTH maintenance window requirement to maximize public welfare. A Decoupled Optimization Model (DOM) first derives closed-form …

Algorithmic Monocultures In Hiring, Rishi Bommasani, Sarah H. Bana, Kathleen A. Creel, Dan Saul Jurafsky, Percy Liang

Economics Faculty Articles and Research

Many employers screen job applicants with algorithms built by the same few algorithm vendors. We hypothesize that algorithmic monoculture leads to the same individuals and members of the same racial groups facing rejection. We acquire and analyze a novel dataset of 3 million applicants submitting 4 million applications where all the applications are screened by algorithms built by the same vendor. We find clear racial disparities in applicant outcomes. Of all applications submitted by Asian and Black applicants, 14.74% and 25.87% are submitted to positions that adversely impact Asian and Black applicants, respectively, according to U.S. employment discrimination standards. Individuals …

Evaluation And Distillation Of Source Code Generation Tasks By Large Language Models, Danny Brahman

Electronic Theses and Dissertations

Large Language Models (LLMs) are predominantly assessed based on their common sense reasoning, language comprehension, and logical reasoning abilities. While models trained in specialized domains like mathematics or coding have demonstrated remarkable advancements in logical reasoning, there remains a significant gap in evaluating their code generation capabilities. Existing benchmark datasets fall short in pinpointing specific strengths and weaknesses, impeding targeted enhancements in models’ reasoning abilities to synthesize code.

To bridge this gap, this thesis introduces two novel contributions: CodeEval and CodeQual. CodeEval is an innovative, pedagogical benchmarking method that mirrors the evaluation processes encountered in academic programming courses. It comprises …

Uniform Stability Of Katyusha In Strongly-Convex Settings, Don Li

University Honors Theses

Acceleration of convergence and reduction of variance constitute a trade-off in the design of stochastic optimization machine learning algorithms. Katyusha was introduced to address this trade-off, synthesizing Nesterov Accelerated Gradient (NAG) and Stochastic Variance-Reduced Gradient (SVRG) into a single first-order optimizer with promising empirical performance. However, the generalization properties of Katyusha remain largely unexplored. We conjecture that, in the smooth quadratic regime (i.e., under assumptions of strong convexity and smoothness of the loss function, and boundedness of gradients), Katyusha is uniformly stable in the sense of Bousquet and Elisseeff. Instantiating our framework for NAG, we extend the use of Lyapunov …

Obstructions To Some Injective Oriented Colourings, Russell J. Campbell, Nancy E. Clarke, Gary Macgillivray

Theory & Applications of Graphs

Each of several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ leads to an injective oriented colouring problem. For each case in which such a problem is solvable in polynomial time, we identify a set $\mathcal{F}$ of oriented graphs such that an oriented graph $G$ has an injective oriented colouring with the given number of colours if and only if there is no $F \in \mathcal{F}$ for which there is a locally-injective homomorphism of $F$ to $G$.

Breadquest: Enhancing Roguelike Accessibility Through Procedural Generation And Thematic Design, Hahns Pena

Computer Science and Software Engineering

BreadQuest is a top-down roguelike dungeon crawler with a whimsical dessert theme that aims to make the genre more accessible while preserving strategic depth and replayability. Players explore procedurally generated dungeons, fight pastry-themed enemies, and collect bakery-inspired items that support a flavor-elemental combat system, with each run offering unique layouts, encounters, and rewards. Built in Unity with a modular, data-driven architecture, the game uses procedural generation techniques like Binary Space Partitioning, Voronoi diagrams, and Perlin noise to create varied and replayable levels. The project emphasizes approachable gameplay, cultural dessert inspiration, and replayability, with success evaluated through playtesting and player feedback.

Extensive And Intensive Margin Labor Supply On Ride-Sourcing Platforms, Hao Sun, Hai Wang, Zhixi Wan

Research Collection School Of Computing and Information Systems

The rapid expansion of ride-sourcing platforms has enabled freelance drivers to flexibly determine both their participation and working hours. Understanding this flexible labor supply behavior is essential for managing platform capacity and evaluating the impacts of pricing and incentive policies on driver welfare. This study develops a labor supply model in which drivers optimally choose whether to participate (extensive margin) and how long to work (intensive margin) to maximize their utility from consumption and leisure. The model incorporates heterogeneity in drivers’ other income, idle time, and participation costs, allowing us to analytically characterize equilibrium labor supply decisions. The results show …

Computational Insights Into Nucleosome Dynamics In Epigenetics Using Molecular Dynamics Simulations, Rutika Patel

Dissertations, Theses, and Capstone Projects

Nucleosome core particles (NCP) are the building blocks that form a highly organized and compact chromatin structure. Nucleosomes package DNA in the nucleus of eukaryotic cells. The NCP consists of about 147 base pairs of DNA wrapped around the histone octamer, with 1.65 superhelical turns in a left-handed manner. The histone octamer is composed of two copies of H3, H4, H2A, and H2B. Together with histone H1 and linker DNA, they further assemble into a higher-order chromatin structure. The nucleosome complex is stabilized by electrostatic interactions between positively charged histone residues and the negatively charged DNA backbone. To effectively access …

Crab: A Novel Clustering Score Using Clustering With Rivals And Buddies For Unsupervised Learning, Allen Choi

Master's Theses

Unsupervised clustering algorithms today are used across a wide variety of fields such as biology, engineering, and industry in order to classify observations into groups where labels are not provided. This can provide important latent information regarding the observations within groups, as well as insight regarding the groups themselves. In order to judge the optimal number of clusters for an unsupervised clustering algorithm, many methods exist such as the Elbow Method and Silhouette Score; however, these methods come with drawbacks and are not necessarily flexible across many unsupervised methods. We present a novel clustering score framework relying on a resampling-based …

Comparing The Sensitivity And Degree Of Boolean Functions Via The Hypercube, Anne-Caroline Rupp

University Honors Theses

This thesis studies three complexity measures of total Boolean functions f:{0,1}ⁿ → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal.

The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry …

Empirical Comparsion Of Traveling Salesperson Approximation Algorithms, Shayan Daijavad

Master's Theses

The traveling salesperson problem deals with optimizing the route a traveling sales- person might take to visit a set of places exactly once and return back to their starting point. The problem is NP-hard, and it is hard to approximate in general, but special cases have many approximation algorithms, which come with tradeoffs. In this thesis we compare the runtime, approximation ratio, and overall implementation complexity of two approximation algorithms for the Euclidean version of the problem, a classical 2-approximation algorithm and the multifragment heuristic. We run both algorithms on randomly generated point sets and real world data from TSPLIB. …

An Evaluation Of Road Network Structure As A Predictor Of Traffic Volume, Colin M. Mcdonald

Master's Theses

This thesis evaluates the relationships between various graph theory metrics and taxi traffic volume for the cities of San Francisco, California and Porto, Portugal. We also evaluate a modified betweenness centrality metric which incorporates the count of distinct origin-destination pairs from the taxi data as the weight function. This thesis extends a paper by Pengyao Ye, Bo Wu, and Wenbo Fan by reducing circularity through a temporal train-test split and by comparing both line-graph and primal-graph formulations of betweenness centrality.

We found that past traffic volume is almost perfectly correlated with future traffic volume and that the modified betweenness centrality …

Edge Co-Occurrence Regularization For Node Classification, Kadir Altunel

Theses

We propose a simple yet effective regularization technique for node classification on graphs that leverages edge-based label co-occurrence patterns. We first train an MLP on node features to produce class probability distributions, then compute a fixed penalty matrix from edge-based co-occurrence statistics of these predictions. This penalty matrix, which captures unlikely class combinations on connected nodes, is then used to regularize GNN training without further updates. We evaluate this approach across multiple homophilic datasets (Cora, CiteSeer, PubMed, ogbn-arxiv) and heterophilic benchmarks (Chameleon, Squirrel, Actor, Roman-Empire) using three GNN architectures: GCN, GraphSAGE, and H2GCN. Results show consistent improvements on homophilic graphs, …

Static Data-Race Detection For Gpu Programs: Behavioral Types With Partial Completeness Guarantees, Zhen Rong Liew

Graduate Doctoral Dissertations

GPUs are essential to modern computing but notoriously difficult to program correctly. Static analysis tools can verify data-race freedom, but their over-approximations produce spurious reports of data races that do not occur, limiting their practical usefulness. This dissertation establishes when Memory Access Protocols (MAPs), a compositional abstraction modeling memory access behavior between synchronization barriers, can be simultaneously sound and complete. We first prove that MAP-based analysis is sound and complete for well-typed Jaminan programs---those without data-dependent array indexing. This result establishes the theoretical boundary: completeness is achievable when data-dependent control flow and indexing are absent. Jaminan extends MAPs with symbolic …

Finding A Way Out Of The Filter Bubble: The Confusion Of A Heavy Social Media User, Longwen Miao

Masters Theses

This thesis studies how algorithmic recommendation systems reshape visual perception, aesthetic judgment, and the construction of selfhood within contemporary digital culture.

Everything begins with the experience of repeatedly encountering algorithmically recommended content on everyday digital platforms. On these platforms, images, sounds, and social interactions are continuously selected, repeated, and reorganized by predictive systems, forming an environment in which perception is constantly structured and adjusted.

From this observation, the research raises two central questions: how do algorithmic recommendation systems reshape visual perception, aesthetic judgment, and self-recognition, and how might these systems be intervened in or made perceptible through artistic practice? Within …

Node Differentially Private Algorithms For Survivable Networks And Graphs Analysis, Jinghua Sun

Computer Science Theses

This thesis studies two graph algorithmic settings where additional structure gives stronger guarantees than worst-case black-box methods. The paper considers higher order edge connectivity under node differential privacy. We study the minimum k-edge-connected spanning subgraph problem (k-ECSS) and the minimum k-edge-connected component problem (k-ECC). These objectives have large global sensitivity under node privacy, since adding or deleting one vertex and its incident edges can significantly change robust connectivity structure. To address this, we use Propose-Test-Release for locally stable k-ECC instances and a Lipschitz extension framework for k-ECSS, based on bounded-degree complement objectives and the Generalized Exponential Mechanism.

The second part …

Computing Certificates Of Members In Archimedean Quadratic Modules In A[X] And Certifying The Emptiness In Inconsistent Monogenic Archimedean Quadratic Modules In A[X_1, ..., X_N], Jose A. Castellanos Joo

Computer Science ETDs

Polynomials have been found to be a powerful tool over hundreds of years for modeling problems in numerous applications in science, engineering, medicine, and other domains. In the context of formal methods, polynomials arise in modeling in aerospace software and robotics, cyber-physical and hybrid systems, autonomous vehicles and controllers based on neural networks.

A quadratic module is a linear combination of polynomials in a set of generators (including the constant 1) with sum of squares polynomials as multipliers. The membership problem for a finitely generated quadratic module can be decided; however, computing a certificate exhibiting why it is nonnegative under …

Uncovering The Impact Of Youtube's Hidden Algorithm On Its Users, Oscar Perez

COD Library Student Research and Award Symposium

YouTube is a well-known platform that offers users endless hours of news, entertainment, and education. This research seeks to understand how the algorithm functions and uncover the effects of allowing a system to curate content for viewers. The research combines academic sources with fieldwork to understand the impact of YouTube's algorithm.

Faculty Sponsor:  Professor Jacqueline McGrath

Largest 2-Regular Subgraphs In Complete S-Partite Graphs, Yiyang Jiang

McKelvey School of Engineering Graduate Student Theses & Dissertations

In this thesis, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in studying largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. …

Search For Slow-Moving Magnetic Monopoles With An Improved High-Energy Event Removal Algorithm, Reeshi N. Gihosal

Honors Theses

Fermilab’s NOvA (NuMI Off-axis 𝑣𝑒 Appearance) experiment focuses on understanding the behavior of neutrinos and how they affect the cosmos. A sub-focus of the NOvA experiment is the search for magnetic monopoles. These elusive particles have not yet been observed in nature, leaving their behavior to be mysterious. The Far Detector, located in Ash River, MN, is integral in the search for these particles. This project is on simulated magnetic monopoles with speeds thousandths the speed of light, with focus on the role of slicing algorithms in event reconstruction using the NOvA experiment’s reconstruction algorithm. Using sample data, analysis occurred …