2 citations · 8 across the 17 of their papers we have counts for
5 papers · 1 filter
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…