De Stefani, Lorenzo

Lorenzo De Stefani

Lecturer in Computer Science

Overview

I am a Lecturer in Computer Science at the Department of Computer Science at Brown University. I am currently teaching CSCI1010 - Theory of Computation, CSCI1570 - Design and Analysis of Algorithms, and CSCI1951A - Data Science.

Some research problems I am currently working on include the following:

Design and analysis of algorithms:
- Lower bounds to the Input/Output (I/O) complexity of sequential and parallel algorithms;
- Computation and Communication-optimal parallel algorithms;
- Time-space and time-I/O tradeoffs;
- Algorithms resilient to byzantine memory faults: can we preserve some measure of functionality?
Big Data analysis and sampling:
- Analysis of large and fully dynamic graphs: can we design algorithms with strong probabilistic guarantees which require just one pass over the entire network?
- Multiple hypothesis testing in Big Data: can we use tools from statistical learning theory to obtain accurate estimates over many quantities of interest?
- Learning from user preferences: how can we model user preferences given incomplete rankings?

I received my second Ph.D. in Computer Science from 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).

Brown Affiliations

Computer Science

On the Web

Homepage

Research

Research Overview

Statistical learning approaches to frequentist multiple hypothesis testing: Developed methods for multiple hypothesis correction building on results from statistical learning theory improving over classical frequentist methods. Our procedures build on uniform convergence bounds based on Rademacher Complexity and Vapnik-Chervonenkis (VC) dimension.
Statistical learning approaches to adaptive data analysis: Developed efficient and rigorous procedure for controlling the accumulated error in adaptive data analysis building on results from statistical learning theory. Developed novel techniques for Rademacher Complexity estimation based on applications of the Martingale Central Limit theorem and Bernstein’s inequality for martingales.
Rigorous statistical approaches to visual data representation and visualization recommendation: Developed a procedure which allows for adaptive visual exploration while controlling the Marginal False Discovery Rate (mFDR) [7,8,9] building on “alpha investing” testing paradigm. Developed alternative technique with stronger FWER guarantees with extension of the scope of the control to the validation of recommendations of “interesting” visualizations building on use statistical learning analysis tools based on Vapnik-Chervonenkis (VC) dimension.
Sub-graph counting in dynamic graph streams: Developed Tr´ıest, a suite of one-pass streaming algorithms based on reservoir sampling and the random pairing sampling schemes, which yield high-quality unbiased estimates of the number of triangle motifs in fully dynamic edges streams while using a small local memory. This work was awarded the Best Student Paper award for the research track at the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’16) . Also developed Tiered Sampling, an extension of the Tr´ıest paradigm which employs multiple reservoir sample tiers in order to accurately estimate the count of rare and complex patterns such as 4- and 5-cliques.
Reconstructing hidden permutations from a sample: Developed a variant of the Mallows model where the distribution is a function of the Average-Precision (AP) correlation statistic. We presented a generative model for constructing samples from this distribution, and we developed 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.
On the I/O complexity integer multiplication and hybrid algorithms Further developed the G-flow I/O technique [6] to include the formalization of the concept of “partial Grigoriev’s flow,” and used it to obtain the first asymptotically tight lower bound on the I/O complexity of the Toom-Cook fast integer multiplication algorithm. In the same work, we presented a matching upper bound . Presented the first asymptotically tight I/O lower bounds for a general class of hybrid non-stationary, non-uniform algorithms for matrix multiplication.

Background

Education and Training

Year	Degree	Institution
2020	PhD	Brown University
2016	PhD	University of Padova
2012	MSc	University of Padova
2009	BSc	University of Padova

Honors and Awards

KDD Best Student Paper Award, Research Track, San Francisco , CA, 2016.

Researchers@Brown