12 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…
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…
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/…
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…
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 -…