Computer Sciences Commons^™

Towards Ryser's Conjecture: Bounds On The Cardinality Of Partitioned Intersecting Hypergraphs, Anna E. Dodson

Dartmouth College Undergraduate Theses

This work is motivated by the open conjecture concerning the size of a minimum vertex cover in a partitioned hypergraph. In an r-uniform r-partite hypergraph, the size of the minimum vertex cover C is conjectured to be related to the size of its maximum matching M by the relation (|C|<= (r-1)|M|). In fact it is not known whether this conjecture holds when |M| = 1. We consider r-partite hypergraphs with maximal matching size |M| = 1, and pose a novel algorithmic approach to finding a vertex cover of size (r - 1) in this case. We define a reactive hypergraph to be a back-and-forth algorithm for a hypergraph which chooses new edges in response to a choice of vertex cover, and prove that this algorithm terminates for all hypergraphs of orders r = 3 and 4. We introduce the idea of optimizing the size of the reactive hypergraph and find that the reactive hypergraph terminates for r = 5...20. We then consider the case where the intersection of any two edges is exactly 1. We prove bounds on the size of this 1-intersecting hypergraph and relate the 1-intersecting hypergraph maximization problem to mutually orthogonal Latin squares. We propose a generative algorithm for 1-intersecting hypergraphs of maximal size for prime powers r-1 = pd under the constraint pd+1 is also a prime power of the same form, and therefore pose a new generating algorithm for MOLS based upon intersecting hypergraphs. We prove this algorithm generates a valid set of mutually orthogonal Latin squares and prove the construction guarantees certain symmetric properties. We conclude that a conjecture by Lovasz, that the inequality in Ryser's Conjecture cannot be improved when (r-1) is a prime power, is correct for the 1-intersecting hypergraph of prime power orders.

Cup-Net: Compressed Ultrafast Photography Using Convolutional Neural Networks, Matthew Parker

ENGS 88 Honors Thesis (AB Students)

Compressed ultrafast photography (CUP) is a cutting-edge imaging technique that uses a variation of the traditional streak camera to obtain video at 100 billion frames per second with a single exposure. In order to achieve this level of temporal detail, CUP leverages compressed sensing (CS). Compressed sensing theory states that a compressed representation of an image can be directly acquired using a non-adaptive measurement matrix so long as the encoding matrix follows certain properties such as restrictive isometry and incoherence. This compressed representation of the original scene can later be reconstructed back into the original form. CUP applies CS by …

Autonomous Eye Tracking In Octopus Bimaculoides, Mark Andrew Taylor

Dartmouth College Undergraduate Theses

The importance of the position of cephalopods, and particularly octopuses, as the most intelligent group of invertebrates is becoming increasingly appreciated by the neuroscience research community. Cephalopods are the most distantly related species to humans that possesses advanced cognitive abilities; as their intelligence evolved independently from vertebrates, comparative analyses reveal trends in the evolution of nervous systems and the foundations of intelligence itself. Vision is an especially important area of cephalopod cognition to research because cephalopods are predominantly visual creatures, like humans, and the rapid transduction of visual signals allows the inner-workings of octopus cognition to be revealed in real …

A Computational Approach To Analyzing And Detecting Trans-Exclusionary Radical Feminists (Terfs) On Twitter, Christina T. Lu

Dartmouth College Undergraduate Theses

Within the realm of abusive content detection for social media, little research has been conducted on the transphobic hate group known as trans-exclusionary radical feminists (TERFs). The community engages in harmful behaviors such as targeted harassment of transgender people on Twitter, and perpetuates transphobic rhetoric such as denial of trans existence under the guise of feminism. This thesis analyzes the network of the TERF community on Twitter, by discovering several sub-communities as well as modeling the topics of their tweets. We also introduce TERFSPOT, a classifier for predicting whether a Twitter user is a TERF or not, based on a …

Restoring Humanity To Those Dying Below: An Inquiry Concerning The Ethics Of Autonomous Weapons Systems, Juliette A. Pouchol

Dartmouth College Undergraduate Theses

Today, autonomous weapons systems promise to make war more precise and effective while removing the human component from the battlefield. With the improvement of deep learning and computer vision, machines will soon be able to navigate and search through contested environments, discriminate between targets, and engage appropriately. The memoirs of drone pilots point to the evolving psychological impact of killing caused by the increase in the amount of empathy and emotional connectedness that drone pilots develop towards their target during the intimate surveillance period. A war fought without "skin-in-the-game" enables drone pilots to become better moral agents and decreases the …

