Combinatorics and Algorithms for Real Problems


List of Projects

TITLE: Simulation of Low-Depth Quantum Circuits

Gorjan Alagic, Matthew Coudron

Prerequisites: A first course in quantum computing or an understanding of the fundamentals of gate-model quantum computation. A course in algorihtms or equivalent knowledge. Probability, Linear Algebra, Math maturity.


Many of the leading proposals for obtaining a quantum advantage on near-term quantum hardware are based on known hardness results for the task of sampling from the output distribution of low-depth quantum circuits. However, while the task of sampling the output of these circuits is known to be hard when performed at sufficiently high precision, it has also been shown that, in some cases, there are efficient classical algorithms for computing output probabilities of these circuits to inverse polynomial precision. These algorithmic results, while currently limited, call into question whether the near-term quantum circuits currently used to perform hard sampling tasks can ever be used to solve hard decision problems. In this project, in an attempt to make progress on this fundamental question, we will focus on notable classes of near-term quantum circuits for which this question is unresolved, and seek to design algorithms to efficiently estimate their outputs. Designing these algorithms is an opportunity to develop and put to use a strong intuition for both quantum computation and classical algorithms.

TITLE: Fast Routing Using Teleportation Primitives

Aniruddha Bapat, Eddie Schoute Andrew Childs, Alexey Gorshkov,

Prerequisites: Basic graph theory, algorithms and complexity. No quantum knowledge required.


In this project we will consider separations for routing tokens on a network (graph). Token routing happens via exchanges (swaps) and by a new primitive that allows us to teleport tokens. Besides theoretical separations, we can also consider practical algorithms that exhibit excellent performance, which can be instrumented through simulations. We are interested in this problem because quantum teleportation enables us to move quantum information (tokens) rapidly across long distances given fast classical communication. Because of quantum hardware constraints, we expect that such long-distance interactions may be necessary for quantum algorithms (in comparison, classical communication is much cheaper and assumed to be free). We model teleportation as finding a path through an auxiliary graph between a node and its destination. If such a path exists, this takes just constant time. Teleportation along multiple non-intersecting paths can be performed in parallel. Now with this teleportation primitive and basic token exchanges, we wish to know the fastest way to implement arbitrary permutations (aka perform routing) on a given graph.

TITLE: Diversity in Matching Markets

John Dickerson

Prerequisites: Basic understanding of supervised machine learning, some experience with a programming language


How should a firm allocate its limited interviewing resources to select the optimal cohort of new employees from a large set of job applicants? How should that firm allocate cheap but noisy resume screenings and expensive but in-depth in-person interviews? We view this problem through the lens of combinatorial pure exploration (CPE) in the multi-armed bandit setting, where a central learning agent performs costly exploration of a set of arms before selecting a final subset with some combinatorial structure. In our case, that combinatorial structure will incorporate elements of diversity, where including multiple elements of the same type in the final set results in diminishing marginal gain. We will apply our algorithms to real data from university admissions and the hiring processes from major tech firms.

TITLE: Using Generative Adversarial Networks in Domain Adaptation

Soheil Feizi

Prerequisite: Probability, Linear Algebra, Python programming preferred but not required.

Learning a probability model from data is a fundamental problem in machine learning and statistics. Building on the success of deep learning, there has been a modern approach to this problem using Generative Adversarial Networks (GANs). GANs view to this problem as a game between two sets of functions: a generator whose goal is to generate synthetic samples that are close to the real data training samples and a discriminator whose goal is to distinguish between the real and fake samples. In this project, we aim to leverage some of the state-of-the-art GAN architectures to produce distributions that are unbiased with respect to some protected features.

TITLE: Understanding bias and fairness in neural networks through visualizations:

Tom Goldstein

Prerequisite: Basic knowledge and experience with machine learning frameworks, preferable Pytorch or Tensorflow, and experience with building and training neural networks.


Artificial neural networks are incredibly powerful machine learning engines, and most of this strength comes from their biases. The “implicit bias” of neural networks enables fast learning from small datasets. At the same time, trained neural networks make decisions that can exhibit social biases for or against protected groups. In this project, our goal is to gain a better understanding of what biases neural networks have, how this enables learning, and how to control biases to achieve positive learning outcomes when making socially important decisions like credit approval or criminal identification. We will try to make use of visualization tools to represent the decision boundaries of neural networks. By doing this, we can visualize how the implicit biases of different network architectures lead to different decision boundaries. We can also visualize how the decision boundaries of neural networks create undesirable outcomes, like “fairness gerrymandering,” that are unacceptable in certain applications. Students working on this project will implement a range of visualization methods for decision boundaries, and will also implement a range of methods for imposing fairness constraints in machine learning. The outcome of this project will be a code repository for visualization and fair learning, and a comprehensive study of how different fairness constraints perform when applied to complex learning problems.

TITLE: Learning Fair Representations

Furong Huang

Prerequisite: Mathematical maturity in linear Algebra, probability, statistics, exposure to Machine Learning is required.


Machine learning algorithms are very powerful and they are being used everywhere today. Unfortunately, machine learning algorithms can learn bias as they learn. This could have drastic consequences. Many concerns have been voiced about the susceptibility of data-intensive AI algorithms to error and misuse, and the possible ramifications for gender, age, racial, or economic classes. The proper collection and use of data for AI systems, in this regard, represent an important challenge. Beyond purely data-related issues, however, larger questions arise about the design of AI to be inherently just, fair, transparent, and accountable. Researchers must learn how to design these systems so that their actions and decision-making are transparent and easily interpretable by humans, and thus can be examined for any bias they may contain, rather than just learning and repeating these biases. There are serious intellectual issues about how to represent and ‘‘encode’’ value and belief systems. Scientists must also study to what extent justice and fairness considerations can be designed into the system, and how to accomplish this within the bounds of current engineering techniques.

The overall goal is to obtain a representation of our original data that has the same dimension as the original data, and preserves as much of information in the original data as possible while de-correlating the sensitive attribute.

TITLE: Lattice-Based Cryptography

Jonathan Katz

Prerequisites: Mathematical maturity, linear algebra/group theory, programming ability. Knowledge of cryptography is useful but not essential.


Next-generation cryptosystems may be based on newer assumptions related to the hardness of solving certain problems on lattices. This project will explore existing schemes, as well as implementations of best-known attacks against those schemes. (Only one of the projects by Jonathan Katz will be offered. Hence if this is one that you list, please list at least one more project.)

TITLE: Adversarial Machine Learning

Jonathan Katz

Prerequisites: Mathematical maturity, probability/statistics, programming ability. Knowledge of machine learning is useful but not essential.


Abstractly, machine learning involves learning a model from a set of training data that was generated according to that model. What happens when the training data is “poisoned,” i.e., some of the training data is maliciously generated by an adversary trying to cause the machine-learning algorithm to produce an incorrect model. This project will explore feasibility results and impossibility results for different variations of this problem. (Only one of the projects by Jonathan Katz will be offered. Hence if this is one that you list, please list at least one more project.)