## Recurrences for generating polynomials

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

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

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

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

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## Spectral stability for the partition function and the number of biased independent sets.

Abstract: In this talk we shall discuss two problems concerning the number of independent sets in regular graphs. The results of Kahn and Zhao show that among all d-regular graphs on n vertices, the graph consisting of disjoint copies of complete bipartite graphs maximizes the number of independent sets. In the first part we discuss a spectral stability phenomenon for this result. Further, we are interested in counting “biased” independent sets in regular bipartite graphs, i.e. independent sets which are essentially contained in one of the partition classes. This problem is related to the...

Read More