Push-Relabel Algorithms For Computing Perfect Matchings Of Regular Bipartite Multigraphs, Benjamin J. Coleman

Dartmouth College Undergraduate Theses

We seek to compute perfect matchings of a d-regular bipartite multigraph G = (V, E). If d is a power of 2, we can perform Euler decomposition, which recursively separates a graph of even degree into subgraphs of smaller degree. When d is not a power of 2, however, Euler decomposition eventually returns a subgraph of odd degree. At this point, we can manually remove a perfect matching to return the graph to even degree and continue Euler decomposition. In this paper, we explore push-relabel algorithms as potential solutions to removing a perfect matching from a regular bipartite multigraph. Empirical …

Learning Humor Through Ai: A Study On New Yorker's Cartoon Caption Contests Using Deep Learning, Ray Tianyu Li

Dartmouth College Undergraduate Theses

My research focuses on predicting a cartoon caption's wittiness using multi-modal deep learning models. Nowadays, deep learning is commonly used in image captioning tasks, during which the machine has to understand both natural languages and visual pictures. However, instead of aiming to describe a real-world scene accurately, my research seeks to train computers to learn humor inside both natural languages and visual images. Cartoons are the artistic medium that supposes to deliver visual humor, and their captions are also supposed to be interesting to add to the fun. Thus, I decided to use research on cartoons' captions to see if …

Automatic Generation Of Input Grammars Using Symbolic Execution, Linda Xiao

Dartmouth College Undergraduate Theses

Invalid input often leads to unexpected behavior in a program and is behind a plethora of known and unknown vulnerabilities. To prevent improper input from being processed, the input needs to be validated before the rest of the program executes. Formal language theory facilitates the definition and recognition of proper inputs. We focus on the problem of defining valid input after the program has already been written. We construct a parser that infers the structure of inputs which avoid vulnerabilities while existing work focuses on inferring the structure of input the program anticipates. We present a tool that constructs an …

Vr-Notes: A Perspective-Based, Multimedia Annotation System In Virtual Reality, Justin Luo

Dartmouth College Undergraduate Theses

Virtual reality (VR) has begun to emerge as a new technology in the commercial and research space, and many people have begun to utilize VR technologies in their workflows. To improve user productivity in these scenarios, annotation systems in VR allow users to capture insights and observations while in VR sessions. In the digital, 3D world of VR, we can design annotation systems to take advantage of these capabilities to provide a richer annotation viewing experience. I propose VR-Notes, a design for a new annotation system in VR that focuses on capturing the annotator's perspective for both "doodle" annotations and …

Label Noise Reduction Without Assumptions, Jason Wei

Dartmouth College Undergraduate Theses

We propose an algorithm for training neural networks in noisy label scenarios that up-weighs per-example gradients that are more similar to other gradients in the same minibatch. Our approach makes no assumptions about the amount or type of label noise, does not use a held-out validation set of clean examples, makes relatively few computations, and only modifies the minibatch gradient aggregation module in a typical neural network training workflow. For CIFAR-10 classification with varying levels of label noise, our method successfully up-weighs clean examples and de-prioritizes noisy examples, showing consistent improvement over a vanilla training baseline. Our results open the …

Predicting Influencer Virality On Twitter, Danah K. Han

Dartmouth College Undergraduate Theses

The ability to successfully predict virality on Twitter holds great potential as a resource for Twitter influencers, enabling the development of more sophisticated strategies for audience engagement, audience monetization, and information sharing. To our knowledge, focusing exclusively on tweets posted by influencers is a novel context for studying Twitter virality. We find, among feature categories traditionally considered in the literature, that combining categories covering a range of information performs better than models only incorporating individual feature categories. Moreover, our general predictive model, encompassing a range of feature categories, achieves a prediction accuracy of 68% for influencer virality. We also investigate …

Information Network Navigation, Ryan W. Blankemeier

Dartmouth College Undergraduate Theses

