Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Keyword
-
- Algorithms (3)
- Algorithm Design (2)
- Chromatic Number (2)
- Embeddings (2)
- Graph-Coloring (2)
-
- Heuristic Algorithms (2)
- NP-Hard (2)
- Reasoning (2)
- Scheduling (2)
- Speedup (2)
- Academic/Educational Applications (1)
- Approximation (1)
- Artificial intelligence (1)
- Bi-partite (1)
- Bibliography (1)
- Branch-And-Bound (1)
- Church-Rosser Property (1)
- Class NC (1)
- Class NG (1)
- Complete Sets of Reductions (1)
- Complexity Of Algorithms (1)
- Computer assisted instruction (1)
- Conant gasket (1)
- Concurrent Systems (1)
- Conditional Reductions (1)
- Conneced-Dense-Connected (1)
- Data Parallelism (1)
- Data Partitioning (1)
- Deep learning (1)
- Densest connected (1)
- Publication Year
- File Type
Articles 1 - 30 of 673
Full-Text Articles in Physical Sciences and Mathematics
Reasoning About The Conant Gasket, M. Douglas Mcilroy
Reasoning About The Conant Gasket, M. Douglas Mcilroy
Computer Science Technical Reports
Previously conjectured properties of the Conant gasket, a particular non-periodic tiling of the non-negative integer grid, are proved using new recurrences. A slabwise periodicity property is identified and proved. Further fractal properties are conjectured.
Eating Detection With A Head-Mounted Video Camera, Shengjie Bi, David Kotz
Eating Detection With A Head-Mounted Video Camera, Shengjie Bi, David Kotz
Computer Science Technical Reports
In this paper, we present a computer-vision based approach to detect eating. Specifically, our goal is to develop a wearable system that is effective and robust enough to automatically detect when people eat, and for how long. We collected video from a cap-mounted camera on 10 participants for about 55 hours in free-living conditions. We evaluated performance of eating detection with four different Convolutional Neural Network (CNN) models. The best model achieved accuracy 90.9% and F1 score 78.7% for eating detection with a 1-minute resolution. We also discuss the resources needed to deploy a 3D CNN model in wearable or …
On Mentzer’S Hardness Of The K-Center Problem On The Euclidean Plane., Raymond Chen
On Mentzer’S Hardness Of The K-Center Problem On The Euclidean Plane., Raymond Chen
Computer Science Technical Reports
An instance of the k-center problem consists of n points in a metric space along with a positive integer k. The goal is to find the smallest radius r such that there exists a subset of k centers picked among them such that every point is within distance r of at least one center. Stuart Mentzer (Mentzer, 1988) wrote a paper showing that in the Euclidean plane, it is NP-Hard to approximate this problem up to a factor of √2 +√3 ≈ 1.93. However, his report is missing some details. In this note, we present details of his full construction.
Improving Grading And Feedback Of Programming Assignments Using Version Control: An Experience Report, Jillian Morgan, Michael Weeks
Improving Grading And Feedback Of Programming Assignments Using Version Control: An Experience Report, Jillian Morgan, Michael Weeks
Computer Science Technical Reports
Leaving meaningful, actionable feedback that students will read and, most importantly, follow-up on, is essential for strengthening their programming skills. In addition, being capable with version control platforms, such as git, is a desired skill in industry. Could a marriage between the two, leaving meaningful feedback for student submissions in a version control system, lead them to be better programmers while improving the time and quality of instructors’ feedback? This experience report describes how we used GitHub Classroom for programming assignment submission and assessment in CS2. We provide examples of typical feedback using various assessment mechanisms, describe the process of …
Thaw Publications, Carl Landwehr, David Kotz
Thaw Publications, Carl Landwehr, David Kotz
Computer Science Technical Reports
In 2013, the National Science Foundation's Secure and Trustworthy Cyberspace program awarded a Frontier grant to a consortium of four institutions, led by Dartmouth College, to enable trustworthy cybersystems for health and wellness. As of this writing, the Trustworthy Health and Wellness (THaW) project's bibliography includes more than 130 significant publications produced with support from the THaW grant; these publications document the progress made on many fronts by the THaW research team. The collection includes dissertations, theses, journal papers, conference papers, workshop contributions and more. The bibliography is organized as a Zotero library, which provides ready access to citation materials …
On Session Languages, Prashant Anantharaman, Sean W. Smith
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 …
Distributed Iot Attestation Via Blockchain (Extended Version), Ira Ray Jenkins, Sean W. Smith
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 …
Finding Connected-Dense-Connected Subgraphs And Variants Is Np-Hard, Dhara Shah, Sushil Prasad, Yubao Wu
Finding Connected-Dense-Connected Subgraphs And Variants Is Np-Hard, Dhara Shah, Sushil Prasad, Yubao Wu
Computer Science Technical Reports
Finding Connected-Dense-Connected (CDC) subgraphs from Triple Networks is NP-Hard. finding One-Connected-Dense (OCD) sub- graphs from Triple Networks is also NP-Hard. We present formal proofs of these theorems hereby.
Finding Densest Subgraph In A Bi-Partite Graph, Dhara Shah, Sushil Prasad, Danial Aghajarian
Finding Densest Subgraph In A Bi-Partite Graph, Dhara Shah, Sushil Prasad, Danial Aghajarian
Computer Science Technical Reports
Finding the densest subgraph in a bi-partite graph is a polynomial time problem. Also, each bi-partite graph has a densest connected subgraph. In this paper, we first prove that each bi-partite graph has a densest connected subgraph. This proof is different than that of an undirected graph, since our definition of the density is different. We then provide a max-flow min-cut algorithm for finding a densest subgraph of a bi-partite graph and prove te correctness of this binary search algorithm.
Battery-Free Eye Tracker On Glasses, Tianxing Li, Xia Zhou
Battery-Free Eye Tracker On Glasses, Tianxing Li, Xia Zhou
Computer Science Technical Reports
This paper presents a battery-free wearable eye tracker that achieves sub-millimeter tracking accuracy at high tracking rates. It tracks both the 2D position and diameter of pupil based on pupil's light absorption property. With a few near-infrared (NIR) lights and photodiodes around the eye, NIR lights sequentially illuminate the eye from various directions while photodiodes sense spatial patterns of reflected light, which are used to infer pupil's position and diameter on the fly via a lightweight inference algorithm. The system also exploits characteristics of different eye movement stages and adjusts its sensing and computation accordingly for further energy savings. A …
Time-Space Tradeoffs For The Memory Game, Yining Chen, Amit Chakrabarti
Time-Space Tradeoffs For The Memory Game, Yining Chen, Amit Chakrabarti
Computer Science Technical Reports
A single-player game of Memory is played with n distinct pairs of cards, with the cards in each pair bearing identical pictures. The cards are laid face-down. A move consists of revealing two cards, chosen adaptively. If these cards match, i.e., they bear the same picture, they are removed from play; otherwise, they are turned back to face down. The object of the game is to clear all cards while minimizing the number of moves. Past works have thoroughly studied the expected number of moves required, assuming optimal play by a player has that has perfect memory. In this work, …
A Radiative Transfer Framework For Non-Exponential Media, Benedikt Bitterli, Srinath Ravichandran, Thomas Müller, Magnus Wrenninge, Jan Novák, Steve Marschner, Wojciech Jarosz
A Radiative Transfer Framework For Non-Exponential Media, Benedikt Bitterli, Srinath Ravichandran, Thomas Müller, Magnus Wrenninge, Jan Novák, Steve Marschner, Wojciech Jarosz
Computer Science Technical Reports
We develop a new theory of volumetric light transport for media with non-exponential free-flight distributions. Recent insights from atmospheric sciences and neutron transport demonstrate that such distributions arise in the presence of correlated scatterers, which are naturally produced by processes such as cloud condensation and fractal-pattern formation. Our theory accommodates correlations by disentangling the concepts of the free-flight distribution and transmittance, which are equivalent when scatterers are statistically independent, but become distinct when correlations are present. Our theory results in a generalized path integral which allows us to handle non-exponential media using the full range of Monte Carlo rendering algorithms …
Investigating Contextual Cues As Indicators For Ema Delivery, Varun Mishra, Byron Lowens, Sarah Lord, Kelly Caine, David Kotz
Investigating Contextual Cues As Indicators For Ema Delivery, Varun Mishra, Byron Lowens, Sarah Lord, Kelly Caine, David Kotz
Computer Science Technical Reports
In this work, we attempt to determine whether the contextual information of a participant can be used to predict whether the participant will respond to a particular Ecological Momentary Assessment (EMA) prompt. We use a publicly available dataset for our work, and find that by using basic contextual features about the participant's activity, conversation status, audio, and location, we can predict whether an EMA prompt triggered at a particular time will be answered with a precision of 0.647, which is significantly higher than a baseline precision of 0.410. Using this knowledge, the researchers conducting field studies can efficiently schedule EMA …
Stem Outreach Activity With Fitbit Wearable Devices, Joseph Carrigan, David Kotz, Aviel Rubin
Stem Outreach Activity With Fitbit Wearable Devices, Joseph Carrigan, David Kotz, Aviel Rubin
Computer Science Technical Reports
This document provides a toolkit for an STEM outreach activity based on Fitbit wearable fitness devices. The activity is targeted toward high-school students. This document provides guidance preparing for and executing the activity and measuring outcomes. This document contains templates that can be used as is or altered to suit your specific needs.
A Jpeg Corner Artifact From Directed Rounding Of Dct Coefficients, Shruti Agarwal, Hany Farid
A Jpeg Corner Artifact From Directed Rounding Of Dct Coefficients, Shruti Agarwal, Hany Farid
Computer Science Technical Reports
JPEG compression introduces a number of well known artifacts including blocking and ringing. We describe a lesser known or understood artifact consisting of a slightly darker or lighter pixel in the corner of 8 x 8 pixel blocks. This artifact is introduced by the directed rounding of DCT coefficients. In particular, we show that DCT coefficients that are uniformly rounded down or up (but not to the nearest neighbor) give rise to this artifact. An analysis of thousands of different camera models reveals that this artifact is present in approximately 61% of cameras. We also propose a simple filtering technique …
A Statistical Prior For Photo Forensics: Object Removal, Wei Fan, Hany Farid
A Statistical Prior For Photo Forensics: Object Removal, Wei Fan, Hany Farid
Computer Science Technical Reports
If we consider photo forensics within a Bayesian framework, then the probability that an image has been manipulated given the results of a forensic test can be expressed as a product of a likelihood term (the probability of a forensic test detecting manipulation given that an image was manipulated) and a prior term (the probability that an image was manipulated). Despite the success of many forensic techniques, the incorporation of a statistical prior has not been previously considered. We describe a framework for incorporating statistical priors into any forensic analysis and specifically address the problem of quantifying the probability that …
A Survey Of Trustworthy Computing On Mobile & Wearable Systems, Travis Peters
A Survey Of Trustworthy Computing On Mobile & Wearable Systems, Travis Peters
Computer Science Technical Reports
Mobile and wearable systems have generated unprecedented interest in recent years, particularly in the domain of mobile health (mHealth) where carried or worn devices are used to collect health-related information about the observed person. Much of the information - whether physiological, behavioral, or social - collected by mHealth systems is sensitive and highly personal; it follows that mHealth systems should, at the very least, be deployed with mechanisms suitable for ensuring confidentiality of the data it collects. Additional properties - such as integrity of the data, source authentication of data, and data freshness - are also desirable to address other …
Monte Carlo Convergence Analysis For Anisotropic Sampling Power Spectra, Gurprit Singh, Wojciech Jarosz
Monte Carlo Convergence Analysis For Anisotropic Sampling Power Spectra, Gurprit Singh, Wojciech Jarosz
Computer Science Technical Reports
Traditional Monte Carlo (MC) integration methods use point samples to numerically approximate the underlying integral. This approximation introduces variance in the integrated result, and this error can depend critically on the sampling patterns used during integration. Most of the well known samplers used for MC integration in graphics, e.g. jitter, Latin hypercube (n-rooks), multi-jitter, are anisotropic in nature. However, there are currently no tools available to analyze the impact of such anisotropic samplers on the variance convergence behavior of Monte Carlo integration. In this work, we propose a mathematical tool in the Fourier domain that allows analyzing the variance, and …
The Darklight Rises: Visible Light Communication In The Dark, Zhao Tian, Kevin Wright, Xia Zhou
The Darklight Rises: Visible Light Communication In The Dark, Zhao Tian, Kevin Wright, Xia Zhou
Computer Science Technical Reports
Visible Light Communication (VLC) emerges as a new wireless communication technology with appealing benefits not present in radio communication. However, current VLC designs commonly require LED lights to emit shining light beams, which greatly limits the applicable scenarios of VLC (e.g., in a sunny day when indoor lighting is not needed). It also entails high energy overhead and unpleasant visual experiences for mobile devices to transmit data using VLC. We design and develop DarkLight, a new VLC primitive that allows light-based communication to be sustained even when LEDs emit extremely-low luminance. The key idea is to encode data into ultra-short, …
Wanda: Securely Introducing Mobile Devices (Extended Version), Timothy J. Pierson, Xiaohui Liang, Ronald Peterson, David Kotz
Wanda: Securely Introducing Mobile Devices (Extended Version), Timothy J. Pierson, Xiaohui Liang, Ronald Peterson, David Kotz
Computer Science Technical Reports
Nearly every setting is increasingly populated with wireless and mobile devices -- whether appliances in a home, medical devices in a health clinic, sensors in an industrial setting, or devices in an office or school. There are three fundamental operations when bringing a new device into any of these settings: (1) to configure the device to join the wireless local-area network, (2) to partner the device with other nearby devices so they can work together, and (3) to configure the device so it connects to the relevant individual or organizational account in the cloud. The challenge is to accomplish all …
On The Multidimensional Stable Marriage Problem, Jared Duker Lichtman
On The Multidimensional Stable Marriage Problem, Jared Duker Lichtman
Computer Science Technical Reports
We provide a problem definition of the stable marriage problem for a general number of parties p under a natural preference scheme in which each person has simple lists for the other parties. We extend the notion of stability in a natural way and present so called elemental and compound algorithms to generate matchings for a problem instance. We demonstrate the stability of matchings generated by both algorithms, as well as show that the former runs in O(pn^2) time.
Mismorphism: A Semiotic Model Of Computer Security Circumvention (Extended Version), Sean W. Smith, R Koppel, J Blythe, V Kothari
Mismorphism: A Semiotic Model Of Computer Security Circumvention (Extended Version), Sean W. Smith, R Koppel, J Blythe, V Kothari
Computer Science Technical Reports
In real world domains, from healthcare to power to finance, we deploy computer systems intended to streamline and improve the activities of human agents in the corresponding non-cyber worlds. However, talking to actual users (instead of just computer security experts) reveals endemic circumvention of the computer-embedded rules. Good-intentioned users, trying to get their jobs done, systematically work around security and other controls embedded in their IT systems. This paper reports on our work compiling a large corpus of such incidents and developing a model based on semiotic triads to examine security circumvention. This model suggests that mismorphisms---mappings that fail to …
Tr-2015001: A Survey And Critique Of Facial Expression Synthesis In Sign Language Animation, Hernisa Kacorri
Tr-2015001: A Survey And Critique Of Facial Expression Synthesis In Sign Language Animation, Hernisa Kacorri
Computer Science Technical Reports
Sign language animations can lead to better accessibility of information and services for people who are deaf and have low literacy skills in spoken/written languages. Due to the distinct word-order, syntax, and lexicon of the sign language from the spoken/written language, many deaf people find it difficult to comprehend the text on a computer screen or captions on a television. Animated characters performing sign language in a comprehensible way could make this information accessible. Facial expressions and other non-manual components play an important role in the naturalness and understandability of these animations. Their coordination to the manual signs is crucial …
Optimistic And Parallel Ising Model Estimation, James Brofos, Rui Shu
Optimistic And Parallel Ising Model Estimation, James Brofos, Rui Shu
Computer Science Technical Reports
We consider a new method for estimating the structure of Ising graphical models from data. We assume that the data is observed with error, so that it is, in a sense, unreliable. We propose and investigate an ``optimistic'' estimator; that is, an approach that seeks to correct the log-likelihood objective function when some amount of the data is known to be mismeasured. We derive an interior point algorithm that constructs our estimator efficiently, and demonstrate that it leads naturally to a parallel procedure for recovering the graphical structure of Ising models. We show that the optimistic estimator has performance comparable …
Information-Theoretic Limits For Density Estimation, James Brofos
Information-Theoretic Limits For Density Estimation, James Brofos
Computer Science Technical Reports
This paper is concerned with the information-theoretical limits of density estimation for Gaussian random variables with data drawn independently and with identical distributions. We apply Fano's inequality to the space of densities and an arbitrary estimator. We derive necessary conditions on the sample size for reliable density recovery and for reliable density estimation. These conditions are true simultaneously for both finitely and infinitely dimensional density spaces.
An Assessment Of Single-Channel Emg Sensing For Gestural Input, Travis Peters
An Assessment Of Single-Channel Emg Sensing For Gestural Input, Travis Peters
Computer Science Technical Reports
Wearable devices of all kinds are becoming increasingly popular. One problem that plagues wearable devices, however, is how to interact with them. In this paper we construct a prototype electromyography (EMG) sensing device that captures a single channel of EMG sensor data corresponding to user gestures. We also implement a machine learning pipeline to recognize gestural input received via our prototype sensing device. Our goal is to assess the feasibility of using a BITalino EMG sensor to recognize gestural input on a mobile health (mHealth) wearable device known as Amulet. We conduct three experiments in which we use the EMG …
On Opportunity Cost Bounds For The Knowledge Gradient, James Brofos
On Opportunity Cost Bounds For The Knowledge Gradient, James Brofos
Computer Science Technical Reports
We prove an upper bound on the cumulative opportunity cost of the online knowledge gradient algorithm. We leverage the theory of martingales to yield a bound under the Gaussian assumption. Using results from information theory we are further able to provide asymptotic bounds on the cumulative opportunity cost with high probability.
Sculptflow: Visualizing Sculpting Sequences By Continuous Summarization, Jonathan D. Denning, Fabio Pellacini, Jiawei Ou
Sculptflow: Visualizing Sculpting Sequences By Continuous Summarization, Jonathan D. Denning, Fabio Pellacini, Jiawei Ou
Computer Science Technical Reports
Digital sculpting is becoming ubiquitous for modeling organic shapes like characters. Artists commonly show their sculpting sessions by producing timelapses or speedup videos. But the long length of these sessions make these visualizations either too long to remain interesting or too fast to be useful. In this paper, we present SculptFlow, an algorithm that summarizes sculpted mesh sequences by repeatedly merging pairs of subsequent edits taking into account the number of summarized strokes, the magnitude of the edits, and whether they overlap. Summaries of any length are generated by stopping the merging process when the desired length is reached. We …
3dflow: Continuous Summarization Of Mesh Editing Workflows, Jonathan D. Denning, Fabio Pellacini
3dflow: Continuous Summarization Of Mesh Editing Workflows, Jonathan D. Denning, Fabio Pellacini
Computer Science Technical Reports
Mesh editing software is continually improving allowing more detailed meshes to be create efficiently by skilled artists. Many of these are interested in sharing not only the final mesh, but also their whole workflows both for creating tutorials as well as for showcasing the artist's talent, style, and expertise. Unfortunately, while creating meshes is improving quickly, sharing editing workflows remains cumbersome since time-lapsed or sped-up videos remain the most common medium. In this paper, we present 3DFlow, an algorithm that computes continuous summarizations of mesh editing workflows. 3DFlow takes as input a sequence of meshes and outputs a visualization of …
Crosscomp: Comparing Multiple Artists Performing Similar Modeling Tasks, Jonathan D. Denning, Fabio Pellacini
Crosscomp: Comparing Multiple Artists Performing Similar Modeling Tasks, Jonathan D. Denning, Fabio Pellacini
Computer Science Technical Reports
In two previous papers, we have focused on summarizing and visualizing the edits of a single workflow and visualizing and merging the edits of two independent workflows. In this paper, we focus on visualizing the similarities and dissimilarities of many workflows where digital artists perform similar tasks. The tasks have been chosen so each artist starts and ends with a common state. We show how to leverage the previous work to produce a visualization tool that allows for easy scanning through the workflows.