*Note that you must be a U.S. Citizen or Permanent Resident to be eligible for these projects.

Fine-Grained Complexity of Geometric Problems

Project #: DC2025-01
Mentor: Karthik Srikanta, Computer Science

Abstract: In this project we will try to tackle some important (and hard) problems in fine-grained complexity (see [1] for an introduction to the area). For example, we would like to prove assuming SETH that for some large constant d, there is no algorithm running in n^1.99 time that takes as input n many d-dimensional points and computes the farthest pair in the input points. This would improve the bounds given in [2] or Section 4 of [3]. This project is ideal for students who like to combine (elementary) tools from various areas of mathematics to solve problems. Having some background in coding theory or algebraic geometry is a bonus.
[1] https://www.youtube.com/playlist?list=PLKVCRT3MRed69ZsztrNOFxSBQ3ddToCTv
[2] https://arxiv.org/pdf/1709.05282
[3] https://arxiv.org/pdf/1802.02325

Property testing algorithms under space constraints

Project #: DC2025-02
Mentor: Sumegha Garg, Computer Science

Abstract: Sublinear algorithms are a broad class of algorithms that use significantly less computational resources (e.g., time or space) than the size of the input, making them well-suited for large-scale data analysis. In this project, we will focus on a particular class of sublinear algorithms known as graph property testers. While space requirements of other sublinear computational tasks, as in the streaming model, are well-explored, the study of low-memory property testers is far less developed. Property testing is a natural notion of approximation for decision problems, where given a property (or decision), the task is to distinguish whether a given instance has this property or is "far" from any instance having the property. Here, the tester is given query access to the instance. Such tasks are widely used in various areas of TCS -- our investigation will center on property testing for graphs (for e.g., whether a graph has a large clique), examining how space constraints influence the query complexity of these tests. Many graph property testers sample a random subset of vertices and construct the induced subgraph on these vertices, which can be memory extensive. This project aims to evaluate whether existing algorithms are optimal in terms of memory usage or if there are potential trade-offs between memory and query complexity.

Algorithms for discrete structures with noisy estimations

Project #: DC2025-03
Mentor: Shahrzad Haddadan, Management Sciences and Information Systems

Abstract: As data mining algorithms become increasingly prevalent across various applications, it is essential to adapt classic computational models to overcome the limitations and challenges encountered in real-world scenarios. A significant challenge in analyzing data in real-world applications is the presence of noise in the estimations and measurements. Various mathematical tools and techniques have been developed to account for noise in algorithm design, particularly when dealing with numerical data. However, these techniques are often unsuitable for analyzing data with a discrete structure, such as graphs or permutations. In this project, we seek to develop algorithms for analyzing discrete data structures, like graphs or permutations, when these structures are subject to noise in their estimations. Our goal is to develop randomized approximation schemes, and to evaluate both their error bounds and computational complexity in relation to the input parameters and the level of noise in the estimations. We will evaluate the performance of our algorithms through both theoretical analysis and experimental validation, using publicly available relevant datasets.

Prerequisites: Candidates should be familiar with some programming language (C++, Java, Python, or R for programming and Python or R for visualization) and have a good understanding of graph theory concepts, probability theory and data structures.

New approaches to uniformity testing

Project #: DC2025-04
Mentor: Periklis Papakonstantinou, Management Science and Information Systems

Abstract: This project regards testing whether samples from a random source are uniformly distributed.
Randomness plays a significant role in various areas of Computer Science, though its necessity is sometimes debated or not fully understood. For instance, modern Machine Learning (ML) systems, such as those used to train transformers for building Large Language Models, rely on coin-flipping techniques during training. These state-of-the-art systems depend heavily on high-quality random sources. In contrast, in fields like Cryptography, the necessity of randomness is unequivocal. The security of every cryptographic protocol fundamentally depends on the availability of high-quality randomness at the outset. High-quality randomness is defined as "uniform noise" - data that follows a uniform distribution or is statistically indistinguishable from uniform.
Given its importance, randomness is a critical resource. This raises two key questions: Where do we obtain randomness, and how can we ensure its quality? This project focuses on the second question: how can we test for uniformity?
The National Institute of Standards and Technology (NIST) has developed standardized test suites to evaluate uniformity. While testing for perfect uniformity is theoretically infeasible, these tests are widely used in practice by systems and protocols that rely on uniform randomness. This project aims to explore the development of a more practical theoretical framework for randomness testing and investigate how deep neural networks might be employed to assess uniformity.
The student who is going to undertake this task should have enough mathematical maturity and/or to know how to program deep neural network architectures.

