Digital Commons Network^™

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 …

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 …

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].

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 …

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.

Using Permuted States Of Validated Simulation To Analyze Conflict Rates In Optimistic Replication, An-I Andy Wang, Geoffrey H. Kuenning, Peter Reiher

All HMC Faculty Publications and Research

Optimistic replication provides high data availability in the presence of network outages. Although widely deployed, this relaxed consistency model introduces concurrent updates, whose behavior is poorly understood due to the vast state space.

This paper introduces the notion of permuted states to eliminate system states that are redundant and unreachable, which can constitute the majority of states (4069 out of 4096 for four replicas). With the aid of permuted states, we are for the first time able to construct analytical models beyond the two-replica case. By examining the analysis for 2 to 4 replicas, we can demystify the process of …

Grid-Enabling A Vibroacoustic Analysis Application, Brian Bentow, Jon Dodge, Aaron Homer, Christopher D. Moore, Robert M. Keller, Matthew T. Presley, Robert Davis, Jorge Seidel, Craig Lee, Joseph Betser

All HMC Faculty Publications and Research

This paper describes the process of grid-enabling a vibroacoustic analysis application using the Globus Toolkit 3.2.1. This is the first step in a project intended to grid-enable a suite of tools being developed as a service-oriented architecture for spacecraft telemetry analysis. Many of the applications in the suite are compute intensive and would benefit from significantly improved performance. In this paper we show the advantage of using Globus to grid-enable a single tool in a vibroacoustic analysis flow, with the result that using as few as eleven nodes, that tool’s runtime improved by a factor of eight. While communication overhead …

Srt Division Algorithms As Dynamical Systems, Mark Mccann, Nicholas Pippenger

All HMC Faculty Publications and Research

Sweeney--Robertson--Tocher (SRT) division, as it was discovered in the late 1950s, represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able …

Enabling Computer Decisions Based On Eeg Input, Benjamin J. Culpepper, Robert M. Keller

All HMC Faculty Publications and Research

Multilayer neural networks were successfully trained to classify segments of 12-channel electroencephalogram (EEG) data into one of five classes corresponding to five cognitive tasks performed by a subject. Independent component analysis (ICA) was used to segregate obvious artifact EEG components from other sources, and a frequency-band representation was used to represent the sources computed by ICA. Examples of results include an 85% accuracy rate on differentiation between two tasks, using a segment of EEG only 0.05 s long and a 95% accuracy rate using a 0.5-s-long segment.

The Computational Complexity Of Motion Planning, Jeff R.K. Hartline '01, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

In this paper we show that a generalization of a popular motion planning puzzle called Lunar Lockout is computationally intractable. In particular, we show that the problem is PSPACE-complete. We begin with a review of NP-completeness and polynomial-time reductions, introduce the class PSPACE, and motivate the significance of PSPACE-complete problems. Afterwards, we prove that determining whether a given instance of a generalized Lunar Lockout puzzle is solvable is PSPACE-complete.

Proof Without Words: The Pigeonhole Principle, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

This article contains one image and no text.

Multicast Communication In Circuit-Switched Optical Networks, Ran Libeskind-Hadas, Rami Melhem

All HMC Faculty Publications and Research

In this paper we examine the problem of multicast routing in Wavelength-division multiplexed (WDM) optical networks. In particular, we examine wavelength and routing assignment problems in circuit-switched WDM networks. We show that although the routing and wavelength assignment (RWA) problem is NP-complete in general, the wavelength assignment (WA) problem can be solevd in a polynomial time.

Optimal Token Allocations In Solitaire Knock 'M Down, Arthur Benjamin, Matthew T. Fluet, Mark L. Huber

All HMC Faculty Publications and Research

In the game Knock ’m Down, tokens are placed in N bins. At each step of the game, a bin is chosen at random according to a fixed probability distribution. If a token remains in that bin, it is removed. When all the tokens have been removed, the player is done. In the solitaire version of this game, the goal is to minimize the expected number of moves needed to remove all the tokens. Here we present necessary conditions on the number of tokens needed for each bin in an optimal solution, leading to an asymptotic solution. MR Subject Classifications: …

Efficient Multicast In Heterogeneous Networks Of Workstations, Ran Libeskind-Hadas, Jeff R.K. Hartline '01

All HMC Faculty Publications and Research

This paper studies the problem of efficient multicast in heterogeneous networks of workstations (HNOWs) using a parameterized communication model [3]. This model associates a sending overhead and a receiving overhead with each node as well as a network latency parameter. The problem of finding optimal multicasts in this model is known to be NP-complete in the strong sense. Nevertheless, we show that for two different properties that arise in typical HNOWs, provably near-optimal and optimal solutions, respectively, can be found in polynomial time. Specifically, we show the following two results: When the ratios of receiving overhead to sending overhead among …

