Theory and Algorithms Commons^™

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

Specialization Or Diversification? Creators’ Strategies On User-Generated Content Platforms, Ziwei Ye

Theses and Dissertations in Business Administration

Recent advancements in digital platforms have reshaped content creation and distribution. User-generated content (UGC), created and shared by internet users, is transforming entertainment, communication, and information sharing. The rise of UGC has fueled the growth of the "creator economy"—an ecosystem of creators, users, and advertisers facilitated by platforms such as YouTube and TikTok. While prior research has primarily explored how UGC platforms incentivize content quantity and quality, this study advances the literature by examining how creators' content strategies influence consumer attention and how platform mechanisms shape this relationship, offering new insights into the interplay between creator behavior and platform design. …

Property Testing Ai: An Efficient Frontier, Paul Sopher Lintilhac

Dartmouth College Ph.D Dissertations

In this dissertation, we take a step towards addressing the major problem of a lack of standardized and rigorous approaches to testing and evaluation of AI systems. Taking inspiration from both the fields of Property Testing and Property Based Testing (for programs), we develop a novel taxonomy of partially overlapping classes of properties of AI systems, including simple properties, compound properties, higher order properties, data relation properties, and architecture-utility properties. We argue that this taxonomy categorizes a diverse set of AI traits -- including accuracy, fairness, robustness, monotonicity, point-wise and global privacy properties, sensitivity, and more -- according to the …

Adapting Large Language Models For Parameter-Efficient Log Anomaly Detection, Ying Fu Lim, Jiawen Zhu, Guansong Pang

Research Collection School Of Computing and Information Systems

Log Anomaly Detection (LAD) seeks to identify atypical patterns in log data that are crucial to assessing the security and condition of systems. Although Large Language Models (LLMs) have shown tremendous success in various fields, the use of LLMs in enabling the detection of log anomalies is largely unexplored. This work aims to fill this gap. Due to the prohibitive costs involved in fully fine-tuning LLMs,we explore the use of parameter-efficient fine-tuning techniques (PEFTs) for adapting LLMs to LAD.To have an in-depth exploration of the potential of LLM-driven LAD, we present a comprehensive investigation of leveraging two of the most …

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 …

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 …

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 …

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 …

Outperforming The Best With Minimal Effort: Algorithm Selection For Constrained Multi-Objective Optimization, Mustafa Misir, Aldy Gunawan

Research Collection School Of Computing and Information Systems

The present study performs algorithm selection on a suite of optimization algorithms targeting the constrained multi-objective optimization problems. The idea is to utilize the existing, relevant algorithmic experience in the literature to deliver an improved solver with limited effort. The reason being that algorithm development, in general, is a challenging and time-consuming process, especially with the goal of outperforming the existing methods from varying perspectives such as performance, speed, and robustness. Concerning the multi-objective optimization problems, the required development efforts happen to be even harder than addressing the single-objective ones. Furthermore, referring to the fact that the number of candidate …

Dupin: A Parallel Framework For Densest Subgraph Discovery In Fraud Detection On Massive Graphs, Jiaxin Jiang, Siyuan Yao, Yuchen Li, Qiange Wang, Bingsheng He, Min Chen

Research Collection School Of Computing and Information Systems

Detecting fraudulent activities in financial and e-commerce transaction networks is crucial. One effective method for this is Densest Subgraph Discovery (DSD). However, deploying DSD methods in production systems faces substantial scalability challenges due to the predominantly sequential nature of existing methods, which impedes their ability to handle large-scale transaction networks and results in significant detection delays. To address these challenges, we introduce Dupin, a novel parallel processing framework designed for efficient DSD processing in billion-scale graphs. Dupin is powered by a processing engine that exploits the unique properties of the peeling process, with theoretical guarantees on detection quality and efficiency. …

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 …

Community Detection In Heterogeneous Information Networks Without Materialization, Jiaxin Jiang, Siyuan Yao, Yuhang Chen, Bingsheng He, Yudong Niu, Yuchen Li, Shixuan Sun, Yongchao Liu

Research Collection School Of Computing and Information Systems

