Abstract: Topological data analysis (TDA) provides tools for studying time-varying data, but many existing methods struggle to distinguish data that are isometric at each time but differ qualitatively. Kim and Memoli's spatiotemporal persistent homology addresses this shortcoming but produces multiparameter modules that are computationally challenging. To mitigate this, we introduce dynamic curvature-set persistent homology, extending Gomez and Memoli's curvature-set persistence to dynamic metric spaces. The resulting modules are interval-decomposable and admit efficient algorithms for computing interleaving distances. Our construction is stable with respect to the dynamic Gromov-Hausdorff distance introduced by the same authors, and we implement both the erosion distance $d_E$ (due to Puuska) and a new Hausdorff-inspired distance $d_2$ with cubic and quadratic runtime, respectively. This enables a robust computational pipeline for distinguishing dynamic data, as demonstrated in experiments with the boids model, where we successfully detect parameter changes.

Abstract: The deletion channel is a simple model of a communication channel, yet its analysis has proved surprisingly complicated over the past half a century. This project aims to develop efficient codes for communicating over the deletion channel. The goal of this project is to explore redundancies in the English language to create novel binary-English codes that are resilient to deletions. We utilize the power of LLMs to correct deletions in English texts.

Abstract: We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to k agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we show that allowing such controlled sharing can restore fairness guarantees that are otherwise unattainable in some scenarios. We additionally propose the Sharing Maximin Share (SMMS), a natural extension of MMS to the k-sharing setting. We show the impossibility of the universal existence of an SMMS guarantee in the k-sharing setting. We further design an algorithm that guarantees a (1 - C)(k - 1)-approximate MMS allocation, where C is the maximum cost of sharing a good. Notably, when (1 - C)(k - 1) ? 1, our algorithm recovers an exact MMS allocation. Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results.

Abstract: Using a proof technique pioneered by Poincare in pursuit of the uniformization theorem, we prove a transversality result which partially implies a major conjecture of Eremenko. This proof requires additionally information about the solutions to a particular Laplace equation, but we conjecture that this information is attainable in the quite general case where our metric is not co-axial.

Abstract: Deoxyribonucelic Acid (DNA) follows a particular biological and mathematical structure. It constantly interacts with enzymes, such as DNA gyrase, which plays an essential role during transcription. There are many mathematical quantities that allow us to understand the topology of a DNA structure. With recent development in chemical and biological modeling software, a program called emDNA allows us to visualize DNA at both the base-pair step and global level. With this software and previously published gyrase-bound structure, we explored the effects of gyrase-binding on the topology of DNA minicircles. We concluded that gyrase generally causes distortion for certain minicircle lengths and with particular structural features, gyrase can cause minicircles to supercoil where high levels of torsion stress are involved.

Abstract: Szegedy and Yu introduced the concept of Rubiks tables which provide an abstraction of object rearrangement problems. In this project, we showed several problems related to Rubiks tables are NP-hard through a reduction from minimum vertex cover.

Abstract: In the sequential learning problem, a network of agents make decisions, informed by a noisy private signal and the predictions of neighboring agents before them. We explore the properties of networks where agents make decisions in a uniformly random order. We characterize necessary conditions for such networks to achieve asymptotic truth learning and introduce various graph constructions that learn in different ways. We also develop an algorithm to transform arbitrary graphs into random-order learning networks using few edge/vertex modifications, with provable approximation guarantees. Finally, we analyze the robustness of learning networks, demonstrating that those achieving asymptotic truth learning under random orderings are resilient to a bounded number of adversarial modifications. Our findings reveal structural properties in networks that achieve random learning and offer algorithmic tools for engineering strong social networks.

Abstract: We consider the problem of approximate Maximum Inner Product (MaxIP). While inapproximability results for high dimensions exist using Distributed PCP, this problem has not been well-studied when the dimension is small--particularly d = O(log n). In this paper, we study the application of threshold graphs for hardness of approximation of MaxIP. Specifically, we describe a reduction that would follow through if a threshold graph did exist, and then explore a potential workaround. Additionally, we discuss applications of the same threshold graph to the problem in the Hitting Set Conjecture, and future directions for this problem.