Sorting In Parallel, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

In 1842, L.F. Menabrea anticipated the benefits of parallel computing in an article that appeared in the Swiss Journal Bibliotheque universelle de Geneve:

When a long series of identical computations is to be performed, such as those required for the formation of numerical tables, the machine can be brought into play so as to give several results at the same time, which will greatly abridge the whole amount of the processes.

Although more than a century passed before Menabrea's vision became a reality, today parallel computers with hundreds and even thousands of processors are used in a broad range …

Tree-Based Multicasting In Wormhole-Routed Irregular Topologies, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A deadlock-free tree-based multicast routing algorithm is presented for all direct networks, regardless of interconnection topology. The algorithm delivers a message to any number of destinations using only a single startup phase. In contrast to existing tree-based schemes, this algorithm applies to all interconnection topologies, requires only fixed-sized input buffers that are independent of maximum message length, and uses a single asynchronous flit replication mechanism. The theoretical basis of the technique used here is sufficiently general to develop other tree-based multicasting algorithms for regular and irregular topologies. Simulation results demonstrate that this tree-based algorithm provides a very promising means of …

Design And Design Centers In Engineering Education, Clive L. Dym

All HMC Faculty Publications and Research

This paper is intended to be the opening salvo of the workshop, Computing Futures in Engineering Design (Dym, 1997). Thus, I want to take this privileged moment to ask you to think with me about the role of design in engineering. In particular, I want to reflect upon how design is articulated and how design is taught; about the role of design in engineering education and in the practice of engineering; and about the role that could be played locally and, perhaps, nationally by a center devoted to design education. Because I teach here at Harvey Mudd College (HMC), …

Optimal Contention-Free Unicast-Based Multicasting In Switch-Based Networks Of Workstations, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A unicast-based multicasting algorithm is presented for arbitrary interconnection networks arising in switch-based networks of workstations. The algorithm is optimal with respect tot he number of startups incurred and is provably free from depth contention. Specifically, no two constituent unicasts for the same multicast contend for a common channel, even if some unicasts are delayed due to unpredictable variations in latencies. The algorithm uses an underlying partially adaptive deadlock-free unicast routing algorithm. Simulation results indicate that the algorithm behaves as predicted by its theoretical properties and provides a promising approach to unicast-based multicasting.

Average-Case Lower Bounds For Noisy Boolean Decision Trees, William Evans, Nicholas Pippenger

All HMC Faculty Publications and Research

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the …

Adaptive Multicast Routing In Wormhole Networks, Ran Libeskind-Hadas, Tom Hehre '96, Andrew Hutchings '98, Mark Reyes '98, Kevin Watkins '97

All HMC Faculty Publications and Research

Multicast communication has applications in a number of fundamental operations in parallel computing. An effective multicast routing algorithm must be free from both livelock and deadlock while minimizing communication latency. We describe two classes of multicast wormhole routing algorithms that employ the multi-destination wormhole hardware mechanism proposed by Lin et al. [12] and Panda et al. [17]. Specific examples of these classes of algorithms are described and experimental results suggests that such algorithms enjoy low communication latencies across a range of network loads.

Approximation Algorithms: Good Solutions To Hard Problems, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

Consider a computer network represented by an undirected graph where the vertices represent computer nodes and the edges represent links between the nodes. Since some of the links in the network may become faulty, link testing devices are placed at some of the nodes. A tester at a particular node can test all links incident to that node. Since the testers are expensive, however, we wish to deploy the minimum number of these devices such that every link is incidient to at least one node containing a tester. In graph theoretic terms, a vertex cover is a subset of the …

Disjoint Covers In Replicated Heterogeneous Arrays, P.K. Mckinley, N. Hasan, Ran Libeskind-Hadas, C.L. Liu

All HMC Faculty Publications and Research

Reconfigurable chips are fabricated with redundant elements that can be used to replace the faulty elements. The fault cover problem consists of finding an assignment of redundant elements to the faulty elements such that all of the faults are repaired. In reconfigurable chips that consist of arrays of elements, redundant elements are configured as spare rows and spare columns.

This paper considers the problem in which a chip contains several replicates of a heterogeneous array, one or more sets of spare rows, and one or more sets of spare columns. Each set of spare rows is identical to the set …

Selection Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

An upper bound asymptotic to $2n\log _e n$ is established for the number of comparators required in a network that classifies $n$ values into two classes, each containing $n / 2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n / 2)\log _2 n$.)

Faster Circuits And Shorter Formulas For Multiple Addition, Multiplication And Symmetric Boolean Functions, Michael Paterson, Uri Zwick, Nicholas Pippenger

All HMC Faculty Publications and Research

A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n1p+o(1)/, where p is the unique real number for which the Lp norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal …