• Seminario 29 giugno  2023

Speaker: Paola Vocca

Title:  Distance-based metrics computation on Very Large Graphs.

In this talk we propose a fast approximation framework to estimate distance-based metrics on very large graphs such as the (effective) diameter or the average distance within a small error. The framework assigns seeds to nodes and propagates them in a BFS-like fashion, computing the neighbours set until we obtain either the whole vertex set (for computing the diameter) or a given percentage of vertices (for the effective diameter). At each iteration, we derive compressed Boolean representations of the neighbourhood sets discovered so far. The framework yields two algorithms: the first one propagates all the $s$ seeds in parallel, and second one which propagates the seeds sequentially. For each node, the compressed representation of the first algorithm requires $s$ bits while the second one, $1$ bit per node, only. Both algorithms compute the average distance, the effective diameter, the diameter, and the connectivity rate (a measure of the sparseness degree of the transitive closure graph) within a small error with high probability. The time complexity of our approaches is linear in the number of edges. We implemented the framework and released an open-source package for the analysis of large graphs. The experimental results show that the proposed framework improves the current state of the art in accuracy, speed, and space. Finally, we experimentally show that the framework is also very efficient for solving the All-Pair Shortest Path problem in very large graphs.

Joint work with (G.B. Amati, S. Angelini, A. Cruciani, D. Pasquini)

Video 

• Seminario 29 marzo  2023

Speaker: Andrea Frosini

Title:  On the reconstruction of hypergraphs from degree sequences: some known results and open problems

The characterization of simple graphs from their degree sequences has been a challenging problem whose solution dates back to a well known result of Erdos and Gallai in 1960. This same problem related to hypergraphs remained open until 2018 when Deza et al. proved its NP-completeness even in the simplest case of uniform hypergraphs. Before this result, some strategies to quick detect and reconstruct classes of hypergraphs from degree sequences were developed. These results use tools borrowed from discrete tomography and combinatorics. At present, some relevant related questions remain unsolved, mainly related both to the extension of the NP-hard core in the detection process and to the uniqueness (up to isomorphism) of the hypergraphs sharing the same degree sequences.

Video 

• Seminario 2 marzo  2023

Speaker: Ugo Dal Lago

Title: Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories

We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably defined theory à la Buss (expressed in this new language) precisely capture polytime random functions. Then, we provide two new characterizations of the semantic class BPP obtained by internalizing the error-bound check within a logical system: one relies on measure-sensitive quantifiers, the other encodes such quantifiers by standard first-order quantification. This leads us to introduce a family of effectively enumerable subclasses of BPP, called BPP(T), each consisting of languages captured by probabilistic Turing machines whose underlying error can be proved bounded in the corresponding arithmetical theory T. As a paradigmatic consequence of this approach, we establish that polynomial identity testing is in BPP(PA).

Video 

• Seminario 26 gennaio 2023

Speaker: Tiziana Calamoneri

Title: A look inside Pairwise Compatibility Graphs

A graph G=(V,E) is a pairwise compatibility graph (PCG)  if there exists an edge-weighted tree T and two non-negative real numbers m and M such that each leaf u of T is a node of V and there is an edge (u,v) in E if and only if  d_T is in the interval [m, M], where d_T (u, v) is the sum of weights of the edges on the unique path from u to v in T.

In this talk, I will start survey the state of the art concerning this class of graphs, some of its subclasses and superclasses.

Video 

• Seminario 22 novembre 2022

Speaker: Paolo Ferragina

Title : Data-aware (learned) design of data structures

Key-value stores and search engines are posing a continuously growing need to efficiently store, retrieve and analyze massive and dynamic sets of (possibly long) keys under the many and different requirements posed by users, devices, and applications. Such a new level of complexity cannot be properly handled by known data structures, so academic and industrial researchers started very recently to devise surprising new results that integrate classic approaches (such as B trees and tries) with data-aware techniques which exploit regularities and patterns in the data in order to squeeze space occupancy and speed up query and update operations. One example of these novel approaches is the so-called “Learned Data Structures”, namely ones that plug machine-learning tools within data-structure design. In this talk, I will survey the evolution of compressed and learned data structures in the context of indexing and compressing fixed- and variable-length keys.

Video 

• Seminario 29 settembre 2022

Speaker: Paolo Boldi

Title : Monotonicity of centralities in directed and undirected networks

Is it always beneficial to create a new relationship (have a new follower/friend) in a social network? This question can be formally stated as a property of the centrality measure that defines the importance of the actors of the network. Score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relatively to the remaining nodes. In this talk, I will explore these two properties for various centralities, and show how the effect of directedness impacts on them.

• Seminario 23 giugno 2022

Speaker: Giovanni Pighizzini

Title : Two-way Automata and Related Models: Power and Complexity

The notion of two-way finite automata was introduced at the origin of automata theory. In this model, the head can be moved in both directions on the input tape. In 1959, Rabin and Scott and, independently, Shepherdson, proved that two-way automata, both in the deterministic and in the nondeterministic versions, have the same power as one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question about the costs, in the number of states, of the simulations of one-way and two-way nondeterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. This question is still open, despite all attempts to solve it. In the last 20 years the problem of Sakoda and Sipser has been widely reconsidered and many new results related to it have been obtained. In the first part of the talk, we will present a survey on the main results of these studies. The second part of the talk will be devoted to limited automata. These models, introduced by Hibbard in 1967, are single-tape Turing machines with strict rewriting restrictions, that make them equivalent to pushdown automata. However, the subfamily of 1-limited automata, which can be seen as an extension of two-way automata, is not more powerful than finite automata. We will present some descriptional complexity results on these models and some connections with the Sakoda and Sipser question.

Video 

• Seminario 26 maggio 2022

Speaker: Giuseppe Italiano

Title : 2-Connectivity in Directed Graphs

We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being

complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has

a much richer and more complicated structure. For undirected graphs it has been known for over 40

years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components

in linear time, by simply using depth first search. In the case of digraphs, however, the very same

problems have been much more challenging and have been tackled only very recently.

Video 

Per partecipare come relatore potete contattare 

Giuseppa Castiglione (giuseppa.castiglione@unipa.it)  e/o Blerina Sinaimeri (bsinaimeri@luiss.it )