Combinatorics and Algorithms for Real Problems


List of Projects

TITLE: Verification of Quantum Simulation

Andrew Childs, Dhurv Devulapalli, Alexy Gorshokov

Prerequisites A first course in quantum computing or quantum mechanics. Linear Algebra and Matematical Maturity.


Quantum computers can be used to solve tasks that are beyond the reach of classical computers. The difficulty of solving these tasks classically often presents a natural challenge: how do we efficiently verify that the output of quantum computers is correct using only classical devices? Recent work has made significant progress on this problem, providing classical strategies for guaranteeing that quantum computers are performing the desired computations.

A promising application of quantum devices is the simulation of quantum systems. These systems can be simulated either with digital quantum computers or with analog quantum simulators. Analog quantum simulators are weaker than universal quantum computers, but still capable of answering questions that are beyond the reach of classical computers. In this project, we aim to provide new classical and quantum strategies for verifying that the output of a digital or analog simulator agrees well with the ideal output.

TITLE Concrete Security Estimation for Post-Quantum Cryptosystems with Side Information

Dana Dachman-Soled


Prerequisite Python, Discrete Math, Algorithms, Linear Algebra. Knowledge of quantum computing is NOT needed for this project.


Most current cryptosystems depend on factoring (or other problems in Number Theory) being Difficult. Quantum computers pose a potential threat to the security of these systems since these problems are all Easy for quantum computers. There is an ongoing effort by NIST to standardize a suite of so-called “post-quantum” cryptographic systems that will remain secure in the presence of a quantum computer.

One of the foremost avenues for efficient, post-quantum cryptosystems, is to construct cryptosystems from “lattice problems,” a type of mathematical problem that is believed to be hard even for quantum computers. It is important to research the best algorithms for breaking cryptosystems in order to inform the setting of concrete parameters for standardized cryptosystems. These parameters must be set so that the security of the resulting cryptosystems cannot be compromised, even by bad actors with very large amounts of computational resources.

What if the attacker has side information such as how much power the system is using? In a recent work, we have developed a publicly available toolkit that provides estimates for the concrete security of lattice-based cryptosystems when side information is incorporated. The toolkit allows one to determine the quantitative impact of the side information on the concrete hardness of the cryptosystem.

In this project, students will experiment with the Toolkit to analyze the effects of side-channel attacks on lattice-based cryptosystems, using publicly available datasets. The students will gain experience in programming in Sage/Python and will learn about the state-of-the-art algorithms for solving lattice problems. Students may also participate in Dachman-Soled's group's current effort to extend and improve the Toolkit.

TITLE Differentiable Economics

John Dickerson, Ian Miers

Prerequisite Some knowledge of Machine Learning.

(This will likely split into two projects. One of them will also need a knowledge of cryptograph.)

How do we allocate food to food banks, children to schools, organs to patients, residents to hospitals, security forces to patrol routes, and credit to multiple authors of an open source project—all in the face of competing incentives affecting selfish participants? Can we fairly divide a house, furniture, cars, and the family dog between a divorcing couple? Can we design mechanisms for these problems that perform well in practice, are computationally tractable, and whose workings and results are understandable by humans? And, can we even trust the person making these decisions?

We're interested, specifically, in applying techniques from machine learning to this application area. Even more specifically, we're interested in using differentiable function approximators (aka modern deep learning) to represent classes of mechanisms that can be trained using gradient-descent-style methods, and proving things about those methods. On top of this, if you have an interest in cryptography, we're especially interested in developing methods that ensure these properties even when the centralized decision-maker cannot be trusted.

TITLE: Comparing AI to Human Intelligence with Regard to Bias

Tom Goldstein

Prerequisite: Competence in python, some knowledge of deep learning. Programming skills in Pytorch preferred.

This REU will consider ways of comparing the capabilities of AI to human capabilities. We will consider two issues. First, are the biases of humans similar to or different from biases of AI for tasks like reading job applications and performing face recognition? Second, are machine more reliable to less reliable than humans at tasks like performing peer review. One source of data that we are particularly interested in is peer-reviews from machine learning conferences. Can AI help us to identify sources of bias and inaccuracy in these reviews?

TITLE: Ramsey Theory on Ordered Sets

William Gasarch

Prerequisite: Combinatorics including the basics of Ramsey Theory.

The first theorem of infinite Ramsey Theory is the following: For all 2-colorings of pairs of Naturals there exists an infinite homogenous set (a set where all of the pairs are the same color). What if instead of coloring pairs of Naturals (N) we color pairs of Integers (Z)? Of course we still get an infinite homogenous set. But what if we a homogenous set with the same order type as the Z. More genereally, we want to color pairs (or a-subsets) of a linear order L and get a homogenous set of the same order type of L. Can this always be done. No :-(

But what if we allow the homogenous set to be c-homogenuos, meaning that there are only c colors? Here is a sample theorem:

For every 100-coloring of pairs of Z there is a 4-homogenous set of order type Z. (100 can be replaced by any natural.)

We will study infinite Ramsey theory on linear orderings and prove theorems like the one above. For more information see here.

TITLE: Fair Decision, Resource Allocation, and Bias

Furong Huang

Prerequisite: foundational knowledge on machine learning, fairness in machine learning, probability theory, linear algebra, calculus is required, basic knowledge on reinforcement learning is preferred.


Machine learning systems have become prominent in many applications in everyday life, such as healthcare, finance, hiring, and education. These systems are intended to improve upon human decision-making by finding patterns in massive amounts of data, beyond what can be intuited by humans. However, it has been demonstrated that these systems learn and propagate similar biases present in human decision-making. This project aims to develop general theory and techniques on fairness in AI. This project is envisioned to go beyond designing “fair classifiers” that satisfy a static fairness notion in a single moment in time, and designs AI systems that make decisions over a period of time with the goal of ensuring overall long-term fair outcomes at the completion of a process. The use of data-driven AI solutions can allow the detection of patterns missed by humans, to empower targeted intervention and fair resource allocation over the course of an extended period of time. The research from this project will contribute to reducing bias in fair decision-making in general applications of machine learning.

This project will focus on machine learning algorithms for resource allocation, which can be used at various points throughout a process. The team can propose new notions of fairness and show the applicability of those notions to settings in which limited resources are allocated fairly. The proposed research will also go beyond fairness in task-specific supervised learning settings and investigate fairness in unsupervised learning that guarantees to learn fair representations or generative models for multiple downstream tasks. The team can address the practical problems that arise due to uncongenial data in real-world sequential decision-making systems, including distribution shifts between training and testing, imbalanced data, and missing sensitive attributes.

TITLE: Exploring the Hilbert Geometry

David Mount, Auguste Gezalyan

Prerequisites Knowledge of discrete structures/introduction to proofs, algorithms, and programming skills.


Normally we think of the distance between two points as the Euclidean distance. But there are other metrics that have been useful in Genetics, Probability, Physics, and other fields see here. In this project we will be examining the Hilbert Metric from the perspective of computational geometry. We will explore questions involving this metric, such as how to construct Voronoi diagrams and other fundamental structures. The project will include writing a software package to help us visualize these structures. In this project you will learn computaional geometry and combine computaional geometry with programming.