Roberto Borelli

Projects, Seminars and material

In this page I expose some of the material I've prepared and I'm producing during my university journey. I share my thesis, my seminars and more. Some of the material is written in english and some of the material is written in italian.

Thesis	Slides	Bachelor's thesis: Algorithms for neighbourhood searches Type: Bachelor's thesis Language: Italian Abstract:
DOI	Code	Data Structures and Algorithms for k-th Nearest Neighbours Conformational Entropy Estimation Type: Publication Language: English Authors: Roberto Borelli, Agostino Dovier and Federico Fogolari Abstract: Entropy of multivariate distributions may be estimated based on the distances of nearest neighbours from each sample from a statistical ensemble. This technique has been applied on biomolecular systems for estimating both conformational and translational/rotational entropy. The degrees of freedom which mostly define conformational entropy are torsion angles with their periodicity. In this work, tree structures and algorithms to quickly generate lists of nearest neighbours for periodic and non-periodic data are reviewed and applied to biomolecular conformations as described by torsion angles. The effect of dimensionality, number of samples, and number of neighbours on the computational time is assessed. The main conclusion is that using proper data structures and algorithms can greatly reduce the complexity of nearest neighbours lists generation, which is the bottleneck step in nearest neighbours entropy estimation.
DOI		The kth nearest neighbor method for estimation of entropy changes from molecular ensembles Type: Publication Language: English Authors: Federico Fogolari, Roberto Borelli, Agostino Dovier, Gennaro Esposito Abstract: All processes involving molecular systems entail a balance between associated enthalpic and entropic changes. Molecular dynamics simulations of the end-points of a process provide in a straightforward way the enthalpy as an ensemble average. Obtaining absolute entropies is still an open problem and most commonly pathway methods are used to obtain free energy changes and thereafter entropy changes. The kth nearest neighbor (kNN) method has been first proposed as a general method for entropy estimation in the mathematical community 20 years ago. Later, it has been applied to compute conformational, positional–orientational, and hydration entropies of molecules. Programs to compute entropies from molecular ensembles, for example, from molecular dynamics (MD) trajectories, based on the kNN method, are currently available. The kNN method has distinct advantages over traditional methods, namely that it is possible to address high-dimensional spaces, impossible to treat without loss of resolution or drastic approximations with, for example, histogram-based methods. Application of the method requires understanding the features of: the kth nearest neighbor method for entropy estimation; the variables relevant to biomolecular and in general molecular processes; the metrics associated with such variables; the practical implementation of the method, including requirements and limitations intrinsic to the method; and the applications for conformational, position/orientation and solvation entropy. Coupling the method with general approximations for the multivariable entropy based on mutual information, it is possible to address high dimensional problems like those involving the conformation of proteins, nucleic acids, binding of molecules and hydration.
Report	Slides	The 3SUM problem admits subquadratic solutions Type: Seminar for the course "Advanced Algorithms" Language: English Abstract: In this work, I consider the 3sum problem. Recent years’ studies have shown that the problem admits a subquadratic solution. The 3sum problem has been used in the area of fine-grained complexity to establish lower bounds to a wide range of other problems (which have shown to be 3sum-hard) for example in the computational geometry area. In this paper, I examine the Freund approach to obtain a subquadratic algorithm. To obtain a saving in the complexity, several tricks have been applied and in particular it has been shown how to efficiently enumerate the so-called chunks through a correspondence with paths in a matrix and then all pairs of blocks agreeing with such derived chunks are obtained through a reduction to the dominance-merge problem.
Report	Slides	Expressiveness of temporal logic Type: Seminar for the course "Automatic system Verification: Theory and Applications" Language: English Abstract: In this work, I consider the expressive power of various temporal logics. First, I recall some basic results about expressiveness of first order logic. Then I consider the case of LTL and I show a theorem that can be used to prove that the concept of parity is not definable in this context. I discuss a counterexample that proves that the mentioned theorem doesn’t directly apply to LTL+P and I briefly highlight how a possible investigation may lead to a generalization of the theorem to the LTL+P case. Next, I relate first order definable languages with LTL ones and I present an extension to LTL which allows us to increase the expressive power and capture regular languages without changing the complexity of the decision procedure. Finally, I move to the more interesting case of interval logic. I introduce the notion of bisimulation and its use in modal logic and, in particular, I show how to apply it to prove that the logic PNL is strictly more expressive than its future fragment A.
Slides		Logic for context-free languages Type: Seminar for the course "Logic for Computer Science" Language: Italian Abstract:
Report	Code	Scheduling of competitions with automated reasoning techniques Type: Final project for the course "Automated Reasoning" Language: Italian Abstract:
Report	Slides	XGBoost Type: Seminar for the course "Applied Statistics and Data Analysis" Language: Italian Abstract: