2 citations · 8 across the 17 of their papers we have counts for
24 papers
Active Learning on Adversarially Corrupted Graphs
Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi +2
Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} insi…
Strongly Refuting Random CSP without Literals
Siu On Chan, Tommaso d'Orsi, Jeff Xu
Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each co…
Complexity of Local Search for CSPs Parameterized by Constraint Difference
Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi +4
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization…
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
Tight Differentially Private PCA via Matrix Coherence
Tommaso d'Orsi, Gleb Novikov
We revisit the task of computing the span of the top singular vectors of a matrix under differential privacy. We show that a simple and efficient algorithm -…
On Purely Private Covariance Estimation
Tommaso d'Orsi, Gleb Novikov
We present a simple perturbation mechanism for the release of -dimensional covariance matrices under pure differential privacy. For large datasets with at least $n\geq d^2/\…
On Finding Randomly Planted Cliques in Arbitrary Graphs
Francesco Agrimonti, Marco Bressan, Tommaso d'Orsi
We study a planted clique model introduced by Feige where a complete graph of size is planted uniformly at random in an arbitrary -vertex graph. We give a simple dete…
Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
Tommaso d'Orsi, Chris Jones, Jake Ruotolo +2
Whether or not the Sparsest Cut problem admits an efficient -approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games C…
Multi-View Stochastic Block Models
Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi +1
Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention…
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC'12], where, given a random bipartite graph with edges and an unknown bipartition $(A…
Perturb-and-Project: Differentially Private Similarities and Marginals
Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto +2
We revisit the input perturbations framework for differential privacy where noise is added to the input and the result is then projected back to the space of adm…
Private graphon estimation via sum-of-squares
Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi +3
We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant numbe…
Max-Cut with -Accurate Predictions
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +2
We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are give…
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
Jingqiu Ding, Tommaso d'Orsi, Yiding Hua +1
We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $…
Private estimation algorithms for stochastic block models and mixture models
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi +4
We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best know…
Higher degree sum-of-squares relaxations robust against oblivious outliers
Tommaso d'Orsi, Rajai Nasser, Gleb Novikov +1
We consider estimation models of the form , where is some -dimensional signal we wish to recover, and is symmetrically distributed noise that may be unbounded…
On the well-spread property and its relation to linear regression
Hongjie Chen, Tommaso d'Orsi
We consider the robust linear regression model , where an adversary oblivious to the design may choose $\bolds…
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
Tommaso d'Orsi, Luca Trevisan
We define a novel notion of ``non-backtracking'' matrix associated to any symmetric matrix, and we prove a ``Ihara-Bass'' type formula for it. We use this theory to prove new resul…
Fast algorithm for overcomplete order-3 tensor decomposition
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu +2
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to . Our algorithm only involves…
Robust recovery for stochastic block models
Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser +1
We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms…
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser +3
We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an obl…
The Complexity of Sparse Tensor PCA
Davin Choo, Tommaso d'Orsi
We study the problem of sparse tensor principal component analysis: given a tensor with having i.i.d. Gaussian…
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov +1
We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being…
Consistent regression when oblivious outliers overwhelm
Tommaso d'Orsi, Gleb Novikov, David Steurer
We consider a robust linear regression model , where an adversary oblivious to the design may choose to corrupt all but an fractio…