Abstract: The Moduli Space of ASD connections is an object of great importance in the study of smooth 4-manifolds. Specifically, it produces invariants which can distinguish between smooth structures over 4-manifolds. We provide a revised and reorganized account of the gluing construction for Anti-Self-Dual connections found in sections 7.2.2 and 7.2.3 of The Geometry of 4-Manifolds by Donaldson and Kronheimer, restricted to the case G = U(n), SU(n) and assuming the second cohomology groups of the deformation complex associated to the ASD connections A_i vanish.

Abstract: In learning theory, realizability is a property a distribution holds if there exists a hypothesis. We say that a distribution ( X x Y ) where X is a set of attribute vectors and Y ) is realizable if there exists a hypothesis within a class of hypotheses H such that the true error of the selected hypothesis is 0. When we aim to determine whether a specific distribution is realizable, using property testing can help us tolerantly test for realizability. In this paper, I introduce two different algorithms that explore efficient low-memory strategies in both the strict realizability testing case (aiming to accept only when true realizability is met) and the tolerant realizability testing case (accepting when hypothesis classes contain a hypothesis that is within ε from realizable, and rejecting all hypothesis classes that only contain hypotheses that are at least ε-far from realizable). I also provide additional future directions and conjectures about low memory realizability testing.

Abstract: This paper addresses the compatibility of four fundamental axioms in social choice theory: anonymity (A), neutrality (N), resolvability (R), and Pareto optimality (PO). Building upon the seminal characterization of Bubboloni and Gori, which completely determines when an anonymous, neutral, and resolute (ANR) social choice rule exists on the domain of total orders, we examine whether Pareto efficiency introduces additional constraints. We show that the divisibility condition identified by Bubboloni and Gori - namely, that the number of alternatives m must be strictly smaller than the smallest nontrivial divisor d of the number of voters N - is both necessary and sufficient for the existence of a rule satisfying all four properties simultaneously. Our argument demonstrates that Pareto optimality can be accommodated without further restrictions, and that in the feasible case any voter's ranking can serve as the social outcome while preserving all desired axioms. We conclude by discussing the theoretical significance of this finding, its relation to symmetry considerations in social choice, and how the result may extend to domains beyond total orders, including partial orders and restricted preference classes.

Abstract: Verifiable sources of randomness are a ubiquitous resource for modern algorithms, like machine learning and cryptography. Existing methods like distribution and statistical testing can be used to check the randomness of a source. While the distribution testing is more theoretically sound, statistical tests are often the only computationally feasible choice. This report analyzes ways to bridge techniques from both fields, reframing the NIST test suite in the language of distribution testing and using randomness extractors to empirically validate these tests. This includes technical optimizations needed to complete the experiments in a reasonable amount of time. Additionally, we explored using compression as a measure of randomness, although our results demonstrate that it is unlikely to be stronger than statistical tests. More importantly, the framework used to test the compression algorithms involve notions of epsilon-closeness, which could be used to design more robust uniformity tests.

Abstract: The Discrete Schwarz-Pick Lemma is a discrete analogue of the classical result from complex analysis, arising from the connection between circle packings and conformal maps established by Thurston. Previous works by Beardon-Stephanson and Van Eeuwen proved this lemma for circle packings where circles are tangent or intersect at non-obtuse angles, corresponding to inversive distances $I in [0,1]$. This paper extends the investigation to circle packings with obtuse intersections ($I in (-1,0)$) and disjoint packings ($I>1$). We prove that the Discrete Schwarz-Pick Lemma holds for the full range of intersecting circle packings with inversive distances in $(-1,1]$, provided an additional condition on the weights of each triangle is satisfied. The proof relies on a variational principle for circle packings with inversive distances. Conversely, we show that the lemma fails for disjoint circle packings where I?1. This is demonstrated by constructing a specific counterexample on a triangulated disk with four vertices and providing a numerical analysis to confirm its validity beyond computational error.

Abstract: We worked on large cardinals and compactness theorems in abelian group theory. More specifically, we generalize two classical compactness results for free abelian groups to the broader context of direct sums of cyclic groups.

Abstract: A prediction market over a set of outcomes enables participants to trade based on their beliefs, with market prices reflecting the perceived probabilities of each outcome. Market designers often employ such markets to elicit information about the underlying probability distribution of an event of interest. We introduce a market design that allows the designer to allocate liquidity selectively across different subsets of outcomes. This targeted allocation causes prices in selected regions to be more or less sensitive to trading activity, enabling finer control over how beliefs are aggregated. Compared to the traditional LMSR, our approach achieves improved probability elicitation in regions of interest, while preserving the same worst-case loss guarantee