Error-Correcting Codes: Between Algebraic and Combinatorial

Project #: DC2025-05
Mentor: Shashank Srivastava, DIMACS

Abstract: Error-correcting codes are large sets of strings over a fixed alphabet and of a common length, such that any two distinct strings in the set are well separated in Hamming distance. Constructing such objects turns out to be often quite non-trivial, and the first success came via existential results based on the probabilistic method. Explicit constructions have been found in certain parameter regimes, and are broadly of two flavors: those based on finite field algebra, and those based on psuedorandom primitives such as expander graphs. Both these approaches have their own advantages and disadvantages. In this project, we will try to investigate the connections between them, as well understanding better their differences or lack thereof. The project will be largely theoretical, with focus on proving statements than practical performance.
Concretely, we will investigate whether some algebraic constructions can be understood in terms of their associated underlying graphs. Another direction is how can one involve pseudorandom objects while dealing with algebraic constructions, where we know truly random choices lead to good performance? We will also potentially investigate interesting algorithmic challenges associated to these codes, which can sometimes involve convex relaxations like LPs and SDPs.
It will help to have familiarity with discrete math, in particular topics like finite fields. No background in coding theory or convex relaxations will be assumed, but a general exposure with combinatorics and algorithms will be desirable.

Intransitive Social Preferences and Intransitive Dice

Project #: DC2025-06
Mentor: Kangning Wang, Computer Science

Abstract: In voting theory, the Condorcet's paradox says that sometimes among three candidates A, B, and C, a majority of voters prefer A to B, a majority of voters prefer B to C, and a majority of voters prefer C to A. In other words, the social preferences under majority voting can be intransitive. In probability theory, there is a similar phenomenon known as intransitive dice: for three mutually independent distributions A, B, and C, it can be the case that Pr[A>B]>0.5, Pr[B>C]>0.5, and Pr[C>A]>0.5. In this project, we are going to explore what will happen in elections when candidates are "dice."

Here is a related paper: "Dominating sets in k-majority tournaments" by Alon, Brightwell, Kierstead, Kostochka, and Winkler.

Measuring and exploiting excess volatility in the stock market

Project #: DC2025-07
Mentor: David Pennock, DIMACS

Abstract: The variance of a prediction, by definition, cannot be higher than the variance of the uncertain quantity being predicted. Economists debate whether prices in the stock market, which predict the discounted future values of public companies, exhibit excess volatility. In this project, we take as an assumption that a prices time series has excess volatility and ask for good trading strategies that exploit that fact. We seek both empirical evidence in stock market and prediction market data and mathematical proofs.

Project at intersection of AI and economics

Project #: DC2025-08
Mentor: Xintong Wang, Computer Science

Abstract: The project will be at the intersection of artificial intelligence and economics, with an emphasis on studying multi-agent, game-theoretic environments where agents interact, often with the aid of algorithms, and agents' desires may not easily and reliably match up. Examples include online platforms, financial markets, a rush-hour commute, and a game of poker.
Some concrete problems that the REU student may explore are (1) the formation of algorithmic collusion and how to mitigate or regulate it from an algorithmic perspective; (2) the use of LLM agent to improve the efficiency of negotiation tasks and bilateral trading; and (3) some other strategic behavior on economic platforms or any multi-agent systems. Background knowledge in economics or game theory may be a plus but not necessary.

Classical, Computational, and AI-Powered Social Choice

Project #: DC2025-09
Mentor: Lirong Xia, DIMACS

