Abstract Bipartite graphs are commonly used to visualize objects and their features. An object may possess several features and several objects may share a common feature. The standard visualization of bipartite graphs, with objects and features on two (say horizontal) parallel lines at integer coordinates and edges drawn as line segments, can often be difficult to work with. A common task in visualization of such graphs is to consider one object and all its features. This naturally defines a drawing window, defined as the smallest interval that contains the x-coordinates of the object and all its features. We show that if both objects and features can be reordered, minimizing the average window size is NP-hard. However, if the features are fixed, then we provide an efficient polynomial-time algorithm for arranging the objects, so as to minimize the average window size. Finally, we introduce a different way of visualizing the bipartite graph, by placing the nodes of the two parts on two concentric circles. For this setting we also show NP-hardness for the general case and a polynomial-time algorithm when the features are fixed.

Over 2 million people across the United States are living with aphasia, the loss of language due to acquired brain injury. Aphasia is an invisible disability that may come with negative consequences for communication, community participation, and quality of life. Game-based rehabilitation is a promising solution to address unmet long-term recovery and psychosocial needs for people with aphasia. In this paper, we describe a participatory game design process that engages people with aphasia (PwA) in the creation of three hybrid digital-analog games. We detail methods for facilitating collaboration across language barriers and divergent professional expertise based on interviews and participant observations throughout our iterative design process. We also contribute a set of design principles synthesized from aphasia rehabilitation research, interviews and community data. We conclude with recommendations for pursuing community-empowered aphasia game design for this underserved population based on reflection from our co-design experience.

We consider the problem of monitoring the interference among a collection of entities moving with bounded speed in d-dimensional Euclidean space. Uncertainty in entity locations due to unmonitored and unpredictable motion gives rise to a space of possible entity configurations at each moment in time, with possibly very different interference properties. We define different measures of what we call the interference potential of such spaces to describe the interference that might actually occur. We study the extent to which restricted monitoring frequency impacts interference potential, through the analysis of a clairvoyant scheme (one that knows the trajectories of all entities) subject to the same monitoring frequency restriction. This forms a benchmark for the analysis of uninformed schemes. In this framework, we describe and analyse an adaptive monitoring scheme for minimizing interference potential over time that is competitive (to within a constant factor) with any other scheme (in particular, a clairvoyant scheme) over modest sized time intervals. As a natural application, imagine that the entities are transmission sources, with associated broadcast ranges, moving in three dimensions. Two such entities, transmitting on the same channel, interfere if their broadcast ranges intersect. Uncertainty in the location of a transmission source effectively expands its broadcast range to a potential broadcast range. The chromatic number of the intersection graph of these potential broadcast ranges, one of our interference potential measures, gives the minimum number of broadcast channels required to avoid interference. Our scheme provides the foundation of an adaptive, locally updated, channel assignment algorithm that is competitive over time, in terms of the number of broadcast channels used with a fixed monitoring frequency, with any other such scheme.

We study the problem of maintaining knowledge of the locations of $n$ entities that are moving, each with some, possibly different, upper bound on their speed. We assume a setting where we can query the current location of any one entity, but this query takes a unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we wish to minimize uncertainty concerning the locations of all entities at some target time that is t units in the future. We measure uncertainty by the ply of the potential locations: the maximum over all points $x$ of the number of entities that could potentially be at $x$. Since the ply could be large for every query strategy, we analyze the performance of our query strategy in a competitive framework: we consider the worst-case ratio of the ply achieved by our strategy to the intrinsic ply (the smallest ply achievable by any strategy, even one that knows in advance the full trajectories of all entities). We describe an efficient strategy that, knowing only an upper bound on the speed of individual entities, is $O(k)$-competitive, provided the lead time t is at least 2n and the number of different entity speed classes (groups of entities whose speed bounds differ by at most a factor of two) is at most $k$. (This contrasts with the fact that, even given the full trajectories, the problem of computing the intrinsic ply is NP-hard.) If t is small, though at least $n$, and the entities move in any constant dimension $d$, our strategy is $O(k(\frac{\widetilde{T}}{n})^{d-\frac{d}{d+1}})$-competitive, where $\widetilde{T}$ is the median of the lengths of time since the $n$ entity locations were last known precisely. Matching lower bounds demonstrate that our strategy, in all cases, is optimally competitive, up to constant factors.

