Hamilton Institute Seminars (HD / large)

Speaker:

Prof. B. Hanzon

Abstract:

Exponential Polynomial Trigonometric (EPT) functions are being considered as probability density functions. A specific matrix-vector representation is proposed for doing calculations with these functions. We investigate when these functions are non-negative and under which conditions the density functions are infinitely divisible--in which case there is an associated Levy process. Application to option price computations in finance will be presented.

For background information on this topic the website www.2-ept.com can be considered.

Speaker:

Dr. F. Gringoli

Abstract:

Experimenting in the field is a key activity for the evolution of the modern Internet: this is especially true for radio access protocols like IEEE 802.11 that are usually affected by unpredictable issues due to noise, competing stations and interference. Here we introduce OpenFWWF, an opensource firmware that implements a fully compliant 802.11 MAC on off-the-shelf WiFi boards: we show how it can be used in conjunction with the Linux kernel to play with the wireless stack. To this end we further demonstrate how we can easily customize the basic DCF access firmware to explore either performance boosting variations or to measure physical properties of the wireless channel.

Speaker:

Dr. M. A. Chaudry

Abstract:

Network coding has gained significant interest from the research community since the first paper by Alshwede et al., in 2000. Network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. We focus on network coding for wireless networks; specifically we investigate the Index Coding problem.

In wireless networks, each transmitted packet is broadcasted within a certain region and can be overheard by the nearby users. When a user needs to transmit packets, it employs the Index Coding that uses the knowledge of what the user's neighbors have heard previously (side information) in order to reduce the number of transmissions. The objective is to satisfy the demands of all the users with the minimum number of transmissions. With the Index Coding, each transmitted packet can be a combination of the original packets. The Index Coding problem has been proven to be NP-hard, and NP-hard to approximate.

Noting that the Index Coding problem is not only NP-hard but NP-hard to approximate, we look at it from a novel perspective and define the Complementary Index Coding problem; where the objective is to maximize the number of transmissions that are saved by employing the Index Coding compared to the solution that does not involve coding. We prove that the Complementary Index Coding problem can be approximated in several cases of practical importance. We investigate both the multiple unicast and multiple multicast scenarios for the Complementary Index Coding problem for computational complexity, and provide polynomial time approximation algorithms.

Speaker:

Dr. B. Radunović

Abstract:

Consider a distributed system that consists of a coordinator node connected to multiple sites. Items from a data stream arrive to the system one by one, and are arbitrarily distributed to different sites. The goal of the system is to continuously track a function of the items received so far within a prescribed relative accuracy and at the lowest possible communication cost. This class of problems is called a continual distributed stream monitoring.

In this talk we will focus on two problems from this class. We will first discuss the count tracking problem (counter), which is an important building block for other more complex algorithms. The goal of the counter is to keep a track of the sum of all the items from the stream at all times. We show that for a class of input loads a randomized algorithm guarantees to track the count accurately with high probability and has the expected communication cost that is sublinear in both data size and the number of sites. We also establish matching lower bounds. We then illustrate how our non-monotonic counter can be applied to solve more complex problems, such as to track the second frequency moment and the Bayesian linear regression of the input stream.

We will next discuss the online non-stochastic experts problem in the continual distributed setting. Here, at each time-step, one of the sites has to pick one expert from the set of experts, and then the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret with respect to the optimal choice in hindsight, while simultaneously keeping communication to the minimum. This problem is well understood in the centralized setting, but the communication trade-off in the distributed setting is unknown. The two extreme solutions to this problem are to communicate with everyone after each payoff, and not to communicate at all. We will discuss how to achieve the trade-off between these two approaches. We will present an algorithm that achieves a non-trivial trade-off and show the difficulties of further improving its performance.

Speaker:

Dr. C. Cano

Abstract:

Wireless Sensor Networks (WSNs) are networks formed by

highly constrained devices that communicate measured environmental

data using low-power wireless transmissions. The increase of spectrum

utilization in non-licensed bands along with the reduced power used by

these nodes is expected to cause high interference problems in WSNs.

Therefore, the design of new dynamic spectrum access techniques

specifically tailored to these networks plays an important role for

their future development. In this talk the main challenges of dynamic

spectrum access in WSNs will be described and a first approach to

coordinate sensor nodes will be presented.

Speaker:

S. Han

