Abstract: There exists a relationship between staircase polygons, persistent graphs, and balanced tableaux. While many aspects of this relationship had been rigorously studied, the problem of recovering a simple staircase polygon whose visibility graph is isomorphic to the skeleton of a given slope-ranking balanced tableau remained open and was previously known to be PSPACE. In this paper, we demonstrate a deterministic polynomial-time algorithm for constructing a staircase polygon with desired properties and prove that certain conditions required by the algorithm hold for any balanced tableau.

Abstract: Degree peeling is frequently used to analyze large networks. In particular, previous work has focused on using degree peeling to decompose networks into cohesive subgraphs. These decompositions allow the researcher to focus in on particularly important structures within the network at hand. However, the properties of such structures have not been studied extensively and may be quite large themselves. Here we examine the properties of the structures generated by the iterative edge decomposition of Abello and Queyroi, which are fixed points of degree peeling. We describe how fixed points of degree peeling can be combined to form larger fixed points. Furthermore, we investigate the effects of graph homeomorphism on degree peeling, which can be very drastic. We provide novel methods for minimizing this influence. Combined with the edge decomposition of Abello and Queyroi, our work can be used in network analysis, community detection, and graph visualization.

Abstract: Given the results of analysis of a tumor sample, can we determine whether a mutation is hereditary or it developed during tumor progression? In this study, we use statistical analysis and tumor simulations to determine in which kinds of tumors the mutational status can be inferred. We found that if we know the ploidy of the sample, we can predict the model with over 95% accuracy in 68% of cases. Otherwise, we can predict the correct model only 11% of the time, where the rest of the time we can make no conclusion. This implies that in many scenarios, doctors do not require additional tumor sequencing in order to know the mutational status. This is useful for both treatment and preventative purposes.

Abstract: As demand rises for machine learning tasks such as classification and regression in many fields, state-of-the-art algorithms and new data collection techniques are necessary to continue to improve performance. Tools such as hyperspectral imaging have been introduced to increase available information, and therefore increase prediction accuracy as well. This creates motivation to curate more hyperspectral datasets, as improved image classification can be achieved through introducing additional spectral bands. Here we introduce a newly curated Hyperspectral Liquid 12-Band dataset (HyL12) that consists twelve classes including eleven liquids and an additional empty class. This dataset can be expanded for security uses to help liquid classification in contexts of safety concerns such as airport security, concerts, and politic events.

Abstract: The margin between cancer survivors and those who receive cancer treatments continues to widen despite modern-day medical efforts. Although there is a great variability of the effectiveness of a treatment from cancer patient to the next, within a single patient and a single tumor,which is composed of thousands of cancerous cells, there is an even greater level of cellular variability, denoted as intra-tumor heterogeneity. Intra-tumor heterogeneity arises as time progresses because cancerous cells continually evolve and acquire mutations that aid in their own survival. Common techniques that analyze the composition of a tumor, such as biopsies, are not accurate measures of a tumor's true composition. It is possible that these treatments are targeted for only a small subset of cells, of the same type, within a single tumor population. By utilizing an open source Java program, it is possible to observe the growth of all individual subpopulations of cancerous cells within a single tumor. This code, may be used with varying parameters that affect tumor growth, would aid in providing more accurate diagnoses, which might help to remedy the ineffectiveness of treatments due to intra-tumor heterogeneity.

Abstract: In 1969, Volker Strassen published a revolutionary paper showing that one can multiply two 2 x 2 matrices with only 7 multiplications, instead of the natural 8; in formal algebraic terms, this means the "tensor rank" of matrix multiplication is at most 7. Since then, there has been extensive literature on the upper and lower bounds of the tensor ranks of various algebraic structures. Despite the computational usefulness and long history, very little is still known about the precise tensor ranks of interesting algebras. In this paper, we provide a method to reduce the natural upper bounds on the tensor ranks of semisimple Lie algebras and lay the framework for improving our bounds on the tensor ranks of semisimple Lie algebras of type A, D, E. In doing so, we not only show how to construct efficient algorithms for computing the Lie bracket in these algebras, but also reveal some important underlying symmetry. In this work we invoke a result of Robert McRae.

Abstract: Network science recasts real-life systems as graphs to study diverse dynamical processes in technological, biological, and physical contexts. More specifically, heterogeneous network structure leads to novel phenomena during synchronization. A network's transition from disorder to coherence can present different forms depending on specific network properties. Modularity in particular can strongly influence the outcome of a synchronization process. This work investigates the effect of modularity on synchronization. I show that the degree of modularity may severely delay global synchronization even though local order emerges after a stable coupling strength threshold. As a result, measurements of global synchronization may be misleading when evaluating coherence in modular networks. These results can be useful for studying the propagation over time of ideas, disease, or information since social, biological, and communication networks often have modular properties.

