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
- Chris Jones: Postdoc, Sept 2022-present
- Isabella Ziccardi: Postdoc, Nov 2022-present
- Caicai Chen: PhD Student, Sept 2020-present
- Lucas Pesenti: PhD Student, Sept 2021-present
- Jiyu Zhang: PhD Student, Sept 2022-present
Alumni
- Jonathan Shi: Postdoc, Sept. 2019 - Sept. 2022
- Fabrizio Pittorino: Postdoc, Dec 1, 2020-June 2021
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
- Tim Hsieh, April-July, 2022
- Pravesh Khotari, June-July, 2022
- Robert Wang, May-August, 2023
- David Zuckerman, June 7-10, 2023
- Anindya De, July 18-20, 2023
Jobs
- No current job announcements
Events
Papers
- Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus.
On the Role of Memory in Robust Opinion Dynamics
In Proc. of IJCAI 2023, arXiv:2302.08600
- Tommaso D'Orsi and Luca Trevisan
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
In Proc. of CCC 2023, pages 27:1-27:16, arXiv:2204.10881
- Fabrizio Pittorino, Antonio Ferraro, Gabriele Perugini, Christoph Feinauer, Carlo Baldassi, Riccardo Zecchina
Deep Networks on Toroids: Removing Symmetries Reveals the Structure of Flat Regions in the Landscape Geometry
Preprint, 2022, arXiv:2202.03038
- Lucas Pesenti and Adrian Vladu
Discrepancy minimization via regularization
In Proc. of SODA 2023
- Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi
Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond
In Proc. of ICALP 2022, pages 41:1-41:20, [open access paper]
- Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, and Luca Trevisan
Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models
In Proc. of AISTATS 2022, pages 10852-10880, arXiv:2108.04729
- Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi
Percolation and Epidemic Processes in One-Dimensional Small-World Networks
In Proc. of LATIN 2022, arXiv:2103.16398
- Antares Chen, Jonathan Shi and Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound
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