Profiles of Random Trees: Limit Theorems for Random Recursive Trees and Binary Search Trees

We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio α of the level and the logarithm of tree size lies in [0,e). Convergence of all moments is shown to hold only for α ∈ [0,1] (with only convergence of finite moments when α ∈ (1,e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for α = 0 and a "quicksort type" limit law for α = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.     

Making working memory work: a computational model of learning in the prefrontal cortex and basal ganglia

The prefrontal cortex has long been thought to subserve both working memory (the holding of information online for processing) and executive functions (deciding how to manipulate working memory and perform processing). Although many computational models of working memory have been developed, the mechanistic basis of executive function remains elusive, often amounting to a homunculus. This article presents an attempt to deconstruct this homunculus through powerful learning mechanisms that allow a computational model of the prefrontal cortex to control both itself and other brain areas in a strategic, task-appropriate manner. These learning mechanisms are based on subcortical structures in the midbrain, basal ganglia, and amygdala, which together form an actor-critic architecture. The critic system learns which prefrontal representations are task relevant and trains the actor, which in turn provides a dynamic gating mechanism for controlling working memory updating. Computationally, the learning mechanism is designed to simultaneously solve the temporal and structural credit assignment problems. The model's performance compares favorably with standard backpropagation-based temporal learning mechanisms on the challenging 1-2-AX working memory task and other benchmark working memory tasks.     

Optimal neuronal tuning for finite stimulus spaces

The efficiency of neuronal encoding in sensory and motor systems has been proposed as a first principle governing response properties within the central nervous system. We present a continuation of a theoretical study presented by Zhang and Sejnowski, where the influence of neuronal tuning properties on encoding accuracy is analyzed using information theory. When a finite stimulus space is considered, we show that the encoding accuracy improves with narrow tuning for one- and two-dimensional stimuli. For three dimensions and higher, there is an optimal tuning width.     

A simple Hebbian/anti-Hebbian network learns the sparse, independent components of natural images

Slightly modified versions of an early Hebbian/anti-Hebbian neural network are shown to be capable of extracting the sparse, independent linear components of a prefiltered natural image set. An explanation for this capability in terms of a coupling between two hypothetical networks is presented. The simple networks presented here provide alternative, biologically plausible mechanisms for sparse, factorial coding in early primate vision.     

Reverse procurement and auctions for consumers

Web-based bid invitation platforms and reverse auctions are increasingly used by consumers for the procurement of goods and services. An empirical examination shows that with B-2-C these procurement methods generate considerable benefits for the consumer:

On Delivery Times in Packet Networks under Adversarial Traffic

We consider packet networks and make use of the "adversarial queuing theory" model [10]. We are interested in the question of guaranteeing that all packets are actually delivered to destination, and of having an upper bound on the delivery times of all packets. Whether this is possible against all adversarial queuing theory rate-1 adversaries was previously posed as an open question [13],[10]. Among other things, we give a queuing policy that guarantees bounded delivery time whenever the rate-1 adversary injects a sequence of packets for which there exists a schedule with a finite upper bound on the delivery times of all packets, and adheres to certain additional conditions. On the negative side we show that there exist rate-1 sequences of packets for which there is no schedule with a finite upper bound on the delivery times of all packets. We thus answer an open question posed by Gamarnik [13]. We further show that delivering all packets while maintaining stability (we coin the term "reliability" for this property) can be done by an offline scheduler whenever the injection of packets is done at rate of at most 1. However, on the other hand, we also show that there is no online protocol (even centralized) that can achieve that property against all rate-1 adversaries. We thus answer an open question of Borodin et al. [10].     

Metacomputing across intercontinental networks

An intercontinental network of supercomputers spanning more than 10 000 miles and running challenging scientific applications was realized at the Supercomputing ’99 (SC99) conference in Portland, OR using PACX-MPI and ATM PVCs. In this paper, we describe how we constructed the heterogeneous cluster of supercomputers, the problems we confronted in terms of multi-architecture and the way several applications handled the specific requirements of a metacomputer.     

Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time. Received 16 May 2000 / Revised 18 December 2000 / Accepted in revised form 2 January 2001     

Projecting CLPR constraints

The presentation of constraints in a usable form is an essential aspect of Constraint Logic Programming (CLP) systems. It is needed both in the output of constraints, as well as in the production of an internal representation of constraints for meta-level manipulation. Typically, only a small subset \(\tilde x\) of the variables in constraints is of interest, and so an informal statement of the problem at hand is: given a conjunction \(c(\tilde x,\tilde y)\) of constraints, express the projection \(\exists \tilde y c(\tilde x,\tilde y)\) ofc onto \(\tilde x\) in the simplest form. In this paper, we consider the constraints of the CLP(R) system and describe the essential features of its projection module. One main part focuses on the well-known problem of projection inlinear arithmetic constraints. We start with a classical algorithm and augment it with a procedure for eliminating redundant constraints generated by the algorithm. A second part discusses projection of the other object-level constraints: equations over trees and nonlinear equations. The final part deals with producing a manipulable form of the constraints, which complicates the projection problem.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.