Theory and Algorithms Commons^™

Federated Boolean Matrix Factorization Using Integer Programming, Quynh Anh Nguyen, Ngoc Nguyen, Nhat Phan

Research from the Berry Summer Thesis Institute, 2025

Identifying the underlying structural patterns in data and extracting meaningful insights is a key challenge in data analysis. One effective approach to this problem is matrix factorization (MF), which approximates large matrices with lower-dimensional representations, making it effective for uncovering hidden patterns. MF techniques are widely applicable across various domains, such as recommender systems, cancer genomics, system identification, clustering, and image processing. Despite their effectiveness, existing MF methods often struggle with computational constraints and convergence challenges when tackling large-scale, nonsmooth, and nonconvex optimization problems, which are common in real-world applications.

This project aims to explore both the theoretical understanding and …

Optimal Hypergraph Connectivity With Cut Queries, Hang Liao

Dartmouth College Ph.D Dissertations

Finding connected components in undirected hypergraphs—hypergraph connectivity—is a fundamental problem in computer science. It can be framed as a special case of Symmetric Submodular Function Minimization (SSFM), where the objective is to determine if the non-trivial minimizer is zero. This thesis develops an optimal algorithm for hypergraph connectivity within the $\CUT$ query model, where an algorithm probes a subset of vertices to learn the weight of the hyperedges ``cut" by that partition.

Our approach is constructive, culminating in an optimal algorithm for the general problem by first developing the necessary tools for two foundational subproblems. The main contributions of this …

L3net: Localized And Layered Reparameterization For Incremental Learning, Xuandi Luo, Huaidong Zhang, Yi Xie, Hongrui Zhang, Xuemiao Xu, Shengfeng He

Research Collection School Of Computing and Information Systems

Model-based class incremental learning (CIL) methods aim to address the challenge of catastrophic forgetting by retaining certain parameters and expanding the model architecture. However, retaining too many parameters can lead to an overly complex model, increasing inference overhead. Additionally, compressing these parameters to reduce the model size can result in performance degradation. To tackle these challenges, we propose a novel three-stage CIL framework called Localized and Layered Reparameterization for Incremental Learning (L3Net). The rationale behind our approach is to balance model complexity and performance by selectively expanding and optimizing critical components. Specifically, the framework introduces a Localized Dual-path Expansion structure, …

Solving Two-Stage Stochastic Integer Programs Via Representation Learning, Yaoxin Wu, Zhiguang Cao, Wen Song, Yingqian Zhang

Research Collection School Of Computing and Information Systems

Solving stochastic integer programs (SIPs) is extremely intractable due to the high computational complexity. To solve two-stage SIPs efficiently, we propose a conditional variational autoencoder (CVAE) for scenario representation learning. A graph convolutional network (GCN) based VAE embeds scenarios into a low-dimensional latent space, conditioned on the deterministic context of each instance. With the latent representations of stochastic scenarios, we perform two auxiliary tasks: objective prediction and scenario contrast, which predict scenario objective values and the similarities between them, respectively. These tasks further integrate objective information into the representations through gradient backpropagation. Experiments show that the learned scenario representations can …

Non-Homophilic Graph Pre-Training And Prompt Learning, Xingtong Yu, Jie Zhang, Yuan Fang, Renhe Jiang

Research Collection School Of Computing and Information Systems

Graphs are ubiquitous for modeling complex relationships between objects across various fields. Graph neural networks (GNNs) have become a mainstream technique for graph-based applications, but their performance heavily relies on abundant labeled data. To reduce labeling requirement, pre-training and prompt learning has become a popular alternative. However, most existing prompt methods do not distinguish between homophilic and heterophilic characteristics in graphs. In particular, many real-world graphs are non-homophilic-neither strictly nor uniformly homophilic-as they exhibit varying homophilic and heterophilic patterns across graphs and nodes. In this paper, we propose ProNoG, a novel pre-training and prompt learning framework for such non-homophilic graphs. …

Three Essays In The Economics Of Disagreements: Incentives, Measurement And Persistence, Mustafa W. Alam

All Dissertations

This dissertation presents three chapters that contribute to the study of economic forces shaping disagreements in society.

In Chapter 1, I demonstrate that political polarization can intensify due to innovations in the information market even if a population's ideological distribution is fixed. Viewership-maximizing news firms cater to a diverse audience who assess source accuracy using noisy private signals that vary in precision and ideological bias. If better-informed consumers disproportionately migrate to newer platforms for news (e.g., the Internet), traditional media firms increase news slant to appeal more to less-informed partisans on both sides of the ideological spectrum. This leads to …

Optimizing Group Utility In Itinerary Planning: A Strategic And Crowd-Aware Approach, Junhua Liu, Aldy Gunawan, Kristin L. Wood, Kwan Hui Lim

Research Collection School Of Computing and Information Systems