Abstract: Social choice studies how to aggregate a group of agents' preferences to make a collective decision. Typical applications include voting, resource allocation/fair division, group recommendation, and participatory budgeting. This project provides an umbrella of a wide range of customizable projects including classical (axiomatic) aspects, game-theoretic aspects, statistical aspects, computational and algorithmic aspects, and using AI including machine learning and Generative AI to learn people's preferences and desiderata and to design and analyze voting rules.

Truth Learning in a Social Network

Project #: DC2025-10
Mentor: Jie Gao, Computer Science

Abstract: Individuals gather information by both independent observations and communication with others in a social environment. Social Learning studies how dispersed and self-interested agents aggregate information. In this project we study whether social learning can enable truth learning. It is well known that learning can fail due to herding, where agents collectively focus on an early false consensus and ignore subsequent observations. Therefore, a general goal in social learning is to get around the issue of herding and enable truth learning. In this project we study the computational aspect of social learning with different observation models, the knowledge landscape, the environment of learning and social processes such as peer pressure, social influence, network effect as well as the existence of adversarial players. This is the third year of this summer REU project and the work of previous two years both led to publishable results at international academic conferences.

Multi-Robot Path Planning: Structural Studies and High-Performance Algorithms

Project #: DC2025-11
Mentor: Jingjin Yu, Computer Science

Abstract: Graph-based Multi-Robot Path Planning (MRPP), also known as Multi-Agent Path Finding (MAPF), seeks to quickly find high-quality paths for routing a large number of robots. MRPP/MAPF has many important applications, e.g., enabling the coordination of thousands of robots at Amazon warehouses. A significant amount of work has been done in the field, and many decent algorithms have been proposed, but we are still in the relatively early stages of fully understanding the structure of the problem and utilizing the insight to design more capable MRPP/MAPF algorithms. For example, current algorithms are mostly agnostic to the graph structure - can we leverage that information? In this summer project, the student researcher will learn about the existing SOTA in MRPP/MAPF, seek a better understanding of particular structures, and leverage that understanding to design better algorithms. The research can be theoretical, algorithmic, or a mix of the two.
Some relevant papers:
https://arxiv.org/pdf/1904.02598.pdf (https://www.youtube.com/watch?v=0MUGrg5CphM)
https://arxiv.org/pdf/2201.08976.pdf (https://www.youtube.com/watch?v=v8WMkX0qxXg)
https://arxiv.org/pdf/2312.10887
Jingjin Yu's website: https://arc-l.github.io/pub.html

Genome folding and function: from DNA base pairs to nucleosome arrays and chromosomes

Project #: DC2025-12
Mentor: Wilma Olson, Chemistry and Chemical Biology

Abstract: Despite the astonishing amount of information now known about the sequential makeup and spatial organization of many genomes, there is much to learn about how the vast numbers of DNA base pairs in these systems contribute to their three-dimensional architectures and workings. The chemical structure of DNA contains information that dictates the observed spatial arrangements of base pairs within the double helix and the susceptibilities of different base sequences to interactions with proteins and other molecules. Our group has been developing software to analyze the spatial and energetic codes within known DNA structures and using these data in computational studies of larger nucleic acid systems. By representing the DNA bases as sets of geometric objects, we can capture the natural deformability of DNA as well as the structural details of ligand-bound interactions (1,2). There are now sufficient data to examine the influence of sequence context, i.e., the effects of immediate neighbors, on the apparent motions of the bases and to develop simple functions that capture this information. The observed behavior can be incorporated in computational treatments to improve our understanding of macromolecular systems in which DNA sequence and protein binding play important roles. For example, DNA elements that regulate gene expression often lie far apart along genomic sequences but come close together during genetic processing. The intervening residues form loops, mediated by proteins, which bind at the sequentially distant sites. We have developed methods that take account of both DNA and protein in simulations of loop formation and successfully captured experimental observations (3-5). Our recent studies of long-range communication between regulatory elements on short nucleosome-decorated DNA (6) provide a basis for linking the 'local' arrangements of nucleosomes in these systems to higher-order macromolecular structures, such as the looped architectures detected within chromosomes and the circular pieces of genomic DNA associated with a variety of cancers. We are developing new algorithms to characterize the spatial arrangements of nucleosome-decorated DNA circles and incorporating the collective information in nucleosome-level depictions of chromosomal DNA (7,8). The build-up of structural components in our treatment of DNA and chromatin offers new insight into the stepwise processes that underlie genome organization and processing.