We study the problem of maintaining the locations of a collection of n entities that are moving with some fixed upper bound on their speed. We assume a setting where we may query the current location of entities, but handling this query takes a certain unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we maintain a representation of the potential locations of all entities. We measure the quality of this representation by its ply: the maximum over all points p of the number of entities that could potentially be at p.

The spanning ratio of a graph defined on n points in the Euclidean plane is the maximum ratio over all pairs of data points (u,v) of the minimum graph distance between u and v divided by the Euclidean distance between u and v. A connected graph is said to be an S-spanner if the spanning ratio does not exceed S. For example, for any S there exists a point set whose minimum spanning tree isnot an S-spanner. At the other end of the spectrum, a Delaunay triangulation is guaranteed to be a 2.42-spanner [J. M. Keil and C. A. Gutwin, Discrete Comput. Geom., 7 (1992), pp. 13-28]. For proximity graphs between these two extremes, such as Gabriel graphs [K. R. Gabriel and R. R. Sokal, Systematic Zoology, 18 (1969), pp. 259-278], relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268], and $\beta$-skeletons [D. G. Kirkpatrick and J. D. Radke, Comput. Geom., G. T. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217-248] with $\beta$ in [0,2] some interesting questions arise. We show that the spanning ratio for Gabriel graphs (which are $\beta$-skeletons with $\beta$ = 1) is $\Theta ( \sqrt{n})$ in the worst case. For all $\beta$-skeletons with $\beta$ in [0,1], we prove that the spanning ratio is at most $O(n^\gamma)$, where $\gamma = (1-\log_2(1+\sqrt{1-\beta^2}))/2$. For all $\beta$-skeletons with $\beta$ in [1,2], we prove that there exist point sets whose spanning ratio is at least $\left( \frac{1}{2} - o(1) \right) \sqrt{n} $. For relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268] (skeletons with $\beta$ = 2), we show that there exist point sets where the spanning ratio is $\Omega(n)$. For points drawn independently from the uniform distribution on the unit square, we show that the spanning ratio of the (random) Gabriel graph and all $\beta$-skeletons with $\beta$ in [1,2] tends to $\infty$ in probability as $\sqrt{\log n / \log \log n}$.

We establish tight bounds on the intrinsic cost (either minimizing delay d for fixed sender and receiver bandwidths, or minimizing sender bandwidth for fixed delay and receiver bandwidth) of broadcasting a video of length m over a channel of bandwidth S in such a way that a receiver (with bandwidth R ), starting at an arbitrary time s , can download the video so that it can begin playback at time s + d .Our bounds are realized by a simple just-in-time protocol that partitions the video into a fixed number of segments, partitions the sender bandwidth into an equivalent number of equal bandwidth subchannels, and broadcasts each segment repeatedly on its own subchannel. The protocol is suitable for the broadcast of compressed video and it can be implemented so that video information is packaged into discrete fixed length packets incurring only a modest overhead (measured in terms of increased delay).Our primary contribution is a lower bound on the required delay that applies to all protocols. This lower bound matches the behavior of our just-in-time protocol in the limit as the number of segments approaches infinity, provided the video compression satisfies some uniform upper bound. For a fixed number of segments, our protocol is optimal within a broad class of protocols, even if the video is compressed arbitrarily.