Itinerary recommendation is a complex sequence prediction problem with numerous practical applications. The task becomes significantly more challenging when optimizing multiple factors simultaneously, such as user queuing times, crowd levels, attraction popularity, walking durations, and operating hours. These factors, combined with the dynamic and unpredictable nature of visitor flow, introduce substantial complexities, particularly when accounting for collective user behavior. Existing solutions often adopt a single-user perspective, overlooking critical challenges arising from natural crowd dynamics. For example, the Selfish Routing problem illustrates how individual decision-making can lead to suboptimal outcomes for the group as a whole. To address these challenges, we …

Advancing Real-World Implementation Of The Well Optimized Linear Finder (Wolf) High-Speed Atmospheric Turbulence Compensation Method, Timothy Evan Coon

Theses and Dissertations

This dissertation advances the real-world implementation of the Well Optimized Linear Finder (WOLF) method for high-speed Atmospheric Turbulence Compensation (ATC). Atmospheric turbulence introduces phase aberrations into optical wavefronts and degrades image quality in terrestrial imaging systems. Traditional phase diversity methods are computationally intensive and poorly suited to real-time operation. The WOLF method addresses these limitations through a novel, point-wise formulation of the optical transfer function (OTF) as a structured autocorrelation of the generalized pupil function (GPF). This formulation enables the estimation of phase aberrations at individual spatial coordinates with distributed computational complexity.

The research begins by developing a MATLAB-based simulation …

Algebraic Multigrid Methods For Nonsymmetric And Indefinite Problems: Theory And Applications, Ahsan Ali

Mathematics & Statistics ETDs

Algebraic multigrid (AMG) is a well-established and highly efficient solver for symmetric positive definite (SPD) systems arising from elliptic and parabolic PDEs, while nonsymmetric systems from hyperbolic PDEs remain a significant challenge. This dissertation develops AMG methods and theory for nonsymmetric problems. First, we develop a novel approach combining mode constraints from energy-minimization AMG with local approximations of ideal restriction in $\ell$AIR, resulting in constrained $\ell$AIR (C$\ell$AIR), which demonstrates scalable convergence across advective and diffusive problems. Second, we extend optimal AMG theory by deriving spectral radius estimates for the two-grid error transfer operator using matrix-induced orthogonality, enabling convergence predictions for …

Pure And Strong Nash Equilibrium Computation In Compactly Representable Aggregate Games, Jared Soundy, Mohammad T. Irfan, Hau Chan

Research & Publications

Aggregate games model interdependent decision making when an agent’s utility depends on their own choice and the aggregation of everyone's choices. We define a compactly representable subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We study computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE). We show that PNE existence is NP-complete for very simple cases of additive aggregate games. We devise an efficient algorithmic scheme for deciding the existence of a PNE and computing one (if it exists) for bounded aggregate space. …

Syntax-Enhanced Boundary-Aware Named Entity Recognition Model, Chuanming Yu, Bin Deng, Zhengang Zhang

Journal of Scientific Information Research

[Purpose/significance] This study addresses the issue of inadequate perception of entity boundaries in traditional character-level modeling-based named entity recognition models by integrating syntax information containing entity boundary features into the task using a multi-head graph attention network with dense connections. This integration enhances the effectiveness of named entity recognition.

[Method/process] This study proposes a Syntax-enhanced Boundary-aware Named Entity Recognition Model (SynBNER), which utilizes BERT for text semantic representation and integrates syntax information using a dense-connected graph attention network. This integration incorporates implicit entity boundary information from syntax information into word representations, thereby enhancing the model's entity boundary perception capability.

[Result/conclusion] …

Multi-Label Classification Of Acoustic And Electronic Drum Sounds Using Machine Learning, Sean Perman

Electronic Theses and Dissertations

This paper presents a system for multi-class classification of drum sounds using audio signal processing and machine learning techniques. The project utilizes a diverse dataset of both acoustic and electronic drum samples and extracts ten distinct audio features to capture the timbral and temporal characteristics of each sound. The methodology includes signal preprocessing, feature extraction, and the application of supervised classification algorithms to distinguish between multiple drum classes. Experimental evaluations demonstrate that the selected features significantly enhance classification accuracy across a varied dataset. These findings underscore the effectiveness of combining traditional audio processing with modern machine learning, offering promising applications …

Optimizing Option Market Clearing, Juan Andrés Malaver Alvarado

Electronic Theses and Dissertations

Modern options markets clear each strike in isolation, leaving cross-strike arbitrage unexploited. This thesis applies a payoff-dominant clearing mechanism to realized trades—roughly 2 000 Cboe VIX option executions from June–November 2016—after classifying each trade’s side and bundling by expiration. Three optimization formulations are tested: a fractional linear program (LP), a mixed-integer LP, and a pure integer program. On a 10-core laptop every bundle solves in < 0.5 s. The LP captures the greatest surplus, yet the integer models recover nearly as much while filling whole contracts and holding only modest margin. Results reveal persistent, albeit small, inefficiencies in executed trades and demonstrate that an integral cross-strike auction could operate in real time. The accompanying C/Gurobi code is modular and readily extendable to early-exercise options. Trade-level evidence thus supports redesigning exchange clearing to consider the complete option book.

