Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.     

Learning to See: Making Sense of the Mathematics of Change in Middle School

In this article, we will describe the results of a study of 6th grade students learning about the mathematics of change. The students in this study worked with software environments for the computer and the graphing calculator that included a simulation of a moving elevator, linked to a graph of its velocity vs. time. We will describe how the students and their teacher negotiated the mathematical meanings of these representations, in interaction with the software and other representational tools available in the classroom. The class developed ways of selectively attending to specific features of stacks of centimeter cubes, hand-drawn graphs, and graphs (labeled velocity vs. time) on the computer screen. In addition, the class became adept at imagining the motions that corresponded to various velocity vs. time graphs. In this article, we describe this development as a process of learning to see mathematical representations of motion. The main question this article addresses is: How do students learn to see mathematical representations in ways that are consistent with the discipline of mathematics? This revised version was published online in July 2006 with corrections to the Cover Date.     

Bodies of constant width in arbitrary dimension

We give a number of characterizations of bodies of constant width in arbitrary dimension. As an application, we describe a way to construct a body of constant width in dimension n, one of its (n – 1)‐dimensional projection being given. We give a number of examples, like a four‐dimensional body of constant width whose 3D‐projection is the classical Meissner's body. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Proximality and Chebyshev sets

This paper is a companion to a lecture given at the Prague Spring School in Analysis in April 2006. It highlights four distinct variational methods of proving that a finite dimensional Chebyshev set is convex and hopes to inspire renewed work on the open question of whether every Chebyshev set in Hilbert space is convex.     

The Central Limit Problem for Random Vectors with Symmetries

Motivated by the central limit problem for convex bodies, we study normal approximation of linear functionals of high-dimensional random vectors with various types of symmetries. In particular, we obtain results for distributions which are coordinatewise symmetric, uniform in a regular simplex, or spherically symmetric. Our proofs are based on Stein’s method of exchangeable pairs; as far as we know, this approach has not previously been used in convex geometry. The spherically symmetric case is treated by a variation of Stein’s method which is adapted for continuous symmetries. This work was done while at Stanford University.     

Pattern Search Method for Discrete <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>–Approximation

We propose a pattern search method to solve a classical nonsmooth optimization problem. In a deep analogy with pattern search methods for linear constrained optimization, the set of search directions at each iteration is defined in such a way that it conforms to the local geometry of the set of points of nondifferentiability near the current iterate. This is crucial to ensure convergence. The approach presented here can be extended to wider classes of nonsmooth optimization problems. Numerical experiments seem to be encouraging. This work was supported by M.U.R.S.T., Rome, Italy.     

Families of Line-Graphs and Their Quantization

Any directed graph G with N vertices and J edges has an associated line-graph L(G) where the J edges form the vertices of L(G). We show that the non-zero eigenvalues of the adjacency matrices are the same for all graphs of such a family L ⁿ (G). We give necessary and sufficient conditions for a line-graph to be quantisable and demonstrate that the spectra of associated quantum propagators follow the predictions of random matrices under very general conditions. Line-graphs may therefore serve as models to study the semiclassical limit (of large matrix size) of a quantum dynamics on graphs with fixed classical behaviour.     

Global error bound for convex inclusion problems

The existence of global error bound for convex inclusion problems is discussed in this paper, including pointwise global error bound and uniform global error bound. The existence of uniform global error bound has been carefully studied in Burke and Tseng (SIAM J. Optim. 6(2), 265–282, 1996) which unifies and extends many existing results. Our results on the uniform global error bound (see Theorem 3.2) generalize Theorem 9 in Burke and Tseng (1996) by weakening the constraint qualification and by widening the varying range of the parameter. As an application, the existence of global error bound for convex multifunctions is also discussed.