References:
1. Young, R.T., L. Czapla, Z.O. Wefers†, B. Cohen†, W.K. Olson. (2022) Revisiting DNA sequence-dependent deformability in high-resolution structures: effects of flanking base pairs on dinucleotide morphology and global chain configuration. Life (Basel) 12:759. DOI: 10.3390/life12050759
2. Olson, W.K., Y. Li, M.O. Fenley. (2022) Insights into DNA solvation found in protein-DNA structures. Biophys. J. 121:4749-4758. DOI: 10.1016/j.bpj.2022.11.019
3. Wei, J., L. Czapla, M.A. Grosner, D. Swigon, W.K. Olson. (2014) DNA topology confers sequence specificity to nonspecific architectural proteins. Proc. Natl. Acad. Sci. USA 111:16742-16747. DOI: 10.1073/pnas.1405016111
4. Clauvelin, N., W.K. Olson. (2021) Synergy between protein positioning and DNA elasticity: energy minimization of protein-decorated DNA minicircles. J. Phys. Chem. B 125:2277-2287. DOI: 10.1021/acs.jpcb.0c11612
5. Young, R.T., N. Clauvelin, W.K. Olson. (2022) emDNA - A tool for modeling protein-decorated DNA loops and minicircles at the base-pair step level. J. Mol. Biol. 434:167558. DOI: 10.1016/j.jmb.2022.167558
6. Clauvelin, N., P. Lo†, O.I. Kulaeva, E.V. Nizovtseva, J. Dias, J. Zola, M. Parashar, V. Studitsky, W.K. Olson. (2015) Nucleosome positioning and composition modulate in silico chromatin flexibility. J. Phys.: Condens. Matter 27:064112. DOI: 10.1088/0953-8984/27/6/064112
7. Todolli, S., P.J. Perez, N. Clauvelin, W.K. Olson. (2017) Contributions of sequence to the higher-order structures of DNA. Biophys. J. 112:416-426. DOI: 10.1016/j.bpj.2016.11.017
8. Todolli, S., R.T. Young, A.S. Watkins†, A. Bu Sha†, J. Yager†, W.K. Olson. (2021) Surprising twists in nucleosomal DNA with implication for higher-order folding. J. Mol. Biol. 433:167121. DOI: 10.1016/j.jmb.2021.167121

Circle packing on surfaces

Project #: DC2025-13
Mentor: Feng Luo, Mathematics & Hongbin Sun, Mathematics & Zhenghao Rao, Mathematics

Abstract: A circle packing is an arrangement of circles in a given metric surface such that no two overlap and some of them are mutually tangent. Circle packing theory investigates the geometry and combinatorics of packings of arbitrarily sized circles: these give rise to discrete analogs of conformal mapping, Riemann surfaces, and the like. The subject was revolutionized by William Thurston in 1979 and has attracted much research attention since then. It can be considered as discrete analytic function theory. In this project, we will aim to prove the famous Koebe-Andreev-Thurston's circle packing of the unit disk and its generalizations. The topics to be covered include Schramm's rigidity of infinite circle packing, the discrete Schwarz Lemma, inversive circle packing, and the discrete uniformization theorem for circle packing.
The students should have a solid knowledge of surface topology, basic algebraic topology, and complex analysis. Some knowledge of Riemannian geometry of surfaces will be helpful.
References:
1. Introduction to Circle Packing: The Theory of Discrete Analytic Functions, by K. Stephenson. Cambridge University Press; Illustrated edition (April 18, 2005)
2. Notes on circle packing, by D. Glickenstein, B. Chow, F. Luo, to be distributed for REU students
3. Circle Packing: A Mathematical Tale, Kenneth Stephenson https://web.math.utk.edu/~kens/Notices_article.pdf
4. The convergence of circle packings to the Riemann mapping", B. Rodin, D. Sullivan, J. Diff . Geom. 26 (1987), 349-360