Abstract:

A cyber-physical system (CPS) is a system featuring a tight combination of, and coordination between, the system's computational and physical elements. A large-scale CPS usually consists of several subsystems which are formed by networked sensors and actuators, and deployed in different locations. These subsystems interact with the physical world and execute specific monitoring and control functions. How to organize the sensors and actuators inside each subsystem and interconnect these physically separated subsystems together to achieve secure, reliable and real-time communication is a big challenge.

In this talk, I will first present a TDMA-based low-power and secure real-time wireless protocol. This protocol can serve as an ideal communication infrastructure for CPS subsystems which require flexible topology control, secure and reliable communication and adjustable real-time service support. I will describe the network management techniques for ensuring the reliable routing and real-time services inside the subsystems and data management techniques for maintaining the quality of the sampled data from the physical world. To evaluate these proposed techniques, we built up a prototype system and deployed it in different environments for performance measurement. I will also present a light-weighted and scalable solution for interconnecting heterogenous CPS subsystems together through a slim IP adaptation layer. This approach makes the underlying connectivity technologies transparent to the application developers thus enables rapid application development and efficient migration among different CPS platforms.

Speaker:

C. Lancia

Abstract:

The cutoff phenomenon is the abrupt convergence to stationarity of a Markov chain. It is characterized by a narrow window centered around a cutoff-time in which the distance from stationarity suddenly drops from 1 to 0.

All the examples in which cutoff was detected clearly indicate that a drift towards the opportune quantiles of the stationary measure could be held responsible for this phenomenon. In the case of birth- and- death chains this mechanism is fairly well understood.

I will present a possible generalization of this picture to more general systems and show that there are two sources of randomness contributing to the size of the cutoff window. One is related to the drift towards the relevant quantiles of $\pi$ and the other to the thermalization in that region of the state space.

For one-dimensional systems a sufficiently strong drift ensures that the thermalization is under control but for higher-dimensional models the thermalization contribution can grow wide the cutoff window and even destroy completely the phenomenon.

Speaker:

Prof. P. Thiran

Abstract:

An increasingly larger number of applications require networks to perform decentralized computations over distributed data. A representative problem of these “in-network processing” tasks is the distributed computation of the average of values present at nodes of a network, known as gossip algorithms. They have received recently significant attention across different communities (networking, algorithms, signal processing, control) because they constitute simple and robust methods for distributed information processing over networks.

The first part of the talk is a survey some recent results on real-valued (analog) gossip algorithms. For many topologies that are realistic for wireless sensor networks, the classical nearest-neighbor gossip algorithms are slow, but a variation of these algorithms can be proven to order optimal (cost of O(n) messages for a network of n nodes) for some random geometric graphs. A second improvement, inspired by Uniform Gossip, allows to use uni-directional paths to compute the average, instead of requiring to route the average back and forth along the same path (one way paths are better suited in highly dynamic networks).

The second part of the talk is devoted to quantized gossip on arbitrary connected networks. By their nature, quantized algorithms cannot produce a real, analog average, but they can (almost surely) reach consensus on the quantized interval that contains the average, in finite time.

(This is a joint work with Florence Benezit, Martin Vetterli, Alex Dimakis, Vincent Blondel and John Tsitsiklis.)

Speaker:

Prof. J. J. Hunter

Abstract:

In a finite m-state irreducible Markov chain with stationary probabilities {\pi_i} and mean first passage times m_{ij} (mean recurrence time when i=j) it was first shown, by Kemeny and Snell, that \sum_{j=1}^{m}\pi_jm_{ij} is a constant, K, not depending on i. This constant has since become known as Kemeny’s constant. We consider a variety of techniques for finding expressions for K, derive some bounds for K, and explore various applications and interpretations of theseresults. Interpretations include the expected number of links that a surfer on the World Wide Web located on a random page needs to follow before reaching a desired location, as well as the expected time to mixing in a Markov chain. Various applications have been considered including some perturbation results, mixing on directed graphs and its relation to the Kirchhoff index of regular graphs.

Speaker:

Prof. S. O'Brien

Abstract:

In the context of the Macsi industrial mathematics group, we look at the types of problems which have arisen from industrial collaboration and examine a couple of these in detail.

In particular, we look at a mathematical model for etching glass with acids which arose from a study group with industry problem presented by Waterford Crystal.