Combinatorics and Algorithms for Real Problems

THIS IS UNDER CONSTRUCTION. DO NOT READ- IT WILL CHANGE

Projects are listed by Type:

Algorithms, Machine Learning-AI, Cryptography/Security, Programming Language

ALGORITHM PROJECTS

TITLE: PHYLOGENIES, ERRORS, AND ALGORITHMS, oh my!

MENTOR: Erin Molloy

Prerequisites

(1) Familiarity with discrete math, algorithms, probability, and machine learning,

(2) Proficiency in at least one programming language (ideally Python or C++),

(3) Knowledge of command line (UNIX)

Description

Evolutionary relationships (e.g., among different species or cells in a tumor) are important for many biological studies. However, evolution cannot be directly observed in most practical applications and thus must be reconstructed from genomic data (DNA). Reconstruction often involves complex computational pipelines, with errors from earlier steps in the pipeline propagating downstream and even impacting the accuracy of the reconstructed evolutionary tree, called a phylogeny.

This project will broadly focus on the issue of error propagation and phylogeny reconstruction from an algorithmic perspective. Specific projects could entail (1) quantifying the theoretical and/or practical impact of errors on combinatorial algorithms for evolutionary tree reconstruction, (2) developing phylogeny reconstruction algorithms that are more robust to erroneous or uncertain inputs, or (3) developing machine learning algorithms for improved error or uncertainty detection and evaluating their utility for phylogeny reconstruction.

ML AND AI PROJECTS

TITLE: AI FOR SOCIAL GOOD

MENTORS: Ming Lin and Grace Cai

Prerequisites At least one course in AI, ML, Robotics, Computer Vision and/or Computer Graphics.

Description

We will design artificial intelligence (AI) and machine learning (ML) algorithms and realize their implementation to address various health, environmental, engineering, education, and other social-technical challenges for enhancing safety, wellness, and equity for all people across diverse communities. Some possible topic areas may include mixed traffic simulation, water monitoring, food quality assessment, Robotics, Physical AI, manufacturing, AI-human dynamics & teaming, and computational finance.

TITLE: BRAIN-INSPIRED AI FOR ANALYZING DNA IN THE FIELD

MENTOR: Can Firtina

Prerequisites

Being comfortable with Python (or AI coding tools such as Claude Code) and having some exposure to machine learning (e.g., PyTorch). Some background in algorithms, signal processing, or computer architecture is helpful, though no prior background in biology, genomics, or spiking neural networks is required. Students can lean toward the machine learning and algorithmic side (designing and training models), the systems and hardware-simulation side (modeling energy efficiency and hardware constraints), or both.

Description

Modern pocket-sized nanopore sequencers can read DNA and RNA molecules outside traditional laboratories, from infectious-disease outbreak sites and rural clinics to agricultural fields and even aboard the International Space Station. As a single DNA strand passes through a microscopic pore, the device measures tiny fluctuations in electrical current, producing a noisy time-series stream of raw signals. To turn those raw electrical signals into useful biological answers, today's pipelines rely on large deep neural networks (DNNs). These models often require power-hungry GPUs that draw substantially more power than the handheld sequencer itself. Making portable genome analysis truly practical in the field requires energy-efficient solutions that co-design algorithms and hardware together to maximize energy gains without sacrificing accuracy.

One path forward is to replace traditional dense neural networks with spiking neural networks (SNNs), a brain-inspired class of AI models designed for ultra-low-power neuromorphic hardware. Instead of running heavy matrix multiplications on every signal sample at a fixed clock rate, SNNs communicate through sparse, binary events called spikes and expend energy only when the incoming signal meaningfully changes.

In this project, students will explore how to design accurate, energy-efficient SNNs for real-time genome analysis. All students will begin with a shared foundation where they learn how to process and analyze raw nanopore genomic data from publicly available benchmark datasets, study how traditional DNN pipelines solve these tasks, and convert dense DNN architectures into SNNs using modern PyTorch-based frameworks (such as snnTorch). Building on this common foundation, each student project will focus on a distinct genomic application or use case, ch as basecalling (translating raw electrical signals into DNA letters), real-time adaptive sampling (deciding within milliseconds whether to keep or eject a DNA strand from a pore), or direct raw-signal pathogen detection.

TITLE: MATHEMATICAL FOUNDATIONS OF AI EVALUATION

MENTOR: Han Shao

Prerequisites

1) Must be a junior or senior (recall that we can take seniors if they will still be an undergraduate in Fall 2027).

2) A strong math background

3) Some knowledge of Algorithms and Complexity Theory.

4) Some knowledge of AI.

Description

How can we reliably evaluate and compare AI models using limited data? This project studies the mathematical foundations of AI evaluation from a statistical learning perspective. We will formulate concrete evaluation objectives, such as comparing model performance or estimating failure probabilities, and investigate what data and algorithms are needed to achieve them.

Possible sources of information include model outputs, benchmark examples, and human preferences. Theoretical questions include when reliable evaluation is possible, how many samples or model queries it requires, and whether computationally efficient methods exist.

The emphasis will be on designing evaluation methods with provable guarantees and understanding their fundamental limitations, rather than implementing a benchmark alone.

Cryptography and Security

TITLE: Efficient Privacy-Preserving Machine Learning on Encrypted Data

MENTOR: Dana Dachman-Soled

Prerequisites Python, C++, Linear Algebra, Calculus, Algorithms. Familiarity with C++ and Machine Learning is helpful but no required background in cryptography is needed.