A Steiner Tree Vc Set System In Minor-Free (Di)Graphs, Eli Friedman

Computer Science Senior Theses

We propose a set system of maximum-covering minimum-density partial Steiner trees for planar and minor-free graphs. We show that this system has VC dimension at most h-1 for edge-weighted K_h-minor-free graphs, both directed and undirected. We also consider its geometric interpretation as a range space, proving it to be piercing.

In addition, we demonstrate how one can form a junction tree set system of bounded VC dimension from such Steiner trees. This is motivated by refining the junction tree set cover approach used in Chekuri and Jain's polylogarithmic approximation algorithm for Directed Steiner Forest in planar graphs [CJ25].

A Multimodal Fusion Model Leveraging Mlp Mixer And Handcrafted Features-Based Deep Learning Networks For Facial Palsy Detection, Heng Yim Nicole Oo, Min Hun Lee, Jeong Hoon Lim

Research Collection School Of Computing and Information Systems

Algorithmic detection of facial palsy offers the potential to improve current practices, which usually involve labor-intensive and subjective assessments by clinicians. In this paper, we present a multimodal fusion-based deep learning model that utilizes an MLP mixer-based model to process unstructured data (i.e. RGB images or images with facial line segments) and a feed-forward neural network to process structured data (i.e. facial landmark coordinates, features of facial expressions, or handcrafted features) for detecting facial palsy. We then contribute to a study to analyze the effect of different data modalities and the benefits of a multimodal fusion-based approach using videos of …

Filling Gaps In Scientific Data Sets Using Physics Informed Neural Networks: A Case Study In Velocity Fields, Ellen Saunders

Master's Theses

Gaps in scientific data sets are a persistent issue for researchers in a variety of fields, and while nothing makes up for missing out on real data, well-simulated synthetic data can be a useful tool. In the world of image processing, machine learning techniques have become quite sophisticated at taking an image with a missing component and filling in that space with something believable. The aim of this thesis is to take machine learning techniques similar to what gets used in image processing and repurpose them to infill gaps in scientific data sets in a realistic manner. This thesis compares …

Ef21 With Bells & Whistles: Six Algorithmic Extensions Of Modern Error Feedback, Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, Peter Richtarik

Research Collection School Of Computing and Information Systems

First proposed by Seide (2014) as a heuristic, error feedback (EF) is a very popular mechanism for enforcing convergence of distributed gradient-based optimization methods enhanced with communication compression strategies based on the application of contractive compression operators. However, existing theory of EF relies on very strong assumptions (e.g., bounded gradients), and provides pessimistic convergence rates (e.g., while the best known rate for EF in the smooth nonconvex regime, and when full gradients are compressed, is O(1/T2/3), the rate of gradient descent in the same regime is O(1/T)). Recently, Richtàrik et al. (2021) proposed a new error feedback mechanism, EF21, based …

Topodino: Self-Supervised Topological Representation Learning For Neuronal Morphologies, Yasser Binbisher

Master's Theses

Neuronal cell types are categorized by transcriptomic identity, yet their morphological heterogeneity defies this classification. In response, researchers have adopted unsupervised graph representation learning as a tool to reveal morphological variation within single-class transcriptomic types. However, the complex geometry of neuronal morphology—especially long axons and dense dendrites—challenges graph neural networks, which struggle with message propagation across extended structures. To mitigate this, current approaches enforce sub-sampling on neuronal graphs and omit axons entirely, sacrificing critical biological features for computational efficiency. To overcome this trade-off, this thesis introduces TopoDINO, a self-supervised, topology-aware representation learning model designed to preserve the full hierarchical organization …

An Exposition Of "Probabilistic Polynomials And Hamming Nearest Neighbors", Vivek Srirama

University Honors Theses

This paper is an exposition of the paper Probabilistic Polynomials and Hamming Nearest Neighbors by Josh Alman and Ryan Williams. It presents the findings of this paper in a more accessible format for Computer Science students earlier in their career who may not be as familiar with Computational Theory and its concepts as their PhD counterparts are. The paper assumes that the reader has a basic understanding of Algorithms and Complexity, typically obtained in an introductory level Algorithms course.

The paper by Alman and Williams analyzes a specific problem known as the Hamming Nearest Neighbor problem. All known solutions for …

Less Is More: On The Importance Of Data Quality For Unit Test Generation, Junwei Zhang, Xing Hu, Shan Gao, Xin Xia, David Lo, Shanping Li

Research Collection School Of Computing and Information Systems

Unit testing is crucial for software development and maintenance. Effective unit testing ensures and improves software quality, but writing unit tests is time-consuming and labor-intensive. Recent studies have proposed deep learning (DL) techniques or large language models (LLMs) to automate unit test generation. These models are usually trained or fine-tuned on large-scale datasets. Despite growing awareness of the importance of data quality, there has been limited research on the quality of datasets used for test generation. To bridge this gap, we systematically examine the impact of noise on the performance of learning-based test generation models. We first apply the open …