Many routing protocols have been developed to establish and maintain routes in mobile ad-hoc networks (MANETs). They try to address the unique challenges that MANETs present over traditional wired networks. Some of these challenges are: use of unreliable wireless medium for communication; frequent change in topology; lack of a central authority to arbitrate communication in the network. These protocols find a route to a destination, if such a route exists. However in the wireless medium, links are susceptible to frequent failures which can cause partitions in the network. Current routing protocols use a passive delivery approach for packets destined to a host in another partition. Packets destined to a disconnected host are dropped after some route repair attempts. The paper presents a novel protocol, Voila/spl grave/, that delivers messages across disconnected hosts. Voila/spl grave/ uses nodes moving between the source and destination partitions to act as carriers of messages. It uses a novel carrier select algorithm to select carrier nodes in the source partition.

We determine the precise threshold of component noise below which formulas composed of odd degree components can reliably compute all Boolean functions.

As computers are increasingly used in contexts where the amount of available memory is limited, it becomes important to devise techniques that reduce the memory footprint of application programs while leaving them in an executable form. This paper describes an approach to applying data compression techniques to reduce the size of infrequently executed portions of a program. The compressed code is decompressed dynamically (via software) if needed, prior to execution. The use of data compression techniques increases the amount of code size reduction that can be achieved; their application to infrequently executed code limits the runtime overhead due to dynamic decompression; and the use of software decompression renders the approach generally applicable, without requiring specialized hardware. The code size reductions obtained depend on the threshold used to determine what code is "infrequently executed" and hence should be compressed: for low thresholds, we see size reductions of 13.7% to 18.8%, on average, for a set of embedded applications, without excessive runtime overhead.

This paper describes the design and implementation of a method for producing compact, bytecoded instruction sets and interpreters for them. It accepts a grammar for programs written using a simple bytecoded stack-based instruction set, as well as a training set of sample programs. The system transforms the grammar, creating an expanded grammar that represents the same language as the original grammar, but permits a shorter derivation of the sample programs and others like them. A program's derivation under the expanded grammar forms the compressed bytecode representation of the program. The interpreter for this bytecode is automatically generated from the original bytecode interpreter and the expanded grammar. Programs expressed using compressed bytecode can be substantially smaller than their original bytecode representation and even their machine code representation. For example, compression cuts the bytecode for lcc from 199KB to 58KB but increases the size of the interpreter by just over 11KB. Categories and Subject Descriptors D.3.3 [Programming Languages]: Processors---optimization, run-time environments. General Terms Algorithms, Performance, Design, Economics, Experimentation, Languages, Theory. Keywords Program compression, bytecode interpretation, variable-to-fixed length codes, context-free grammars. 1.

Granularity is an integral feature of temporal data. For instance, a person's age is commonly given to the granularity of years and the time of their next airline flight to the granularity of minutes. A granularity creates a discrete image, in terms of granules, of a (possibly continuous) time-line. We present a formal model for granularity in temporal operations that is integrated with temporal indeterminacy, or "don't know when" information. We also minimally extend the syntax and semantics of SQL-92 to support mixed granularities. This support rests on two operations, scale and cast, that move times between granularities, e.g., from days to months. We demonstrate that our solution is practical by showing how granularities can be specified in a modular fashion, and by outlining a time- and space-efficient implementation. The implementation uses several optimization strategies to mitigate the expense of accommodating multiple granularities.

In recent years there has been an increasing trend toward the incorpor ation of computers into a variety of devices where the amount of memory available is limited. This makes it desirable to try to reduce the size of applications where possible. This article explores the use of compiler techniques to accomplish code compaction to yield smaller executables. The main contribution of this article is to show that careful, aggressive, interprocedural optimization, together with procedural abstraction of repeated code fragments, can yield significantly better reductions in code size than previous approaches, which have generally focused on abstraction of repeated instruction sequences. We also show how “equivalent” code fragments can be detected and factored out using conventional compiler techniques, and without having to resort to purely linear treatments of code sequences as in suffix-tree-based approaches, thereby setting up a framework for code compaction that can be more flexible in its treatment of what code fragments are considered equivalent. Our ideas have been implemented in the form of a binary-rewriting tool that reduces the size of executables by about 30% on the average.

