Physical Sciences and Mathematics Commons^™

An Undergraduate Consortium For Addressing The Leaky Pipeline To Computing Research, James C. Boerkoel Jr., Mehmet Ergezer

All HMC Faculty Publications and Research

Despite an increasing number of successful interventions designed to broaden participation in computing research, there is still significant attrition among historically marginalized groups in the computing research pipeline. This experience report describes a first-of-its-kind Undergraduate Consortium (UC; https://aaai-uc.github.io/about) that addresses this challenge by empowering students with a culmination of their undergraduate research in a conference setting. The UC, conducted at the AAAI Conference on Artificial Intelligence (AAAI), aims to broaden participation in the AI research community by recruiting students, particularly those from historically marginalized groups, supporting them with mentorship, advising, and networking as an accelerator toward graduate school, AI research, …

Quantifying Controllability In Temporal Networks With Uncertainty, James C. Boerkoel Jr., Lindsay Popowski, Michael Gao, Hemeng Li, Savana Ammons, Shyan Akmal

All HMC Faculty Publications and Research

Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We provide new insights inspired by a geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability - continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods …

Dynamic Control Of Probabilistic Simple Temporal Networks, James C. Boerkoel Jr., Michael Gao, Lindsay Popowski

All HMC Faculty Publications and Research

The controllability of a temporal network is defined as an agent’s ability to navigate around the uncertainty in its schedule and is well-studied for certain networks of temporal constraints. However, many interesting real-world problems can be better represented as Probabilistic Simple Temporal Networks (PSTNs) in which the uncertain durations are represented using potentially-unbounded probability density functions. This can make it inherently impossible to control for all eventualities. In this paper, we propose two new dynamic controllability algorithms that attempt to maximize the likelihood of successfully executing a schedule within a PSTN. The first approach, which we call MIN-LOSS DC, finds …

Digital Libraries For Open Science: Using A Socio-Technical Interaction Network Approach, Jennifer E. Beamer

Library Staff Publications and Research

This paper argues that using Socio-Technical Interaction Networks to build on extensively-used Digital Library infrastructures for supporting Open Science knowledge environments. Using a more social -technical approach could lead to an evolutionary reconceptualization of Digital Libraries. Digital Libraries being used as knowledge environments, built upon on the document repositories, will also emphasize the importance of user interaction and collaboration in carrying out those activities. That is to say, the primary goal of Digital Libraries is to help users convert information into knowledge; therefore, Digital Libraries examined in light of socio-technical interaction networks have the potential to shift Digital Libraries from …

Improving Image Clustering Using Sparse Text And The Wisdom Of The Crowds, Anna Ma, Arjuna Flenner, Deanna Needell, Allon G. Percus

CMC Faculty Publications and Research

We propose a method to improve image clustering using sparse text and the wisdom of the crowds. In particular, we present a method to fuse two different kinds of document features, image and text features, and use a common dictionary or “wisdom of the crowds” as the connection between the two different kinds of documents. With the proposed fusion matrix, we use topic modeling via non-negative matrix factorization to cluster documents.

Kaczmarz Algorithm With Soft Constraints For User Interface Layout, Noreen Jamil, Deanna Needell, Johannes Muller, Christof Lutteroth, Gerald Weber

CMC Faculty Publications and Research

The Kaczmarz method is an iterative method for solving large systems of equations that projects iterates orthogonally onto the solution space of each equation. In contrast to direct methods such as Gaussian elimination or QR-factorization, this algorithm is efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. However, the Kaczmarz method as described in the literature has its limitations: it considers only equality constraints and does not support soft constraints, which makes it inapplicable to the UI layout problem.

In this paper we extend the Kaczmarz method for solving specifications containing soft constraints, …

Signal Space Cosamp For Sparse Recovery With Redundant Dictionaries, Mark A. Davenport, Deanna Needell, Michael B. Wakin

CMC Faculty Publications and Research

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well conditioned, but these approaches fail to address the case of a truly …

Using Correlated Subset Structure For Compressive Sensing Recovery, Atul Divekar, Deanna Needell

CMC Faculty Publications and Research

Compressive sensing is a methodology for the reconstruction of sparse or compressible signals using far fewer samples than required by the Nyquist criterion. However, many of the results in compressive sensing concern random sampling matrices such as Gaussian and Bernoulli matrices. In common physically feasible signal acquisition and reconstruction scenarios such as super-resolution of images, the sensing matrix has a non-random structure with highly correlated columns. Here we present a compressive sensing recovery algorithm that exploits this correlation structure. We provide algorithmic justification as well as empirical comparisons.

Stable Image Reconstruction Using Total Variation Minimization, Deanna Needell, Rachel Ward

CMC Faculty Publications and Research

This article presents near-optimal guarantees for stable and robust image recovery from undersampled noisy measurements using total variation minimization. In particular, we show that from O(s log(N)) nonadaptive linear measurements, an image can be reconstructed to within the best s-term approximation of its gradient up to a logarithmic factor, and this factor can be removed by taking slightly more measurements. Along the way, we prove a strengthened Sobolev inequality for functions lying in the null space of suitably incoherent matrices.

Virtual Machine Workloads: The Case For New Nas Benchmarks, Vasily Tarasov, Dean Hildebrand, Geoffrey H. Kuenning, Erez Zadok

All HMC Faculty Publications and Research

Network Attached Storage (NAS) and Virtual Machines (VMs) are widely used in data centers thanks to their manageability, scalability, and ability to consolidate resources. But the shift from physical to virtual clients drastically changes the I/O workloads to seen on NAS servers, due to guest file system encapsulation in virtual disk images and the multiplexing of request streams from different VMs. Unfortunately, current NAS workload generators and benchmarks produce workloads typical to physical machines.

This paper makes two contributions. First, we studied the extent to which virtualization is changing existing NAS workloads. We observed significant changes, including the disappearance of …

Exploring The Baccalaureate Origin Of Domestic Ph.D. Students In Computing Fields, Susanne Hambrusch, Ran Libeskind-Hadas, Fen Zhao, David Rabson, Amy Csizmar Dalal, Ed Fox, Charles Isbell, Valerie Taylor

All HMC Faculty Publications and Research

Increasing the number of US students entering graduate school and receiving a Ph.D. in computer science is a goal as well as a challenge for many US Ph.D. granting institutions. Although the total computer science Ph.D. production in the U.S. has doubled between 2000 and 2010 (Figure 1), the fraction of domestic students receiving a Ph.D. from U.S. graduate programs has been below 50% since 2003 (Figure 2).

The goal of the Pipeline Project of CRA-E (PiPE) is to better understand the pipeline of US citizens and Permanent Residents (henceforth termed domestic students ) who apply, matriculate, and graduate from …

School Choice As A One-Sided Matching Problem: Cardinal Utilities And Optimization, Sinan Aksoy, Alexander Adam Azzam, Chaya Coppersmith, Julie Glass, Gizem Karaali, Xueying Zhao, Xinjing Zhu

Pomona Faculty Publications and Research

The school choice problem concerns the design and implementation of matching mechanisms that produce school assignments for students within a given public school district. Previously considered criteria for evaluating proposed mechanisms such as stability, strategyproofness and Pareto efficiency do not always translate into desirable student assignments. In this note, we explore a class of one-sided, cardinal utility maximizing matching mechanisms focused exclusively on student preferences. We adapt a well-known combinatorial optimization technique (the Hungarian algorithm) as the kernel of this class of matching mechanisms. We find that, while such mechanisms can be adapted to meet desirable criteria not met by …

On The Hardness Of Counting And Sampling Center Strings, Christina Boucher, Mohamed Omar

All HMC Faculty Publications and Research

Given a set S of n strings, each of length ℓ, and a nonnegative value d, we define a center string as a string of length ` that has Hamming distance at most d from each string in S. The #CLOSEST STRING problem aims to determine the number of center strings for a given set of strings S and input parameters n, ℓ, and d. We show #CLOSEST STRING is impossible to solve exactly or even approximately in polynomial time, and that restricting #CLOSEST STRING so that any one of the parameters n, ℓ, or d is fixed leads to …

The Cophylogeny Reconstruction Problem Is Np-Complete, Yaniv J. Ovadia '10, Daniel Fielder '11, Chris Conow, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

The cophylogeny reconstruction problem arises in the study of host-parasite relationships. Specif- ically, we are given a host tree H, a parasite tree P, and a function ' mapping the leaves (extant taxa) of P to the leaves of H. Four biologically plausible operations are considered: cospeciation, duplication, host switching, and loss (Figure 1). A host switch is permitted in conjunction with a duplication event but not with a cospeciation event [1].

Mixed Operators In Compressed Sensing, Matthew A. Herman, Deanna Needell

CMC Faculty Publications and Research

Applications of compressed sensing motivate the possibility of using different operators to encode and decode a signal of interest. Since it is clear that the operators cannot be too different, we can view the discrepancy between the two matrices as a perturbation. The stability of L1-minimization and greedy algorithms to recover the signal in the presence of additive noise is by now well-known. Recently however, work has been done to analyze these methods with noise in the measurement matrix, which generates a multiplicative noise term. This new framework of generalized perturbations (i.e., both additive and multiplicative noise) extends the prior …

Jane: A New Tool For The Cophylogeny Reconstruction Problem, Chris Conow, Daniel Fielder '11, Yaniv J. Ovadia '10, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

Background

This paper describes the theory and implementation of a new software tool, called Jane, for the study of historical associations. This problem arises in parasitology (associations of hosts and parasites), molecular systematics (associations of orderings and genes), and biogeography (associations of regions and orderings). The underlying problem is that of reconciling pairs of trees subject to biologically plausible events and costs associated with these events. Existing software tools for this problem have strengths and limitations, and the new Jane tool described here provides functionality that complements existing tools.

Results

The Jane software tool uses a polynomial time dynamic …

Local Versus Global Search In Channel Graphs, A.H. Hunter, Nicholas Pippenger

All HMC Faculty Publications and Research

Previous studies of search in channel graphs has assumed that the search is global; that is, that the status of any link can be probed by the search algorithm at any time. We consider for the first time local search, for which only links to which an idle path from the source has already been established may be probed. We show that some well known channel graphs may require exponentially more probes, on the average, when search must be local than when it may be global.

Learning To Create Jazz Melodies Using Deep Belief Nets, Greg Bickerman '10, Sam Bosley, Peter Swire, Robert M. Keller

All HMC Faculty Publications and Research

We describe an unsupervised learning technique to facilitate automated creation of jazz melodic improvisation over chord sequences. Specifically we demonstrate training an artificial improvisation algorithm based on unsupervised learning using deep belief nets, a form of probabilistic neural network based on restricted Boltzmann machines. We present a musical encoding scheme and specifics of a learning and creational method. Our approach creates novel jazz licks, albeit not yet in real-time. The present work should be regarded as a feasibility study to determine whether such networks could be used at all. We do not claim superiority of this approach for pragmatically creating …

The Effects Of Linguistic Features And Evaluation Perspective On Perceived Difficulty Of Medical Text, Gondy Leroy, Stephen Helmreich, James Cowie

CGU Faculty Publications and Research

Millions of laypersons need more medical information than they are customarily provided during their doctor’s visit. Health websites can help fill this knowledge gap, but the text is believed to be too difficult to understand for many laypersons. To help write text that is not perceived as too difficult and leads to better comprehension (actual difficulty), we study how linguistic structures influence text difficulty. Since perceived difficulty has been shown to be a barrier to self-education, evaluating perceived difficulty is an essential first step to take. In this study, we evaluated the impact of noun phrase complexity and of function …

Integrating Environmental Science Into Information Technology Content To Generate Student Interest, Rondalynne Mcclintock '13, Yoonmi Lee '12, June Hilton '04, Brian Hilton, Gondy Leroy

CGU Faculty Publications and Research

In an effort to increase female student interest in computing we applied and evaluated an interdisciplinary approach at a suburban high school in eastern Los Angeles County, California. Three classes, an IB Environmental Science class, an AP Environmental Science class, and a Computer Science were surveyed to assess attitude changes toward information technology. Results indicated gender differences between the participating classes, and differences before and after the project. Although the project did not uniformly impact the attitude of female high school students, it impacted teachers who are adjusting their teaching methods, an outcome that has a long-term positive influence.

A Life Cycle Perspective On Online Community Success, Alicia Iriberri '06, Gondy Leroy

CGU Faculty Publications and Research

Using the information systems lifecycle as a unifying framework, we review online communities research and propose a sequence for incorporating success conditions during initiation and development to increase their chances of becoming a successful community, one in which members participate actively and develop lasting relationships. Online communities evolve following distinctive lifecycle stages and recommendations for success are more or less relevant depending on the developmental stage of the online community. In addition, the goal of the online community under study determines the components to include in the development of a successful online community. Online community builders and researchers will benefit …

On The Computational Complexity Of The Reticulate Cophylogeny Reconstruction Problem, Ran Libeskind-Hadas, Michael A. Charleston

All HMC Faculty Publications and Research

The cophylogeny reconstruction problem is that of finding minimal cost explanations of differences between evolutionary histories of ecologically linked groups of biological organisms. We present a proof that shows that the general problem of reconciling evolutionary histories is NP-complete and provide a sharp boundary where this intractability begins. We also show that a related problem, that of finding Pareto optimal solutions, is NP-hard. As a byproduct of our results, we give a framework by which meta-heuristics can be applied to find good solutions to this problem.

Persuading Consumers To Form Precise Search Engine Queries, Gondy Leroy

CGU Faculty Publications and Research

Today’s search engines provide a single textbox for searching. This input method has not changed in decades and, as a result, consumer search behaviour has not changed either: few and imprecise keywords are used. Especially with health information, where incorrect information may lead to unwise decisions, it would be beneficial if consumers could search more precisely. We evaluated a new user interface that supports more precise searching by using query diagrams. In a controlled user study, using paper-based prototypes, we compared searching with a Google interface with drawing new or modifying template diagrams. We evaluated consumer willingness and ability to …

The Pixtalk Communication System A Smartphone Application And Companion Website For The Improvement Of Communication Skills Of Children With Autism, Gondy Leroy, Gianluca De Leo

CGU Faculty Publications and Research

No abstract provided.

A Different Pencil Too Good To Be Ignored? A First Look At Wolfram|Alpha, Gizem Karaali, Bruce Yoshiwara

Pomona Faculty Publications and Research

So you came across several news pieces about Wolfram|Alpha and you’re wondering what all the fuss is about. Let’s start with the basics.

Evaluating Online Health Information: Beyond Readability Formulas, Gondy Leroy, Stephen Helmreich, James Cowie, Trudi Miller '08, Wei Zheng '08

CGU Faculty Publications and Research

Although understanding health information is important, the texts provided are often difficult to understand. There are formulas to measure readability levels, but there is little understanding of how linguistic structures contribute to these difficulties. We are developing a toolkit of linguistic metrics that are validated with representative users and can be measured automatically. In this study, we provide an overview of our corpus and how readability differs by topic and source. We compare two documents for three groups of linguistic metrics. We report on a user study evaluating one of the differentiating metrics: the percentage of function words in a …

E-Transcript Web Services System Supporting Dynamic Conversion Between Xml And Edi, Myungjae Kwak '11, Woohyun Kang '14, Gondy Leroy, Samir Chatterjee

CGU Faculty Publications and Research

As XML becomes a standard for communications between distributed heterogeneous machines, many schools plan to implement Web Services systems using the XML e-transcript (electronic transcript) standard. We propose a framework that supports both XML e-transcript Web Services and existing EDI e-transcript systems. The framework uses the workflow engine to exploit the benefits of workflow management mechanisms. The workflow engine manages the e-transcript business process by enacting and completing the tasks and sub-processes within the main business process. We implemented the proposed framework by using various open source projects including Java, Eclipse, and Apache Software Foundation’s Web Services projects. Compared with …

Uniform Uncertainty Principle And Signal Recovery Via Regularized Orthogonal Matching Pursuit, Deanna Needell, Roman Vershynin

CMC Faculty Publications and Research

This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements—L1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of L1-minimization. Our algorithm, ROMP, reconstructs a sparse signal in a number of iterations linear in the sparsity, and the reconstruction is exact provided the linear measurements satisfy the uniform uncertainty principle.

Smartphones To Facilitate Communication And Improve Social Skills Of Children With Severe Autism Spectrum Disorder: Special Education Teachers As Proxies, Gondy Leroy, Gianluca De Leo

CGU Faculty Publications and Research

We present an overview of the approach we used and the challenges we encountered while designing software for smartphones to facilitate communication and improve social skills of children with severe autism spectrum disorder (ASD). We employed participatory design, using special education teachers of children with ASD as proxies for our target population.

The Motivators And Benefits Of Sharing Knowledge To A Kms Repository In An Omani Organization, Kamla Al-Busaidi '05, Lorne Olfman, Terry Ryan, Gondy Leroy

CGU Faculty Publications and Research

Knowledge is a powerful resource that enables individuals and organizations to achieve several benefits such as improved learning and decisionmaking. Repository knowledge management system (KMS) assists organizations to efficiently capture their knowledge for later reuse. However, the breadth and depth of a knowledge management system depends on the magnitude of knowledge contributed to the system. This paper aimed to empirically investigate the motivators of knowledge sharing behavior and the individual benefits of such behavior in a culture where knowledge is perceived as power and private. Based on 104 employees in a major private petroleum organization in Oman and the partial …