Compactness in the mathematical universe

Project #: DC2025-14
Mentor: Filippo Calderoni, Mathematics

Abstract: Large cardinals axioms postulate the existence of combinatorial properties of infinity. These axioms are far beyond the usual axioms of mathematics and expand the burden of the mathematical universe. A well-studied consequence of large cardinal axioms is compactness. Compactness denotes the extent to which mathematical structures are determined by their local behavior.
This project focuses on set theory, with an eye toward abstract algebra. We will examine some famous compactness properties for algebraic structures and investigate new ones.
The student is expected to have some background in set theory and linear algebra. Some experience in group theory or abstract algebra is a plus.

Spherical metrics with cone singularities

Project #: DC2025-15
Mentor: Chi Li, Mathematics

Abstract: Given finitely many points {p₁, . . . , pn} on a topological sphere S² and an n-tuple of positive real numbers {β₁, . . . , β_n}, we will study the following problems which could be considered as a generalization of the classical uniformization theorem for spherical Riemann surfaces:
Problem 1: Does there exist a Riemannian metric g on S²\ {p₁, . . . , p_n} of constant Gauss curvature 1 that has cone singularities at p_i of cone angle 2πβ_i.
Problem 2: If there exist such metrics, how many different equivalent classes are there?
These problems have been studied by many mathematician using methodsfrom different subjects: complex analysis, geometry, analytic theory of ODE,parabolic vector bundles on Riemann surfaces. The preliminary preparation forstudying these problems are good knowledge of complex analysis and basics forRiemann surfaces
For details about this project please check this pdf file.

Projects in Pure Math

Project #: DC2025-16
Mentor: Faculty of the Math Department, Mathematics

Abstract: The Math REU Coordinator is Prof. Kristen Hendricks. Several projects will be run in 2025 by members of the pure math faculty, in addition to the ones described below. Applicants interested in a project in pure mathematics should list this project in their application and indicate their specific Math interests; further details on the projects will be worked out in the Spring.

About mutations of Laurent polynomials

Project #: DC2025-17
Mentor: Christopher Woodward, Mathematics

Abstract: We will look at maximally mutable Laurent polynomials in three variables, and what the corresponding mutation graphs looks like. We will look for tropical formulas for the polynomials that are "maximally mutable."

Vortices in geometry and physics

Project #: DC2025-18
Mentor: Paul Feehan, Mathematics

Abstract: Vortices were first proposed by physicists Ginzburg and Landau as mathematical models for superconductivity. Their vortex equations are non-linear first order PDEs for a U(1) connection A and a field phi over two-dimensional Euclidean space. Within the mathematical gauge theory community, their key properties were proved by Cliff Taubes (1980) and Arthur Jaffe and Cliff Taubes (1980). These basic Ginzburg-Landau vortex equations were extended by Steve Bradlow (1990 and 1991) to the case of unitary connections A on and sections phi of a Hermitian vector bundle E over Riemann surfaces and then complex Kaehler manifolds of any dimension, first in the case where E is a line bundle and then a bundle of arbitrary complex rank. In this project, we will extend Taubes' and Bradlow's work by learning how to use gluing to construct solutions to the vortex equations in increasing generality: (1) U(1) vortices over the complex plane C, (2) U(1) vortices on Hermitian line bundles over Riemann surfaces, (3) U(r) vortices on Hermitian vector bundles of rank r over Riemann surfaces, and finally (4) U(r) vortices on Hermitian vector bundles of rank r over complex Kaehler manifolds. Time permitting, we will also explore methods to extend these gluing results from the category of complex Kaehler manifolds to symplectic manifolds.

Return to REU Home Page
DIMACS Home Page
DIMACS Contact Information
Page last modified on January 30, 2025.