In this paper, we develop an interactive system to navigate information networks as a space with geometry, assigning each node in the network to geographical coordinates, and with that the ability to navigate as if on a map. A map-based rendering of the network gives the user the ability to understand meta-relationships (i.e., non-link-based relationships) that exist in the dataset that are lost with a traditional web search and (hyper-)link navigation. This requires first being able to represent the information corpus in such a way as to enable a quantifiable notion of similarity between the information nodes. A t-SNE (t-distributed …

Query Free Adversarial Transfer Via Undertrained Surrogates, Christopher S. Miller

Dartmouth College Undergraduate Theses

Adversarial examples consist of minor perturbations added to a model's input which cause the model to output an incorrect prediction. Deep neural networks have been shown to be highly vulnerable to these attacks, and this vulnerability represents both a security risk for the use of deep learning models in security-conscious fields and an opportunity to improve our understanding of how neural networks generalize to unexpected inputs. Transfer attacks are an important subcategory of adversarial attacks. In a transfer attack, the adversary builds an adversarial attack using a surrogate model, then uses that attack to fool an unseen target model. Recent …

Mining Academic Publications To Predict Automation, Elena A. Doty

Dartmouth College Undergraduate Theses

This paper proposes a novel framework of predicting future technological change. Using abstracts of academic publications available in the Microsoft Academic graph, co-occurrence matrices are generated to indicate how often occupation and technological terms are referenced together. This matrices are used in linear regression models to predict future co-occurrence of occupations and technologies with a relatively high degree of accuracy as measured through the mean squared error of the models. While this work is unable to link the co-occurrences found in academic publications to automation in the labor force due to a dearth of automation data, future work conducted when …

Memory Constraints In Cued-Recall-Dependent Learning And Performance Tasks: Why Do Humans Struggle With Simple Yet Memory-Intensive Tasks?, Jack L. Burgess

Dartmouth College Undergraduate Theses

This study explores how various constraints on a computer agent's memory and recall capacities affect how it performs a simple reinforcement learning task: the card-matching memory game "Concentration". Existing computer agents can solve this task easily, but humans struggle with it, even though its rules and objectives are simple. Why is this the case? We identify specific human memory limitations that may be at play: decaying of memories over time and remembering broad characteristics of card locations and faces while forgetting card specifics. Through building and testing a reinforcement learning agent with these human-like memory constraints, we find that they …

Regression-Based Motion Planning, Josiah K. Putman

Dartmouth College Undergraduate Theses

This thesis explores two novel approaches to sample-based motion planning that utilize regressions as continuous function approximations to reduce the memory cost of planning. The first approach, Field Search Trees (FST) provides a solution for single-start planning by iteratively building local regressions of the cost-to-arrive function. The second approach, the Regression Complex (RC), constructs a complex of cells with each cell containing a regression of the distance between any two points on its boundary, creating a useful data structure for any start and goal planning query. We provide formal definitions of both approaches and experimental results of running the algorithms …

On Session Languages, Prashant Anantharaman, Sean W. Smith

Computer Science Technical Reports

The LangSec approach defends against crafted input attacks by defining a formal language specifying correct inputs and building a parser that decides that language. However, each successive input is not necessarily in the same basic language---e.g., most communication protocols use formats that depend on values previously received, or on some other additional context. When we try to use LangSec in these real-world scenarios, most parsers we write need additional mechanisms to change the recognized language as the execution progresses. This paper discusses approaches researchers have previously taken to build parsers for such protocols and provides formal descriptions of new sets …

A Clustering Algorithm For Early Prediction Of Controversial Reddit Posts, Abenezer Daniel Dara

Dartmouth College Undergraduate Theses

Social curation platforms like Reddit are rich with user interactions such as comments, upvotes, and downvotes. Predicting these interactions before they happen is an interesting computational challenge and can be used for a variety of tasks, ranging from content moderation to personality prediction. Given the vast amount of information posted on these sites, it's important to develop models that can simplify this prediction task. In this paper, we present a simple clustering algorithm that helps predict the controversiality of a Reddit post using the user's profile information, their past contributions on Reddit, and the sentiment expressed in their post. On …

A Critical Audit Of Accuracy And Demographic Biases Within Toxicity Detection Tools, Jiachen Jiang

Dartmouth College Undergraduate Theses

The rise of toxicity and hate speech on social media has become a cause for concern due to their effects on politics and the growth of extremist internet communities. The tools currently used to identify and eliminate harmful content have received widespread criticism from both the public and the academic community for their inaccuracies and biases. In our research, we set out to audit the performance of Perspective API, a toxicity detector created by research teams at Google and Jigsaw, on the language of users across a variety of demographic categories. We draw from Crenshaw's framework of intersectionality to discuss …

Defense In Depth Of Resource-Constrained Devices, Ira Ray Jenkins

Dartmouth College Ph.D Dissertations

The emergent next generation of computing, the so-called Internet of Things (IoT), presents significant challenges to security, privacy, and trust. The devices commonly used in IoT scenarios are often resource-constrained with reduced computational strength, limited power consumption, and stringent availability requirements. Additionally, at least in the consumer arena, time-to-market is often prioritized at the expense of quality assurance and security. An initial lack of standards has compounded the problems arising from this rapid development. However, the explosive growth in the number and types of IoT devices has now created a multitude of competing standards and technology silos resulting in a …

Bridging The Gap Between Intent And Outcome: Knowledge, Tools & Principles For Security-Minded Decision-Making, Vijay Harshed Kothari

Dartmouth College Ph.D Dissertations

Well-intentioned decisions---even ones intended to improve aggregate security--- may inadvertently jeopardize security objectives. Adopting a stringent password composition policy ostensibly yields high-entropy passwords; however, such policies often drive users to reuse or write down passwords. Replacing URLs in emails with "safe" URLs that navigate through a gatekeeper service that vets them before granting user access may reduce user exposure to malware; however, it may backfire by reducing the user's ability to parse the URL or by giving the user a false sense of security if user expectations misalign with the security checks delivered by the vetting process. A short timeout …

Digital Legacies For Digital Natives, Katie Goldstein

Dartmouth College Undergraduate Theses

Our identities are becoming increasingly digital.As technology continues to advance and digital content begins to either encapsulate or provide the basis for much of our lives, it must also accommodate one's preference to highlight or conceal specific digital content post-mortem.This paper presents a summary of a two-term long study regarding the creation and implementation of a design prototype that allowed users the ability to aggregate and cultivate one's digital content, empowering users to control the narrative of their own legacies through the very medium that helped to create them - technology.Over the course of two ethnographic studies, I surveyed 20 …

Distributed Iot Attestation Via Blockchain (Extended Version), Ira Ray Jenkins, Sean W. Smith

Computer Science Technical Reports

The growing number and nature of Internet of Things (IoT) devices makes these resource-constrained appliances particularly vulnerable and increasingly impactful in their exploitation. Current estimates for the number of connected "things" commonly reach the tens of billions. The low-cost and limited computational strength of these devices can preclude security features. Additionally, economic forces and a lack of industry expertise in security often contribute to a rush to market with minimal consideration for security implications. It is essential that users of these emerging technologies, from consumers to IT professionals, be able to establish and retain trust in the multitude of diverse …

The Application Of Digital Health To The Assessment And Treatment Of Substance Use Disorders: The Past, Current, And Future Role Of The National Drug Abuse Treatment Clinical Trials Network, Lisa A. Marsch, Aimee Campbell, Cynthia Campbell, Ching-Hua Chen, Emre Ertin, Udi Ghitza, Chantal Lambert-Harris, Saeed Hassanpour, August F. Holtyn, Yih-Ing Hser, Petra Jacobs, Jeffrey D. Klausner, Shea Lemley, David Kotz, Andrea Meier, Bethany Mcleman, Jennifer Mcneely, Varun Mishra, Larissa Mooney, Edward Nunes, Chrysovalantis Stafylis, Catherine Stanger, Elizabeth Saunders, Geetha Subramaniam, Sean Young

Dartmouth Scholarship

The application of digital technologies to better assess, understand, and treat substance use disorders (SUDs) is a particularly promising and vibrant area of scientific research. The National Drug Abuse Treatment Clinical Trials Network (CTN), launched in 1999 by the U.S. National Institute on Drug Abuse, has supported a growing line of research that leverages digital technologies to glean new insights into SUDs and provide science-based therapeutic tools to a diverse array of persons with SUDs.

This manuscript provides an overview of the breadth and impact of research conducted in the realm of digital health within the CTN. This work has …

Apparatus For Securely Configuring A Target Device And Associated Methods, Timothy J. Pierson, Xiaohui Liang, Ronald Peterson, David Kotz

Other Faculty Materials

Apparatus and method securely transfer first data from a source device to a target device. A wireless signal having (a) a higher speed channel conveying second data and (b) a lower speed channel conveying the first data is transmitted. The lower speed channel is formed by selectively transmitting the wireless signal from one of a first and second antennae of the source device based upon the first data. The first and second antenna are positioned a fixed distance apart and the target device uses a received signal strength indication (RSSI) of the first signal to decode the lower speed channel …

Workshop On The Development And Evaluation Of Digital Therapeutics For Health Behavior Change: Science, Methods, And Projects, Alan J. Budney, Lisa A. Marsch, Will M. Aklin, Jacob T. Borodovsky, Mary F. Brunette, Andrew T. Campbell, Jesse Dallery, David Kotz, Ashley A. Knapp, Sarah E. Lord, Edward V. Nunes, Emily A. Scherer, Catherine Stanger, William C. Torrey

Dartmouth Scholarship

The health care field has integrated advances into digital technology at an accelerating pace to improve health behavior, health care delivery, and cost-effectiveness of care. The realm of behavioral science has embraced this evolution of digital health, allowing for an exciting roadmap for advancing care by addressing the many challenges to the field via technological innovations. Digital therapeutics offer the potential to extend the reach of effective interventions at reduced cost and patient burden and to increase the potency of existing interventions. Intervention models have included the use of digital tools as supplements to standard care models, as tools that …

Data-Driven Personalized Applications In Networks, Chuankai An

Dartmouth College Ph.D Dissertations

A network models relationships. For a network that either encodes or supports internal information sharing activities, a better understanding of the network may enable data-driven applications (e.g., social network based recommendation), and boost both descriptive and predictive modeling of information flow in itself. In a multi-faceted manner, we propose in this thesis to contribute to several challenges that arise in the development of personalized applications in the general area of information and networks: 1) articulation of new patterns (and associated metrics) for individual user behavior and network structure; 2) exploitation of new forms of feature vector representations derived from large …