Abstract: Schubert calculus studies Schubert structure constants for the cohomology rings of a homogeneous space X. In many cases, combinatorial rules involving jeu de taquin on posets associated to these spaces have given positive formulas for these constants. Schutzenberger first proved such a rule for X a Grassmanian. Chaput and Perrin extended this to products of Λ-minuscule classes of spaces under a Kac-Moody group. This includes all Schubert classes for X a minuscule variety. Meanwhile, Buch, Samuel, Thomas, and Yong extended the jeu de taquin theory to the K-theory of all minuscule varieties. We begin to develop the analogous K-theoretic jeu de taquin theory for Proctor's d-complete posets, which are the associated posets for Λ-minuscule Schubert varieties.

Abstract: The multi-robot path planning problem (MPP) on the plane has long been studied both as a topic of research interest and because of it's numerous applications in numerous fields. While many effective algorithms and heuristics exist for discrete MPP on a graph, up until there have been very few results for the continuous version on the plane. In this work we provide a complete algorithm that solves the MPP problem on the plane with a guarantee of constant factor optimality in expectation. We hope that our work may be a good first step into exploring this problem extensions of it in special cases that reflect real world applications.

Abstract: The polynomial hierarchy is a central topic in computer science today, particularly because of its close relationship with the infamous question of whether or not P=NP. For instance, we know that P=NP implies that the polynomial hierarchy collapses. Therefore studying the polynomial hierarchy, for instance finding new ways to define its structure, is an important part of research in theoretical computer science. This project aimed to discover a new hierarchical structure that has a strong correspondence with the polynomial hierarchy. In the end, we discovered a structure based off of the logspace hierarchy that is equivalent to the polynomial hierarchy when given an additional quantifier. The main consequence of this result is that we now have a new way to consider the polynomial hierarchy. Additionally, we were able to define a new set of complete problems for various levels of the hierarchy. More generally, we hope this work can act as a stepping stone for further study in formulations of complexity classes that have somehow relate to the polynomial hierarchy. The results also provide a strong framework for the discovery of new natural complete problems for the polynomial hierarchy phrased in terms of the properties of our model as opposed to the standard model. The ultimate goal is to generally improve our understanding of the various components of the polynomial hierarchy, especially P and NP, in the hopes of answering broader questions such as whether or not P=NP.

Abstract: The packing of DNA into nucleosome core particles (NCPs) is vital to the field of epigenetics and gene expression. Until now, the packing of NCPs has been studied physically via X-rays and cryogenic electron microscopy (cryo-EM), with few to little mathematical tools available. We here develop tools to quantitatively evaluate the amount of interaction between two nucleosomes on their faces and sides, as well as to give biological meaning to the regions of interaction. We apply our methods to X-ray crystal and cryo-EM structures, in the process confirming much of the existing observations while developing new insights into some atypical structures. We also deploy our algorithm to analyze configuration outputs from Markov Chain Monte Carlo (MCMC) simulations, which we found to closely resemble those from cryo-EM and X-ray.

Abstract: Osteoarthritis (OA) is the most prevalent disease amongst knee joints which mostly affects the cartilage in elderly and overweight people. Articular cartilage is simply defined as a soft connective tissue at the end of bones which prevents the bones from erosion and allows smooth glide bones in the joint. OA is characterized by the gradual degeneration of cartilage in knee joint. In Osteoarthritis, cartilage seizes up, erodes away, and eventually disappears in some regions causing the bones to rub again one another with severe pain during motions. Measurement of cartilage loss and 3D visualization can help to quantify the severity of osteoarthritis. Nowadays, Magnetic Resonance imaging (MRI) is extensively used to image the knee joint due to its high resolution and contrast displacement between the bones and cartilage. Though a profound work has been done to detect boundary, there is lack of discussion on cartilage measurement of severe OA knee and the advantages of image pre-processing have not been fully exploited. Encouraged by initial research, this paper proposes a semiautomatic method to improve clinical evaluation of osteoarthritis disease. It emphasizes on improving image pre-processing techniques and the treatments to severe osteoarthritis cases. We explore the image processing techniques applied on MRI in the progression of osteoarthritis diagnosis. Namely, we will identify the clinical biomarkers for early detection of OA by (1) pre-processing MR images, (2) detecting boundary of cartilage by modified radial search method, (3) 2D and 3D cartilage visualizing and (4) calculating volume and thickness of cartilage for OA quantification.