Community detection in heterogeneous information networks (HINs) poses significant challenges due to the diversity of entity types and the complexity of their interrelations. While traditional algorithms may perform adequately in some scenarios, many struggle with the high memory usage and computational demands of large-scale HINs. To address these challenges, we introduce a novel framework, SCAR, which efficiently uncovers community structures in HINs without requiring network materialization. SCAR leverages insights from meta-paths to interpret multi-relational data through compact vertex-based sketches, significantly reducing computational overhead and materialization overhead. We propose a sketch-based technique for estimating changes in modularity, improving both the precision …

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 …

On The Design Of A Framework For Large-Scale Exploratory Graph Analytics, Oliver Andres Alvarado Rodriguez

Dissertations

Large-scale exploratory graph analytics merges data science with high-performance computing to extract critical insights from network-representable data. Data scientists routinely analyze data from the natural, social, and computing sciences by representing it as networks, or graphs, where objects become vertices and their relationships become edges. This representation allows data scientists to add graph analytics to their toolbox. However, designing tools for large-scale exploratory graph analytics is challenging due to the complexities of graph algorithms, such as high communication in distributed systems and large memory demands. These challenges can lead to overly complex software, which limits usability and development to a …

Tree Story, Jia Hu

Masters Theses

What is Nature?

Nature is a system of intelligence. It means designing for efficiency—often by learning from strategies that have evolved over time. In my research, I use patterns to interpret and decode nature.

To explore nature, I began with the red cedar tree, aiming to simulate and predict its growth patterns—forms shaped by both internal biology and external forces. By analyzing its geometry, I sought to understand how trees embody the dynamic relationship between organism and environment. These patterns reveal the adaptive logic of life.

Patterns are central to understanding nature. While tree geometry may appear chaotic, it follows …

Towards Practical And Real-Time Decoding Of Quantum Hypergraph Codes, Binghong (Leo) Li

Computer Science Theses

Quantum error correction (QEC) enables scalable quantum computation by detecting and correcting physical errors. However, decoding remains a key bottleneck—particularly for quantum low-density parity-check (qLDPC) codes, whose hypergraph structures demand complex reasoning. Most existing decoders are either too slow for real-time use or lack formal guarantees, and often struggle to generalize across diverse quantum hardware.

This thesis introduces the Minimum-Weight Parity Factor (MWPF) algorithm, a unified and certifiable decoding formulation that extends minimum-weight perfect matching to general hypergraph-based stabilizer codes. We focus on making MWPF practical and performant through a two-phase decoding architecture, consisting of a fast search phase and …

Data Encoding, Compilation, And Algorithms For Quantum Machine Learning, Aviraj Sinha

Computer Science and Engineering Theses and Dissertations

Quantum computing enables new approaches to data processing, especially in quantum machine learning. Unlike classical systems, quantum data must be synthesized through operations and can exist in superposition. Encoding choices affect efficiency, noise resilience, and trainability—key factors in quantum machine learning models. This dissertation enhances quantum data encodings by extending quantum read-only memory (QROM) beyond binary representations, improving efficiency and parallelism. It introduces new compilation methods for quantum random number generators (QRNGs), supporting non-parametric distributions for post-quantum cryptography. Additionally, it explores Cayley graph-based encodings to extract spectral features for quantum machine learning.

Noise-Embedded Image Processing Based On Quantum Data Encodings, Yayu Mo

Multidisciplinary Studies Theses and Dissertations

Advancements in quantum information have significantly impacted the field of image processing, although challenges remain. Especially in the edge detection and image encoding area, distorted feature and noises would affect the further classification or super resolution tasks. In our work, we conduct researches on two stages to both evaluate the potential of Quantum-based Convolutional Structure in extracting distorted feature and further explore the effects of quantum noise channels on quantum image encodings.

In the first stage, we propose a method to extract distorted edge features by applying shallow layers in quantum convolutional neural networks (QCNN). By combining the advantages of …

Algorithms To Estimate Contours: Two Applications Of Analytical Tools In Differential Geometry And Topology, Mohammad Abirul Islam

Computer Science ETDs

We develop distributed robotics algorithms with analytical tools needed to define and analyze angle turned and distance traversed by robots executing geometric algorithms. We then use these analytical tools to obtain information, via sensor measurements, about an a priori unknown surface. Our contributions are threefold. First, we develop the Sketch Algorithm, which estimates the boundary of any unknown contour and is asymptotically optimal in terms of distance traversed and angle turned. Second, we present experimental field work that validates the Sketch Algorithm. Finally, we propose an approach to find multiple sources of a surface with potential applications to approximate that …