CS 1010: Theory of computation
In the 2020 fall semester, I am teaching CS 1010: Theory of computation, which is offered for undergraudate students at Brown University.
I am Lecturer in Computer Science at the Computer Science department at Brown University. Among others I am currently teaching CS1010 - Theory of Computation and CS1570 - Design and Analysis of Algorithms.
Some research problems I am currenly working on include:
I received my second Ph.D. in Computer Science from the Brown University in 2020, I was advised by Professor Eli Upfal.
I received my first Ph.D. in Computer Engineering from the University of Padova in 2016, I was advised by Professor Gianfranco Bilardi.
From the same institution I received a Master of Science degree in Computer Engineering (2012 advised by Professor Gianfranco Bilardi) and a Bachelor of Science degree in Computer Engineering (2009 advised by Professor Giorgio Maria Di Nunzio).
Ph.D. in Computer Science
Brown University
Adivisor: Professor Eli Upfal
Thesis title: "Probabilistic approaches for rigorous and efficient analysis ofstatistical properties of large datasets"
Ph.D. in Information Engineering
University of Padova
Adivisor: Professor Gianfranco Bilardi
Thesis title: "On Space Constrained Computations"
MS in Computer Engineering
University of Padova
Adivisor: Professor Gianfranco Bilardi
Thesis title: "On the Space Complexity of Computational Directed Acyclic Graphs"
Final grade: 110/110 cum laude
BS in Computer Engineering
University of Padova
Adivisor: Professor Giorgio Maria Di Nunzio
Thesis title: "Study on the classification of documents retrieved by information retrieval systems using linear regression analysis" (in Italian)
Final grade: 110/110 cum laude
Nearly matching upper and lower bounds are derived for the I/O complexity of the Toom-Cook-k (or Toom-k) algorithm computing the products of two integers, each represented with n digits in a given base s, in a two-level storage hierarchy with M words of fast memory, with different digits stored in different memory words. An IO_{A,k}(n,M) = (n/M)^{log_k 2k-1}M lower bound on the I/O complexity is established, by a technique that combines an analysis of the size of the dominators of suitable sub-CDAGs of the Toom-Cook-k CDAG (Computational Directed Acyclic Graph) and the analysis of a function, which we call Partial Grigoriev's flow", which captures the amount of information to be transferred between specific subsets of input and output variables, by any algorithm that solves the integer multiplication problem. The lower bound applies even if the recomputation of partial results is allowed. A careful implementation of the Toom-Cook-k algorithm, assuming that M = ^k3 log_s k, is also developed and analyzed, leading to an I/O complexity upper bound that is within a factor O(k^2) of the corresponding lower bound, hence asymptotically optimal for fixed k. Both the lower and the upper bounds are actually derived in the more general case where the value of k is allowed to vary with the level of recursion, although the quantitative expressions become more involved. Extensions of the lower bound for a parallel model with P processors are also discussed.
A tight Ω((n/√M)^log_2^7 M) lower bound is derived on the I/O complexity of Strassen's algorithm to multiply two n×n matrices, in a two-level storage hierarchy with M words of fast memory. A proof technique is introduced, which exploits the Grigoriev's flow of the matrix multiplication function as well as some combinatorial properties of the Strassen computational directed acyclic graph (CDAG). Applications to parallel computation are also developed. The result generalizes a similar bound previously obtained under the constraint of no-recomputation, that is, that intermediate results cannot be computed more than once. For this restricted case, another lower bound technique is presented, which leads to a simpler analysis of the I/O complexity of Strassen's algorithm and can be readily extended to other "Strassen-like" algorithms.
We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, highquality approximations of the global and local (i.e., incident to each vertex) number of triangles in a fully-dynamic graph represented as an adversarial stream of edge insertions and deletions. Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all times. This is in contrast with previous approaches, which require hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they use. We analyze the variance of the estimations and show novel concentration bounds for these quantities. Our experimental results on very large graphs demonstrate that trièst outperforms state-of-the-art approaches in accuracy and exhibits a small update time.
Best student paper award, research track.
We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, highquality
approximations of the global and local (i.e., incident to each vertex) number of triangles in a
fully-dynamic graph represented as an adversarial stream of edge insertions and deletions.
Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all
times. This is in contrast with previous approaches, which require hard-to-choose parameters (e.g., a fixed
sampling probability) and offer no guarantees on the amount of memory they use. We analyze the variance
of the estimations and show novel concentration bounds for these quantities.
Our experimental results on very large graphs demonstrate that TRIÈST outperforms state-of-the-art
approaches in accuracy and exhibits a small update time.
We study the problem of learning probabilistic models for permutations, where the order between highly ranked items in the observed permutations is more reliable (i.e., consistent in different rankings) than the order between lower ranked items, a typical phenomena observed in many applications such as web search results and product ranking. We introduce and study a variant of the Mallows model where the distribution is a function of the widely used Average-Precision (AP) Correlation statistic, instead of the standard Kendall's tau distance. We present a generative model for constructing samples from this distribution and prove useful properties of that distribution. Using these properties we develop an efficient algorithm that provably computes an asymptotically unbiased estimate of the center permutation, and a faster algorithm that learns with high probability the hidden central permutation for a wide range of the parameters of the model. We complement our theoretical analysis with extensive experiments showing that unsupervised methods based on our model can precisely identify ground-truth clusters of rankings in real-world data. In particular, when compared to the Kendall's tau based methods, our methods are less affected by noise in low-rank items.
We extend the Faulty RAM model by Finocchi and Italiano (2008) by adding a safe memory of arbitrary size S, and we then derive tradeoffs between the performance of resilient algorithmic techniques and the size of the safe memory. Let δ and α denote, respectively, the maximum amount of faults which can happen during the execution of an algorithm and the actual number of occurred faults, with α≤δ. We propose a resilient algorithm for sorting n entries which requires O(n log n + α(δ/S+log S)) time and uses Θ(S) safe memory words. Our algorithm outperforms previous resilient sorting algorithms which do not exploit the available safe memory and require O(n log n + αδ) time. Finally, we exploit our sorting algorithm for deriving a resilient priority queue. Our implementation uses Θ(S) safe memory words and Θ(n) faulty memory words for storing n keys, and requires O(log n+δ/S) amortized time for each insert and deletemin operation. Our resilient priority queue improves the O(log n+δ) amortized time required by the state of the art.
Since massive collections of textual documents become more and more available in digital format, the organization and classification of these documents in Digital Library Management System (DLMS) becomes an important issue. Information access components of a DLMS, such as automatic categorization and retrieval components of digital objects, allow users to interact with the system in order to browse, explore, and retrieve resources from collections of objects. The demonstration presents a two-dimensional visualization tool of Naïve Bayes (NB) probabilistic models for Automated Text Categorization (ATC) and Information Retrieval (IR) useful to explore raw data and interpret results.
In the 2020 fall semester, I am teaching CS 1010: Theory of computation, which is offered for undergraudate students at Brown University.
In the 2020 fall semester, I am teaching CS 1570: Design and Analysis of Algorithms, which is offered for undergraudate students at Brown University. I will be co-teaching this class with Professor Roberto Tamassia.
In the 2018 fall semester, I served as co-instructor with Professor Eli Upfal for CS1450: Introduction to Probability in Computing , which is offered to undergraudate and graduate students at Brown University.
In 2016 and 2017, I served as Grad TA for CS450, which is offered to undergraudate and graduate students at Brown University. The main instructor for the class is Professor Eli Upfal.
In 2013 and 2014, I served as Teaching Assistant for Parallel Computing, which is offered to graduate students at the Department of Information Engineering at the University of Padova. The main instructor for the class is Professor Gianfranco Bilardi
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Time permitting, I am alway happy to discuss interesting research topics with sudents and colleagues.
You can find me at my office located at the Department of Computer Science of Brown Univeristy at 115 Waterman St, Providence, RI 02906
I am generally at my office every day from 9:30am until 18:30 pm, but you may consider a sending me and email at lorenzo_destefani AT brown.edu to set up an appointment.