Abstract: We study the multiplicative of a (small) quantum cohomology ring which is encoded by Gromov-Witten invariants. The multiplicative structure of the cohomology ring is rather complicated. In this work, we use the Pieri formula to work on the special cases. Since Gromov-Witten invariants are positive integers, a conjecture of Buch states that this fact determines some properties in quantum cohomology. He also proves that it is true for the Grassmann variety Gr(2,n). We try to prove that this is also true for Gr(m,n) when m>2.

Abstract: This study is about students' note taking in their advanced mathematics lectures. We wonder why students were not able to identity the content the professor was convey during lectures. We found out that (I) students' notes were only copy of what the teacher wrote on the blackboard, (II) students did not record information that was orally stated, and (III) students did not show evidence of being actively engaged during their lectures. We record 7 80 minutes mathematics lectures and photographed of 69 students' notes from these lectures. We found that in the lectures, much of the important information was stated orally, but students typically did not record what was orally stated in their notes.

Abstract: Anomaly detection methods play an important role in keeping Internet operating without interruptions. While many methods rely on centralized detection, there are many benefits in implementing distributed methods where Internet nodes can decide whether there is an ongoing attack using local information only. In this work, I extend a distributed anomaly detection algorithm, DIAMoND, for the case of attacks on both layers of a two-layer network system. The nodes in each layer, which may represent the Internet and the power-grid, communicate with each other and can share information on their status, without sharing sensitive information such as the amount of traffic they handle. The main contribution of this work is to implement a system of trust among layers, so that a node weighs differently information received by nodes in different layers. I show that changes in the trust parameter can influence the accuracy of attack detection.

Abstract: Stadium Security has increased in recent years due to stadium attacks and harmful activity, being a threat to large crowds. Within this security, we examine Walk Through Metal Detectors as they are widely used and an important part of large crowd venue locations. Security in general, is examined to understand the process and activities taking place during real environment security processes through data collection and security software testing.

Abstract: Unlike traditional protocols, mobile authentication is frequently performed in a public setting, so a certain amount of information leakage is inevitable. A common attack called "shoulder surfing" takes advantage of this inadvertently leaked information for various harmful purposes. The objective of this project is to determine whether it is possible to obtain enough information from observing the full-body action of a user unlocking a mobile device to improve the guessing attack accuracy rate.

Abstract: In this paper, we begin by introducing the concept of differential privacy and why it is a useful notion of privacy compared to other approaches. We also introduce the locally distributed differential privacy model. We then introduce various recommendation problems and formulate them mathematically. We then introduce some theoretical tools useful in differential privacy and recommendation algorithms. We then survey some existing literature in differential privacy to get the reader more familiar with how it is applied in various settings and continue to survey various intersections of differential privacy and recommendation algorithms. We end by identifying and precisely stating two open problems and discuss approaches to solving them.

Abstract: The holonomy group of the tangent bundle of the two dimensional unit sphere is precisely the special orthogonal group. Let V denote the tangent space at some fixed point p on the sphere. We seek to consider the invariant space of . Every tensor defines globally a differential operator on . This is of interest since forms a noncommutative vertex operator algebra. The Beltrami-Laplace operator Δ sits inside some . The focus of this paper is to consider the eigenfunctions of Δ and characterize the set of functions in the orbit of differential operators in acting on an eigenfunction. Such a result will allow us to mathematically construct a 2-d nonlinear σ-model.

Abstract: Estimating passenger travel time in public transportation systems provides useful information to commuters and improves their travel experience. Most existing work on travel time estimation has focused on estimating riding time for a single mode of transportation. However, passengers often use different modes of transportation, e.g. subways and buses, and a significant portion of travel time is spent walking and waiting. Therefore, estimating riding time for a single mode of transportation underestimates actual travel time. Using vehicle GPS and passenger fare transaction records from existing transportation infrastructures, we propose a novel unified model that integrates multiple transportation networks in a city. In the model, travel time is divided into components by passenger status and transportation modality. Estimators for each component are constructed from historical data. We evaluate the performance of our travel time estimation model on large-scale real-world data from multiple sources in four transportation networks: subway, taxi, bus, and private vehicle. We show that our model is more accurate than baseline estimates in all modalities by at least **%. In addition, our model is elastic to support new transportation modalities. Finally, we discuss potential applications based on the travel time estimates from our model.

Return to REU Home Page
DIMACS Home Page
DIMACS Contact Information
Page last modified on August 4, 2017.