The information carried by a signal decays when the signal is corrupted by random noise. This occurs when a message is transmitted over a noisy channel, as well as when a noisy component performs computation. We first study this signal decay in the context of communication and obtain a tight bound on the rate at which information decreases as a signal crosses a noisy channel. We then use this information theoretic result to obtain depth lower bounds in the noisy circuit model of computation defined by von Neumann. In this model, each component fails (produces 1 instead of 0 or vice-versa) independently with a fixed probability, and yet the output of the circuit is required to be correct with high probability. Von Neumann showed how to construct circuits in this model that reliably compute a function and are no more than a constant factor deeper than noiseless circuits for the function. We provide a lower bound on the multiplicative increase in circuit depth necessary for reliable computation, and an upper bound on the maximum level of noise at which reliable computation is possible.

Summary form only given. The reduction in storage size achieved by compressing a file translates directly into a reduction in transmission time when communicating the file. An increasingly common form of transmitted data is a computer program description. This paper examines the compression of source code, the high-level language representation of a program, using the language's context free grammar. We call the general technique guided parsing since it is a compression scheme based on predicting the behavior of a parser when it parses the source code and guiding its behavior by encoding its next action based on this prediction. In this paper, we describe the implementation and results of two very different forms of guided parsing. One is based on bottom-up parsing while the other is a top-down approach.

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 worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.

It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability E, then reliable computation can or cannot take place according as /spl epsiv/ is less than or greater than /spl epsiv//sub 0/=(3-/spl radic/7)/4=0.08856....

Current research in compiler optimization counts mainly CPU time and perhaps the first cache level or two. This view has been important but is becoming myopic, at least from a system-wide viewpoint, as the ratio of network and disk speeds to CPU speeds grows exponentially.For example, we have seen the CPU idle for most of the time during paging, so compressing pages can increase total performance even though the CPU must decompress or interpret the page contents. Another profile shows that many functions are called just once, so reduced paging could pay for their interpretation overhead.This paper describes:• Measurements that show how code compression can save space and total time in some important real-world scenarios.• A compressed executable representation that is roughly the same size as gzipped x86 programs and can be interpreted without decompression. It can also be compiled to high-quality machine code at 2.5 megabytes per second on a 120MHz Pentium processor• A compressed "wire" representation that must be decompressed before execution but is, for example, roughly 21% the size of SPARC code when compressing gcc.

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 Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.

We study the problem of inferring an accurate model for a stochastic process from its output.We identify two desirable properties -resoluteness and reliability -of any identification algorithm.We prove that for any countable class of stochastic processes, there is an identification algorithm that has these properties.This result also formulates an optimization problem whose solution is sufficent to solve the identification problem.In this sense, our result provides an analogue to the Occam principle in a probabilistic setting.

We study the decay of an information signal propagating through a series of noisy channels. We obtain exact bounds on such decay, and as a result provide a new lower bound on the depth of formulas with noisy components. This improves upon previous work of N. Pippenger (1988) and significantly decreases the gap between his lower bound and the classical upper bound of von Neumann. We also discuss connections between our work and the study of mixing rates of Markov chains.>

The notion of program checking is extended to include programs that alter their environment, in particular, programs that store and retrieve data from memory. The model considered allows the checker a small amount of reliable memory. The checker is presented with a sequence of requests (online) to a data structure which must reside in a large but unreliable memory. The data structure is viewed as being controlled by an adversary. The checker is to perform each operation in the input sequence using its reliable memory and the unreliable data structure so that any error in the operation of the structure will be detected by the checker with high probability. Checkers for various data structures are presented. Lower bounds of log n on the amount of reliable memory needed by these checkers, where n is the size of the structure, are proved.>