1.7k citations · 1.9k across the 33 of their papers we have counts for
39 papers
Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
Rafail Ostrovsky
We prove that the quantum code distance is NP-hard to approximate within an additive error of , for some constant , where is the number of qubits. Our reductions are…
Fast Networks for High-Performance Distributed Trust
Yicheng Liu, Rafail Ostrovsky, Scott Shenker +1
Organizations increasingly need to collaborate by performing a computation on their combined dataset, while keeping their data hidden from each other. Certain kinds of collaboratio…
Budget and Profit Approximations for Spanning Tree Interdiction
Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov
We give polynomial time logarithmic approximation guarantees for the budget minimization, as well as for the profit maximization versions of minimum spanning tree interdiction. In…
Game of Trust: How Trustworthy Does Your Blockchain Think You Are?
Petros Drineas, Rohit Nema, Rafail Ostrovsky +1
We investigate how a blockchain can distill the collective belief of its nodes regarding the trustworthiness of a (sub)set of nodes into a {\em reputation system} that reflects the…
A Refined Approximation for Euclidean k-Means
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani +2
In the Euclidean -Means problem we are given a collection of points in an Euclidean space and a positive integer . Our goal is to identify a collection of points…
Function Secret Sharing for PSI-CA:With Applications to Private Contact Tracing
Samuel Dittmer, Yuval Ishai, Steve Lu +5
In this work we describe a token-based solution to Contact Tracing via Distributed Point Functions (DPF) and, more generally, Function Secret Sharing (FSS). The key idea behind the…