Abstract: We present a simple proof that any constant-approximation for clique requires (n^{Omega(log n)}) time under the Exponential Time Hypothesis. In particular, our proof avoids the highly non-trivial PCP Theorem, the foundation for all known hardness-of-approximation results for clique at the time of writing.

Abstract: The Plackett-Luce ranking model is one of the most widely used models for dealing with ranking and preference problems. Although it simplifies work with probability distributions of individual preferences, the parameters are quite complicated to learn from the available preference data. While several methods for doing so are developed and guaranteed to converge over time, some real-world applications require a rather fast but not as precise solution. To fulfill this need, I tried to investigate the possibility of learning Plackett-Luce parameters using simple neural networks and loss functions. This work shows that as the number of voters increases, neural networks are much faster than standard algorithms in determining suboptimal solutions, which are enough for testing and highly loaded services like search engines or non-playable character behavior computation units. These models also introduce a way to initialize less random parameters, which potentially can improve performance of iterative approaches.

Abstract: We studied the distortion of randomized voting rules under mild utility assumptions, focusing on settings where utilities are bounded below by 1 and above by a parameter $d$. We first prove a lower bound showing that the distortion of the uniform distribution over candidates can be as large as $Omega(sqrt{d})$, even when preferences are cyclic. We then match this with an upper bound: in the committee selection setting, any $alpha$-approximately stable committee of size $k = lfloor sqrt{d} floor$, when paired with a uniform lottery over its members, achieves distortion at most $O(sqrt{d})$. Additionally, we explored two extensions based on dice-induced utility models, where one candidate receives utility from a discrete distribution (interpreted as a die roll) and the others receive uniformly random utility. In the first direction, we investigated how to minimize distortion with respect to the Nash social welfare under such dice-generated utilities. In the second, we tried to construct families of dice whose induced utility distributions yield a uniform ranking over the special candidate. Our work hope to open new paths for bounding distortion in probabilistic social choice.

Abstract: Alon-Edmonds-Luby (AEL) codes are combinatorial objects designed from bipartite spectral expander graphs: these are concatenated codes that offer powerful unique decoding properties with small alphabet sizes and extremely robust distance amplifications (while preserving the rate property of concatenated codes). When studying AEL codes, we follow the Hamming model: there are polynomial-time algorithms to uniquely decode an AEL codeword when e≤δ/2 (δ is the distance of the code). However, the list-decodability of AEL codes is an emerging area: following the work of Srivastava and Tulsiani, we addressed the problem of proving that when e = kδ/(k+1) as k → ∞, the singly exponential (in k) list size bounds hold but that for the realistic case of constant values of k, we can have much smaller, tight list size bounds (as opposed to the singly exponential list size bounds previously known even for local k values).

Abstract: In the subject of mirror symmetry, there is believed to be a correspondence between Fano varieties and Laurent polynomials. In their paper Maximally Mutable Laurent Polynomials, Coates et al. proved that a family of Fano three-manifolds correspond one-to-one with certain mutation classes of Laurent polynomials. Here, a mutation is a change of variables which changes a Laurent polynomial \(f\) into another Laurent polynomial \(f\). The mutation graph is the graph whose vertices are all Laurent polynomials produced in this way, and edges are the mutations. In our project we will examine the mutation graph of the Laurent polynomial \(x+y+z+\frac{1}{xyz}\) corresponding to projective three-space \(\mathbb{P}^3\).

Abstract: This paper introduces a stochastic observation model for liquid democracy that accounts for uncertainty in delegation decisions, addressing limitations of existing deterministic models. By analyzing key properties such as Positive Proxy Gain (PPG) and Delegated Nash Harmony (DNH), alongside node influence metrics, we evaluate system performance. Theoretical analysis and simulations validate the model's generalizability and PPG property, though DNH may not hold in certain configurations. We incorporate machine learning and heuristic methods to predict node influence, providing robust analytical tools for liquid democracy systems.

Return to REU Home Page
DIMACS Home Page
DIMACS Contact Information
Page last modified on August 1, 2025.