SO Re Co Di
Spectral and Optimization
Techniques
for
Robust Recovery,
Combinatorial Constructions,
and Distributed Algorithms
This project started in September, 2019, and is supported by the European Research Council. It applies techniques from linear algebra and from convex optimization to
- problems of robust recovery and robust statistics;
- the construction of combinatorial objects such as graph and hypergraph sparsifiers;
- the analysis of probabilistic network processes.
People
Staff
- Luca Trevisan: PI
- Jonathan Shi: Postdoc, Sept. 1, 2019-present
- Fabrizio Pittorino: Postdoc, Dec 1, 2020-present
- Lucas Pesenti: PhD Student, Sept 1, 2021-present
Visitors
- Antares Chen, Sept. 15 - Dec. 15, 2019
- Hoeteck Wee, Oct. 2-5, 2019
- Andrej Bogdanov, Dec. 9-14, 2019
- Alon Rosen, Dec. 12-15, 2019
- Lucas Pesenti, Sept. - Dec., 2020
- Pedro Paredes, July 25-31, 2021
- Luca Becchetti, Dec. 13-15, 2021
- Pierluigi Crescenzi, Dec. 13-17, 2021
Jobs
Papers
- Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi
Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks
Preprint, 2021, arXiv:2103.16398
- Antares Chen, Jonathan Shi and Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound
To appear in Proc. of SODA 2022,
arXiv:2008.05648
- Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan and Isabella Ziccardi
Expansion and Flooding in Dynamic Random Networks with Node Churn
In Proc. of ICDCS 2021,
arXiv:2007.14681
- Sam Hopkins, Tselil Schramm and Luca Trevisan
Subexponential LPs Approximate Max Cut
In Proc. of FOCS 2020, arXiv:1911.10304
- Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco
Pasquale, Giacomo Scornavacca and Luca Trevisan
Consensus vs Broadcast, with and w/o Noise
In Proc. of ITCS 2020,
arXiv:1807.05626
-
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan
Finding a Bounded-Degree Expander Inside a Dense One
In Proc. of SODA 2020, arXiv:1811.10316
- Theo McKenzie, Hermish Mehta, and Luca Trevisan
A New Algorithm for the Robust Semi-random Independent Set Problem
In Proc. of SODA 2020, arXiv:1808.03633
- Nikhil Bansal, Ola Svensson and Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
In Proc. of FOCS 2019, arXiv:1905.01495