Stylized 2d Fabrication Of Non-Photorealistic Images, Athina Panotopoulou

Dartmouth College Ph.D Dissertations

A current trend in computer graphics is the use of programmable tools that allow non-experts to engage in the design of physical prototypes. Within fabrication, one area of research focuses on non-photorealistic images which are stylized to depict a particular aesthetic quality or convey key information. In cases where authenticity is demanded or the images need to be manipulated, fabrication is necessary. Non-photorealistic image fabrication involves two challenges: identifying and abstracting key information during design and considering material restrictions during fabrication. This thesis showcases two examples for fabricating new types of non-photorealistic images, the first involving watercolors, and the second …

Feasibility And Acceptability Of A Rural, Pragmatic, Telemedicine‐ Delivered Healthy Lifestyle Programme, John A. Batsis, Auden C. Mcclure, Aaron B. Weintraub, David F. Kotz, Sivan Rotenberg, Summer B. Cook, Diane Gilbert-Diamond, Kevin Curtis, Courtney J. Stevens, Diane Sette, Richard I. Rothstein

Dartmouth Scholarship

Background: The public health crisis of obesity leads to increasing morbidity that are even more profound in certain populations such as rural adults. Live, two‐way video‐conferencing is a modality that can potentially surmount geographic barriers and staffing shortages. Methods: Patients from the Dartmouth‐Hitchcock Weight and Wellness Center were recruited into a pragmatic, single‐arm, nonrandomized study of a remotely delivered 16‐week evidence‐based healthy lifestyle programme. Patients were provided hardware and appropriate software allowing for remote participation in all sessions, outside of the clinic setting. Our primary outcomes were feasibility and acceptability of the telemedicine intervention, as well as potential effectiveness on …

Exploring The State-Of-Receptivity For Mhealth Interventions, Florian Künzler, Varun Mishra, Jan-Niklas Kramer, David Kotz, Elgar Fleisch, Tobias Kowatsch

Dartmouth Scholarship

Recent advancements in sensing techniques for mHealth applications have led to successful development and deployments of several mHealth intervention designs, including Just-In-Time Adaptive Interventions (JITAI). JITAIs show great potential because they aim to provide the right type and amount of support, at the right time. Timing the delivery of a JITAI such as the user is receptive and available to engage with the intervention is crucial for a JITAI to succeed. Although previous research has extensively explored the role of context in users’ responsiveness towards generic phone notiications, it has not been thoroughly explored for actual mHealth interventions. In this …