Tommaso d'Orsi

According to our database, Tommaso d'Orsi authored at least 27 papers between 2020 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

Strongly Refuting Random CSP without Literals.

Siu On Chan, Tommaso d'Orsi, Jeff Xu

CoRR, April, 2026

Combinatorial Optimization using Comparison Oracles.

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Tight Differentially Private PCA via Matrix Coherence.

Tommaso d'Orsi, Gleb Novikov

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

2025

Combinatorial Optimization using Comparison Oracles.

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff

CoRR, November, 2025

On Purely Private Covariance Estimation.

Tommaso d'Orsi, Gleb Novikov

CoRR, October, 2025

Complexity of Local Search for CSPs Parameterized by Constraint Difference.

Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, Sijin Peng

Proceedings of the 20th International Symposium on Parameterized and Exact Computation, 2025

Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs.

Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil P. Vadhan, Jiyu Zhang

Proceedings of the Approximation, 2025

On Finding Randomly Planted Cliques in Arbitrary Graphs.

Francesco Agrimonti, Marco Bressan, Tommaso d'Orsi

Proceedings of the Approximation, 2025

2024

Max-Cut with ε-Accurate Predictions.

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi

CoRR, 2024

Private Graphon Estimation via Sum-of-Squares.

Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems.

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi

Proceedings of the Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, 2024

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering.

Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Multi-View Stochastic Block Models.

Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Perturb-and-Project: Differentially Private Similarities and Marginals.

Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Information-computation gaps in robust statistics.

Tommaso d'Orsi

PhD thesis, 2023

Higher degree sum-of-squares relaxations robust against oblivious outliers.

Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Private estimation algorithms for stochastic block models and mixture models.

Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions.

Yiding Hua, Jingqiu Ding, Tommaso d'Orsi, David Steurer

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs.

Tommaso d'Orsi, Luca Trevisan

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Fast algorithm for overcomplete order-3 tensor decomposition.

Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

On the well-spread property and its relation to linear regression.

Hongjie Chen, Tommaso d'Orsi

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers.

Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

The Complexity of Sparse Tensor PCA.

Davin Choo, Tommaso d'Orsi

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Consistent regression when oblivious outliers overwhelm.

Tommaso d'Orsi, Gleb Novikov, David Steurer

Proceedings of the 38th International Conference on Machine Learning, 2021

Robust recovery for stochastic block models.

Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Regress Consistently when Oblivious Outliers Overwhelm.

Tommaso d'Orsi, Gleb Novikov, David Steurer

CoRR, 2020

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates.

Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020