
Wolfgang Maass; Eduardo D. Sontag
We consider recurrent analog neural nets where the output of each gate is subject to gaussian noise or any other common noise distribution that is nonzero on a sufficiently large part of the statespace. We show that many regular languages cannot be recognized by networks of this type, and we give a precise characterization of languages that can be recognized. This result implies severe constraints on possibilities for constructing recurrent analog neural nets that are robust against realistic types of analog noise. On the other hand, we present a method for constructing feedforward analog neural nets that are robust with...

Wolfgang Maass; Pekka Orponen
We introduce a model for analog computation with discrete time in the presence of analog noise that is flexible enough to cover the most important concrete cases, such as noisy analog neural nets and networks of spiking neurons. This model subsumes the classical model for digital computation in the presence of noise. We show that the presence of arbitrarily small amounts of analog noise reduces the power of analog computational models to that of finite automata, and we also prove a new type of upper bound for the VCdimension of computational models with analog noise.

Jose Lugomartinez; Predrag Radivojac

Aasa Feragen; Niklas Kasenburg; Jens Petersen; Karsten Borgwardt; Marleen de Bruijne
While graphs with continuous node attributes arise in many applications, stateoftheart graph kernels for comparing continuousattributed graphs suffer from a high runtime complexity. For instance, the popular shortest path kernel scales as O(n4), where n is the number of nodes. In this paper, we present a class of graph kernels with computational complexity O(n2(m+ log n+ δ2 + d)), where δ is the graph diameter, m is the number of edges, and d is the dimension of the node attributes. Due to the sparsity and small diameter of realworld graphs, these kernels typically scale comfortably to large graphs. In our...

Kurt Mehlhorn; Stefan Näher
LEDA is a library of efficient data types and algorithms. At present, its strength is graph algorithms and the data structures related to them. The computational geometry part is evolving. The main features of the library are 1) a clear separation of specification and implementation 2) parameterized data types 3) a comfortable data type graph, and 4) its ease of use.

Luc Brun; Didier Villemin, et al.

Kurt Mehlhorn, et al.

T. Bonald; L. Massoulié; A. Proutière; J. Virtamo
We compare the performance of three usual allocations (maxmin fairness, proportional fairness and balanced fairness) in a communication network whose resources are shared by a random number of data flows. The model consists of a network of processorsharing queues. The vector of service rates, which is constrained by some compact, convex capacity set representing the network resources, is a function of the number of customers in each queue. This function determines the way network resources are allocated. We show that this model is representative of a rich class of wired and wireless networks. We give in this general framework the...

Ioannis Z. Emiris; Elias P. Tsigaridas; George M. Tzoumas

Rong Qu; Edmund Burke; Barry McCollum; Liam T. G. Merlot; Sau Y. Lee
Exam timetabling is one of the most important administrative activities that takes place in academic institutions. In this paper we present a critical discussion of the research on exam timetabling in the last decade or so. This last ten years has seen an increased level of attention on this important topic. There has been a range of significant contributions to the scientific literature both in terms of theoretical and practical aspects. The main aim of this survey is to highlight the new trends and key research achievements that have been carried out in the last decade. We also aim to...

R. Bekker; O. J. Boxma; O. Kella
We consider a reflected Lévy process without negative jumps, starting at the origin. When the reflected process first upcrosses level K, a timer is activated. D time units later the timer expires, and the Lévy exponent of the Lévy process is changed. As soon as the process hits zero again, the Lévy exponent reverses to the original function. If the process has reached the origin before the timer expires, then the Lévy exponent does not change. Using martingale techniques, we analyze the steadystate distribution of the resulting process, reflected at the origin. We pay special attention to the cases of...

Christophe Giraud; Sylvie Huet; Nicolas Verzelen
We review recent results for highdimensional sparse linear regression in the practical case of unknown variance. Different sparsity settings are covered, including coordinatesparsity, groupsparsity and variationsparsity. The emphasis is put on nonasymptotic analyses and feasible procedures. In addition, a small numerical study compares the practical performance of three schemes for tuning the Lasso estimator and some references are collected for some more general models, including multivariate regression and nonparametric regression.

Paul G. Constantine; David F. Gleich
We suggest a revision to the PageRank random surfer model that considers the influence of a population of random surfers on the PageRank vector. In the revised model, each member of the population has its own teleportation parameter chosen from a probability distribution, and consequently, the ranking vector is random. We propose three algorithms for computing the statistics of the random ranking vector based respectively on (i) random sampling, (ii) paths along the links of the underlying graph, and (iii) quadrature formulas. We find that the expectation of the random ranking vector produces similar rankings to its deterministic analogue, but...

David F. Gleich; Paul G. Constantine; Abraham D. Flaxman; Asela Gunawardana
PageRank computes the importance of each node in a directed graph under a random surfer model governed by a teleportation parameter. Commonly denoted alpha, this parameter models the probability of following an edge inside the graph or, when the graph comes from a network of web pages and links, clicking a link on a web page. We empirically measure the teleportation parameter based on browser toolbar logs and a click trail analysis. For a particular user or machine, such analysis produces a value of alpha. We find that these values nicely fit a Beta distribution with mean edgefollowing probability between...

T. Bonald; L. Massoulie; A. Proutiere; J. Virtamo
We compare the performance of three usual allocations, namely maxmin fairness, proportional fairness and balanced fairness, in a communication network whose resources are shared by a random number of data flows. The model consists of a network of processorsharing queues. The vector of service rates, which is constrained by some compact, convex capacity set representing the network resources, is a function of the number of customers in each queue. This function determines the way network resources are allocated. We show that this model is representative of a rich class of wired and wireless networks. We give in this general framework...

Ioannis Z. Emiris; Elias P. Tsigaridas

R. Bekker; O. J. Boxma; O. Kella
We consider a reflected Lévy process without negative jumps, starting at the origin. When the reflected process first upcrosses level K, a timer is activated. D time units later the timer expires, and the Lévy exponent of the Lévy process is changed. As soon as the process hits zero again, the Lévy exponent reverses to the original function. If the process has reached the origin before the timer expires, then the Lévy exponent does not change. Using martingale techniques, we analyze the steadystate distribution of the resulting process, reflected at the origin. We pay special attention to the cases of...

Elias P. Tsigaridas, Ioannis Z. Emiris

Sem Borst; N. Hegde; A. Proutière

Ralph Matthes