Discrete Mathematics

Thermodynamics of small systems through a reversible and conservative discrete automaton.

Event Date: Jun 14, 2017 in Discrete Mathematics, Seminars

Abstract: The focus of this talk will be the Q2R model which is a reversible and conservative cellular automaton. The Q2R model possesses quite a rich and complex dynamics. Indeed, the configuration space is composed of a huge number of cycles with exponentially long periods, that we attempt to characterize. Furthermore, a coarse-graining approach is applied to the time series of the total magnetization, leading to a master equation that governs the macroscopic irreversible dynamics of the Q2R automata. The methodology is replicated for various system sizes. In the case of small systems, we...

Read More

Recurrences for generating polynomials

Event Date: Apr 07, 2017 in Discrete Mathematics, Seminars

Abstract:   In this talk we consider sequences of polynomials that satisfy differential–difference recurrences. Our interest is motivated by the fact that polynomials satisfying such recurrences frequently appear as generating polynomials of integer valued random variables that are of interest in discrete mathematics. It is, therefore, of interest to understand the properties of such polynomials and their probabilistic consequences. We will be primarily interested in the limiting distribution of the corresponding random variables. As an illustration we give a few examples, leading...

Read More

Provably efficient high dimensional feature extraction

Event Date: Dec 28, 2016 in Discrete Mathematics, Seminars

Abstract: The goal of inference is to extract information from data. A basic building block in high dimensional inference is feature extraction, that is, to compute functionals of given data that represent it in a way that highlights some underlying structure. For example, Principal Component Analysis is an algorithm that finds a basis to represent data that highlights the property of data being close to a low-dimensional subspace. A fundamental challenge in high dimensional inference is the design of algorithms that are provably efficient and accurate as the dimension grows. In this...

Read More

Fault-Tolerant Decentralized Runtime Monitoring

Event Date: Mar 16, 2016 in Discrete Mathematics, Seminars

Abstract:   Runtime verification  is aiming at extracting information from a running system, and using it to detect and possibly react to  behaviors violating a given correctness property. Decentralized runtime verification involves a set of monitors observing the behavior of  the underlying system. In this talk, the investigation of decentralized runtime verification in which not only the elements of the observed system, but also the monitors themselves are subject to failures will be presented. In this context, it is unavoidable that the unreliable monitors may have different views of...

Read More

P-Stability: Graph generation, randomization and k-degree anonymity

Event Date: Mar 11, 2016 in Discrete Mathematics, Seminars

With the motivation of social network privacy and the aim of anonymizing the graph structure of a social network, several methods have been studied. One of the most basic is that of k-degree anonymization. It consists of making the least edge modifications to a given graph, in order that for every degree value of a vertex in the modified graph there are at least k repetitions of it in the degree sequence. This implies that no vertex can be uniquely identified by its degree, hence, the modified graph is k-degree anonymous.   Another technique for graph anonymization is the random...

Read More

Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

Event Date: Nov 04, 2015 in Discrete Mathematics, Seminars

ABSTRACT:     Consider the following model of strong-majority bootstrap percolation on a graph. Let r be some positive integer, and p in [0,1]. Initially, every vertex is active with probability p, independently from all other vertices. Then, at every step of the process, each vertex v of degree deg(v) becomes active if at least (deg(v)+r)/2 of its neighbours are active. Given any arbitrarily small p>0 and any integer r, we construct a family of d=d(p,r)-regular graphs such that with high probability all vertices become active in the end. In particular, the case r=1 answers a...

Read More