Description Machine learning (ML) has become an essential tool in applications ranging from healthcare to finance. However, training ML models often requires access to sensitive data, raising significant privacy concerns. How can we train ML models while protecting the privacy of individuals whose information is used?

One promising approach is fully homomorphic encryption (FHE), a cryptographic technique that allows computations to be performed directly on encrypted data. However, FHE alone does not prevent the resulting model from revealing sensitive information about its training data. To address this concern, FHE can be combined with differential privacy (DP), a mathematical framework that provides rigorous privacy guarantees.

Unfortunately, standard ML training algorithms are computationally expensive to implement under FHE, particularly when combined with DP. In recent work, our research group has developed new techniques for efficient privacy-preserving ML training using polynomial approximations and specialized optimization algorithms.

In this project, students will explore ways to improve the efficiency of privacy-preserving ML training. Students will implement and experiment with different algorithms, studying their effects on model accuracy, convergence, privacy, and computational cost. Depending on their interests and backgrounds, students may also investigate theoretical questions related to these algorithms.

TITLE: Can we Do Private Inference Without Cryptography? (Of this and the next project, only one will be offered.)

MENTOR: Gabe Kaptchuk

Prerequisites: Comfort with Python, some exposure to machine learning (e.g., PyTorch), and some exposure to either cryptography or computer security. Students can lean toward the experimental side (building and attacking systems), the theoretical side (definitions and proofs), or both.

Description

People increasingly send sensitive data to large AI models running in the cloud: proprietary source code, medical notes, legal documents. Cryptography offers strong ways to protect that data while it is being processed, such as homomorphic encryption and secure multiparty computation. These tools come with a steep concrete price, though, often making computation hundreds or thousands of times slower. That cost has led to a wave of lighter-weight proposals. Instead of encrypting the data, they scramble, perturb, or add noise to it before handing it to the server, and they promise privacy while the server runs the model at full speed.

These ad-hoc approaches are attractive, but history suggests they are error-prone. Several earlier schemes in this space have been broken soon after publication, often by attacks that used nothing more than the information the server was already allowed to see. This raises a basic question: are the failures just bugs in particular designs, or is there a fundamental limit on what non-cryptographic techniques can achieve?

In this project, students will study existing proposals for privacy-preserving machine learning inference. They will re-implement representative schemes, design attacks against them, and measure how they break down in practice. Building on what we learn, we will work toward formal definitions and proofs that characterize what is and is not possible without cryptographic machinery. The goal is to give clear guidance on when lightweight protections can be trusted and when they cannot.

TITLE: PRIVATE SET INTERSECTION WITH RECEIPTS (Of this and the previous project only one will be offered.)

MENTOR: Gabe Kaptchuk

Prerequisites Algorithms, comfort with modular arithmetic and proofs, programming in Python or Rust. Prior exposure to cryptography is a plus but not required cryptography needed.

Description

Private set intersection (PSI) lets two parties, each holding a list, learn which items appear on both and nothing else; a bank can check its customers against a sanctions list without either side revealing its list. PSI is fast and deployed today, but when the protocol ends the party that gets the answer has no way to prove it to anyone. The bank cannot show a regulator that it screened a customer and found no match without exposing the list or the customer.

This project asks for PSI with receipts: a short certificate that convinces a third party that a given item was in the receiver’s input and was, or was not, in the other party’s set, checkable in time independent of the set sizes and revealing nothing else. The fastest PSI protocols are built from symmetric-key techniques whose outputs only the two participants can check, so something has to be added. The challenge is a framework that says what that something is, how to attach it to existing protocols, and what it costs. Students will implement a few PSI protocols, read the literature on PSI with committed inputs, and then work on definitions, constructions, and prototypes.

PROGRAMMING LANGUAGES PROJECTS

TITLE: VERIFIED DATAFLOW COMPILATION

MENTOR: Milijana Surbatovich

Prerequisites

(1) facility with more than one programming language (preferably one of them being Rust or OCaml)

(2) at least one course touching on low-level systems (comp organization, comp architecture, etc.)

(3) a course in prog languages (compilers, principles of programming, PL design, etc.)

(4) familiarity with proofs (could be from math, PL, symbolic logic, etc.)

Description

Dataflow execution is a computational model in which operations execute as soon as their input data becomes available, rather than according to some centralized control (like a program counter). This execution model can greatly improve efficiency and performance of applications, hence the model is seeing a lot of interest.

One way to realize this execution model is to take an existing program, compile it with a dataflow compiler that translates the program into a dataflow graph (operators as nodes, data dependencies as edges), and then map this graph directly onto some programmable, parallel hardware platform.

Unfortunately, this compilation flow is difficult to implement correctly and effectively, as existing programming languages lack good abstractions for dataflow features. For example, translating from a language originally meant for sequential execution into a highly-parallel dataflow graph easily introduces data races and deadlocks, or sacrifices potential parallelism.

This project broadly looks at developing verified (i.e., with a mathematical proof of correctness), efficient dataflow compilers, with multiple directions possible. Specific projects could include

a) experiment-driven exploration of how well existing parallel programming frameworks can compile to dataflow representations,

b) designing new type systems or compiler intermediate representations to enforce key properties by construction, or

c) more theoretical directions such as defining formal semantics or memory models.

With all three potential projects students will learn concepts of dataflow execution, type system design, and system verification.